On the Kolmogorov-Chaitin Complexity for short sequences
From MaRDI portal
Publication:5448299
zbMATH Open1137.68412arXiv0704.1043MaRDI QIDQ5448299FDOQ5448299
Authors: Hector Zenil, Jean-Paul Delahaye 
Publication date: 20 March 2008
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.
Full work available at URL: https://arxiv.org/abs/0704.1043
Recommendations
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80)
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)
