| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
07 February 2025 |
|
| | | |
|
Article overview
| |
|
A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity | Hector Zenil
; Fernando Soler-Toscano
; Narsis A. Kiani
; Santiago Hernández-Orozco
; Antonio Rueda-Toicen
; | Date: |
1 Sep 2016 | Abstract: | We investigate the properties of a divide-and-conquer Block Decomposition
Method (BDM), which extends the power of a Coding Theorem Method (CTM) that
approximates local estimations of algorithmic complexity and of logical depth
based upon Solomonoff-Levin’s theory of algorithmic probability, thereby
providing a closer connection to algorithmic complexity. The strategy behind
BDM is to find small computer programs that produce the components of a larger,
decomposed object. The set of short computer programs can then be artfully
arranged in sequence so as to produce the original object and to estimate an
upper bound on the greatest length of the shortest computer program that
produces said original object. We show that the method provides efficient
estimations of algorithmic complexity but that it performs like Shannon entropy
when it loses accuracy. We estimate errors and study the behaviour of BDM for
different boundary conditions, all of which are compared and assessed in
detail. The measure may be adapted for use with more multi-dimensional objects
than strings, objects such as arrays and tensors. To test the measure we
provide proofs of the algorithmic complexity relations among dual, isomorphic
and cospectral graphs. Finally, we introduce a measure based upon the seminal
concept of logical depth whose numerical comparisons to CTM and BDM agree with
the theoretical expectations. We provide implementations in most major
programming languages --Mathematica, Matlab, R, Java, Perl, Python, Pascal,
C++, and Haskell-- and a free online algorithmic complexity calculator. | Source: | arXiv, 1609.0110 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|