Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures
arXiv:1211.4891 · doi:10.3233/COM-13019
Abstract
We show that real-value approximations of Kolmogorov-Chaitin (K_m) using the algorithmic Coding theorem as calculated from the output frequency of a large set of small deterministic Turing machines with up to 5 states (and 2 symbols), is in agreement with the number of instructions used by the Turing machines producing s, which is consistent with strict integer-value program-size complexity. Nevertheless, K_m proves to be a finer-grained measure and a potential alternative approach to lossless compression algorithms for small entities, where compression fails. We also show that neither K_m nor the number of instructions used shows any correlation with Bennett's Logical Depth LD(s) other than what's predicted by the theory. The agreement between theory and numerical calculations shows that despite the undecidability of these theoretical measures, approximations are stable and meaningful, even for small programs and for short strings. We also announce a first Beta version of an Online Algorithmic Complexity Calculator (OACC), based on a combination of theoretical concepts, as a numerical implementation of the Coding Theorem Method.
22 pages, 8 images. This article draws heavily from arXiv:1211.1302
References in corpus (2)
Cited by in corpus (7)
- Correlation of Automorphism Group Size and Topological Properties with Program-size Complexity Evaluations of Graphs and Complex Networks
- A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions
- Natural scene statistics mediate the perception of image complexity
- Two-Dimensional Kolmogorov Complexity and Validation of the Coding Theorem Method by Compressibility
- Approximations of Algorithmic and Structural Complexity Validate Cognitive-behavioural Experimental Results
- Algorithmic complexity for psychology: A user-friendly implementation of the coding theorem method
- On the Complexity and Behaviour of Cryptocurrencies Compared to Other Markets