Towards a stable definition of Kolmogorov-Chaitin complexity

Laboratoire d’Informatique Fondamentale de Lille (CNRS)Institut d’Histoire et de Philosophie des Sciences et des Techniques, (CNRS, ENS, Universite Paris 1)´Carnegie Mellon Universityhector.zenil@lifl.fr, hector.zenil-chavez@malix.univ-paris1.fr, hectorz@andrew.cmu.eduAbstract. Although information content is invariant up to an additive constant, the range of pos-sible additive constants applicable to programming languages is so large that in practice it plays amajor role in the actual evaluation of K(s), the Kolmogorov-Chaitin complexity of a string s. Someattempts have been made to arrive at a framework stable enough for a concrete definition of K, in-dependent of any constant under a programming language, by appealing to the naturalness of thelanguage in question. The aim of this paper is to present an approach to overcome the problem bylooking at a set of models of computation converging in output probability distribution such that thatnaturalness can be inferred, thereby providing a framework for a stable definition of Kunder the setof convergent models of computation.Keywords: algorithmic information theory, program-size complexity.

• Publication year

  2008

• Venue

  arXiv.org

• Publication date

  2008-04-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 0804.3459
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Ockham's Razor, Truth, and Information

  2007cited by this paper
• Algorithmic information theory

  2007cited by this paper
• On the Kolmogorov-Chaitin Complexity for short sequences

  2007cited by this paper
• Binary Lambda Calculus and Combinatory Logic

  2006cited by this paper
• Handbook on the Philosophy of Information

  2006cited by this paper
• Permutation, Parametric, and Bootstrap Tests of Hypotheses (3rd ed.)

  2005cited by this paper
• Permutation, Parametric, and Bootstrap Tests of Hypotheses

  2005cited by this paper
• A New Kind of Science

  2003cited 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
• Information and Randomness: An Algorithmic Perspective

  1994cited by this paper
• Information and Randomness: An Algorithmic Perspective

  1994cited by this paper
• 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
• Statistical Methods

  1959cited by this paper
• The Theory of Group-Reduced Distributions

  1927cited by this paper

• An Additively Optimal Interpreter for Approximating Kolmogorov Prefix Complexity

  2024influential citation
• Coding-theorem like behaviour and emergence of the universal distribution from resource-bounded algorithmic probability

  2017cites this paper
• A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences

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

  2015cites this paper
• On the role of simplicity in science

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

  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
• Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines

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

  2011influential citation
• 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
• Clustering based on kolmogorov information

  2010cites this paper
• Clustering Based on Kolmogorov Information

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

  2009cites 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