2012/11/06 by Fernando Soler Toscano, Soler-Toscano, Fernando, Héctor Zenil +5 · 2 citations
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Pattern Formation and Solitons (nlin.PS) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1211.1302
openalex publication_date 2012/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Drawing on various notions from theoretical computer science, we present a\nnovel numerical approach, motivated by the notion of algorithmic probability,\nto the problem of approximating the Kolmogorov-Chaitin complexity of short\nstrings. The method is an alternative to the traditional lossless compression\nalgorithms, which it may complement, the two being serviceable for different\nstring lengths. We provide a thorough analysis for all \∑n=111 2n\nbinary strings of length n<12 and for most strings of length 12\≤ n\n\≤16 by running all \∼ 2.5 \× 1013 Turing machines with 5 states\nand 2 symbols (8\× 229 with reduction techniques) using the most\nstandard formalism of Turing machines, used in for example the Busy Beaver\nproblem. We address the question of stability and error estimation, the\nsensitivity of the continued application of the method for wider coverage and\nbetter accuracy, and provide statistical evidence suggesting robustness. As\nwith compression algorithms, this work promises to deliver a range of\napplications, and to provide insight into the question of complexity\ncalculation of finite (and short) strings.\n