Numerical Evaluation of Algorithmic Complexity for Short Strings: A Glance into the Innermost Structure of Randomness - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Applied Mathematics and Computation Année : 2012

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

Résumé

We describe an alternative method (to compression) that combines several theoretical and experimental results to numerically approximate the algorithmic Kolmogorov-Chaitin complexity of all Sigma(8)(n-1)2(n) 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 four 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-Chaitin coding theorem. (

Dates et versions

hal-00825530 , version 1 (24-05-2013)

Identifiants

Citer

Jean-Paul Delahaye, Hector Zenil. Numerical Evaluation of Algorithmic Complexity for Short Strings: A Glance into the Innermost Structure of Randomness. Applied Mathematics and Computation, 2012, 219 (1), pp.63-77. ⟨10.1016/j.amc.2011.10.006⟩. ⟨hal-00825530⟩
141 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More