Affiliations: Grupo de Lógica, Lenguaje e Información, University of Seville (Spain) C/ Camilo José Cela s/n, 41018 Sevilla, Spain [email protected] personal.us.es/fsoler | Unit of Computational Medicine, Center for Molecular Medicine, Karolinska Institutet Karolinska University Hospital, L8:05, S-171 76, Stockholm, Sweden [email protected] mathrix.org/zenil | Laboratoire d'Informatique Fondamentale de Lille, Université des Sciences et Technologies de Lille, France 59655 Villeneuve d'Ascq Cédex, France [email protected] lifl.fr/∼delahaye | CHART (paris-reasoning), University Paris-8 and EPHE 2 Rue de la Liberté, 93200 Saint-Denis, France [email protected] paris-reasoning.eu
Abstract: We show that real-value approximations of Kolmogorov-Chaitin complexity K(s) 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 consistent with the number of instructions used by the Turing machines producing s, which in turn is consistent with strict integer-value program-size complexity (based on our knowledge of the smallest machine in terms of the number of instructions used). We also show that neither K(s) nor the number of instructions used manifests any correlation with Bennett's Logical Depth LD(s), other than what's predicted by the theory (shallow and non-random strings have low complexity under both measures). The agreement between the theory and the numerical calculations shows that despite the undecidability of these theoretical measures, the rate of convergence of approximations is stable enough to devise some applications. We announce a Beta version of an Online Algorithmic Complexity Calculator (OACC) implementing these methods.
