Numerical Evaluation of Algorithmic Complexity for Short Strings: A Glance into the Innermost Structure of Randomness

2011/01/25 by Jean-Paul Delahaye, Delahaye, Jean-Paul, Héctor Zenil +1
Computer Science · Mathematics · #Algorithms and Data Compression #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #E.4 #F.1 #F.1.3 #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1101.4795

openalex publication_date 2011/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We describe an alternative method (to compression) that combines several theoretical and experimental results to numerically approximate the algorithmic (Kolmogorov-Chaitin) complexity of all ∑_n=1⁸2ⁿ bit strings up to 8 bits long, and for some between 9 and 16 bits long. This is done by an exhaustive execution of all deterministic 2-symbol Turing machines with up to 4 states for which the halting times are known thanks to the Busy Beaver problem, that is 11019960576 machines. An output frequency distribution is then computed, from which the algorithmic probability is calculated and the algorithmic complexity evaluated by way of the (Levin-Zvonkin-Chaitin) coding theorem.

Related

• Calculating Kolmogorov Complexity from the Output Frequency\n Distributions of Small Turing Machines
• On the Kolmogorov-Chaitin Complexity for short sequences
• Complexity analysis for algorithmically simple strings
• A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences
• Two-Dimensional Kolmogorov Complexity and Validation of the Coding Theorem Method by Compressibility