On the Length of Programs for Computing Finite Binary Sequences

By Gregory J. Chaitin. 1966

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Deep learning in neural networks: An overview (2014, methodology): “…the complexity of a solution candidate by the length of the shortest program that computes it (e.g., Blumer, Ehrenfeucht, Haussler, & Warmuth, 1987; Chaitin, 1966; Grünwald,Myung, & Pitt, 2005; Kolmogorov, 1965b; Levin, 1973a; Li & Vitányi, 1997; Rissanen, 1986; Solomonoff, 1964, 1978;Wallace &…”
Causal Inference Using the Algorithmic Markov Condition (2008, neutral): “Recall that the Kolmogorov complexityK(s) of a strings ∈ {0, 1}∗ is defined as the length of the shortest program that generates s u ing a previously defined universal prefix Turing machine [17], [18], [19], [20], [21], [4], [22].”
On Learning to Think: Algorithmic Information Theory for Novel Combinations of Reinforcement Learning Controllers and Recurrent Neural World Models (2015, background): “Given some RL problem, according to the AIT argument (Sec.”
One Big Net For Everything (2018, methodology): “As discussed in earlier work [77], according to the Theory of Algorithmic Information (AIT) or Kolmogorov Complexity [84, 31, 6, 34, 85, 36], given some universal computer, U , whose programs are encoded as bit strings, the mutual information between two programs p and q is expressed as K ( q | p )…”
QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS (2006, methodology): “The notion of Kolmogorov complexity has been used [3] to solve in a simple and elegant way many otherwise difficult problems, such as, e.”
Complexity–entropy analysis of daily stream flow time series in the continental United States (2014, background): “2011); for example, Kolmogorov–Chaitin algorithmic complexity (Kolmogorov 1965; Chaitin 1966), the Lempel–Ziv complexity (Lempel and Ziv 1976), the effective measure complexity of Grassberger (CE; Grassberger 1986), the e-machine complexity (Crutchfield and Young 1989), among others.”
Handbook of Applied Cryptography (2018, background): “Kolmogorov[704] and Chaitin [236] introduced the notion of so-called Turing-Kolmogorov -Chaitin complexity, which measures the minimum size of the input to a fixed universal Turing machine which can generate a given sequence; see also Martin-Löf [783].”
A catalog of Boolean concepts (2003, background): “Boolean complexity has properties paralleling those of Kolmogorov complexity (Kolmogorov, 1965; Solomonoff, 1964; Chaitin, 1966; Li & Vitányi, 1997).”
Computational Mechanics: Pattern and Prediction, Structure and Simplicity (1999, unknown): “If the limit goes to 1, on the other hand, we have a completely incompressible description and conclude, following Kolmogorov, Chaitin, and others, that O is random [37–40,42,43].”
Mathematical discoveries from program search with large language models (2023, background): “In a loose sense, FunSearch attempts to find solutions that have low Kolmogorov complexity 48–50 (which is the length of the shortest computer program that produces a given object as output), whereas traditional search procedures have a very different inductive bias.”
MML clustering of multi-state, Poisson, von Mises circular and Gaussian distributions (2000, methodology): “For an elaboration on the relation between MML, Chaitin’s work (Chaitin 1966) and Kolmogorov complexity, see Wallace and Dowe (1999).”
Predictability: a way to characterize complexity (2001, background): “The notion of algorithmic complexity, independently introduced by Kolmogorov [126], Chaitin [53,56] and Solomonov [207], is a way to formalize the intuitive idea of randomness of a sequence.”