On the Kolmogorov-Chaitin Complexity for short sequences

MaRDI QIDQ5448299zbMATH OpenFDO

Authors Hector Zenil, Jean-Paul Delahaye

Publication date 20 March 2008

Full work available at URL https://arxiv.org/abs/0704.1043

zbMATH Keywords

Kolmogorov-Chaitin complexityexperimental approach

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80)

Abstract: A drawback of Kolmogorov-Chaitin complexity (K) as a function from s to the shortest program producing s is its noncomputability which limits its range of applicability. Moreover, when strings are short, the dependence of K on a particular universal Turing machine U can be arbitrary. In practice one can approximate it by computable compression methods. However, such compression methods do not always provide meaningful approximations--for strings shorter, for example, than typical compiler lengths. In this paper we suggest an empirical approach to overcome this difficulty and to obtain a stable definition of the Kolmogorov-Chaitin complexity for short sequences. Additionally, a correlation in terms of distribution frequencies was found across the output of two models of abstract machines, namely unidimensional cellular automata and deterministic Turing machine.

Recommendations

• scientific article; zbMATH DE number 176218
• scientific article; zbMATH DE number 3917706
• scientific article; zbMATH DE number 107774
• Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness
• Kolmogorov Complexity and Noncomputability

Cited in

(6)

• Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness
• On the complexity of a family of \(k\)-context-free sequences
• Analogical proportions: from equality to inequality
• Algorithmic information dynamics of cellular automata
• Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks
• Abstract Chaitin's theorem and its methodological consequences

This page was built for publication: On the Kolmogorov-Chaitin Complexity for short sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5448299)