On the Kolmogorov-Chaitin Complexity for short sequences

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.

• Publication year

  2007

• Venue

  arXiv.org

• Publication date

  2007-04-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1142/9789812770837_0006arXiv 0704.1043
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Algorithmic information theory

  2007influential reference
• Meta Math!: The Quest for Omega

  2004cited by this paper
• A PRELIMINARY REPORT ON A GENERAL THEORY OF INDUCTIVE INFERENCE

  2001cited by this paper
• The Discovery of Algorithmic Probability

  1997cited by this paper
• The miraculous universal distribution

  1997influential reference
• Information and Randomness: An Algorithmic Perspective

  1994cited by this paper
• Information, Randomness and Incompleteness

  1987influential reference
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

  1970cited by this paper

• All Kolmogorov complexity functions are optimal, but are some more optimal?

  2025cites this paper
• Algorithmic Information Dynamics of Cellular Automata

  2021cites this paper
• Estimating Algorithmic Information Using Quantum Computing for Genomics Applications

  2021cites this paper
• A Computable Piece of Uncomputable Art whose Expansion May Explain the Universe in Software Space

  2021cites this paper
• ACSS-q: Algorithmic complexity for short strings via quantum accelerated approach

  2020cites this paper
• Quines are the Fittest Programs - Large Nesting Algorithmic Probability Converges to Constructors

  2020cites this paper
• Algorithmic Information Dynamics

  2020cites this paper
• The computational inevitability of life: self-replication under resource-bounded nested algorithmic probability

  2020cites this paper
• Compression is Comprehension, and the Unreasonable Effectiveness of Digital Computation in the Natural World

  2019cites this paper
• Algorithmic Probability Method Versus Kolmogorov Complexity with No-Threshold Encoding Scheme for Short Time Series: An Analysis of Day-To-Day Hourly Solar Radiation Time Series over Tropical Western Indian Ocean

  2019cites this paper
• Analogical proportions: From equality to inequality

  2018cites this paper
• Boolean Analogical Proportions - Axiomatics and Algorithmic Complexity Issues

  2017cites this paper
• A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity

  2016cites this paper
• A Computable Measure of Algorithmic Probability by Finite Approximations

  2015cites this paper
• Approximations of algorithmic and structural complexity validate cognitive-behavioral experimental results

  2015cites this paper
• Algorithmic Complexity for Short Strings

  2014cites this paper
• Information Measures of Complexity, Emergence, Self-organization, Homeostasis, and Autopoiesis

  2013cites this paper
• Correlation of automorphism group size and topological properties with program−size complexity evaluations of graphs and complex networks

  2013cites this paper
• Two-dimensional Kolmogorov complexity and an empirical validation of the Coding theorem method by compressibility

  2012cites this paper
• Complexity and information: Measuring emergence, self-organization, and homeostasis at multiple scales

  2012cites this paper
• Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines

  2012cites this paper
• Nature-Like Computation and a Measure of Programmability 1

  2012cites this paper
• Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures

  2012cites this paper
• An Algorithmic Approach to Information and Meaning : A Formal Framework for a Philosophical Discussion

  2012cites this paper
• Two-Dimensional Kolmogorov Complexity and Validation of the Coding Theorem Method by Compressibility

  2012cites this paper
• Une approche expérimentale à la théorie algorithmique de la complexité

  2011cites this paper
• Sloane's Gap. Do Mathematical and Social Factors Explain the Distribution of Numbers in the OEIS ?

  2011cites this paper
• Le fossé de Sloane

  2011cites this paper
• Un metodo estable para la evaluacion de la complejidad algoritmica de cadenas cortas

  2011cites this paper
• An Algorithmic Approach to Information and Meaning

  2011cites this paper
• An Algorithmic Approach to Information and Meaning: A Formal Framework for a Philosophical Discussion

  2011cites this paper
• The World is Either Algorithmic or Mostly Random

  2011cites this paper
• Numerical evaluation of algorithmic complexity for short strings: A glance into the innermost structure of randomness

  2011cites this paper
• Algorithmic complexity for short binary strings applied to psychology: a primer

  2011cites this paper
• An algorithmic information-theoretic approach to the behaviour of financial markets

  2010cites this paper
• Image characterization and classification by physical complexity

  2010cites this paper
• Image information content characterization and classification by physical complexity

  2010cites this paper
• On the Algorithmic Nature of the World

  2009cites this paper
• Le hasard et les sources de la variation biologique : analyse critique d'une notion multiple

  2009cites this paper
• Towards a stable definition of Kolmogorov-Chaitin complexity

  2008cites this paper
• Distributed under Creative Commons Cc-by 4.0 Two-dimensional Kolmogorov Complexity and an Empirical Validation of the Coding Theorem Method by Compressibility

  year unknowncites this paper