A Theory of Program Size Formally Identical to Information Theory

By Gregory J. Chaitin. 1975

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

Algorithmic independence of initial condition and dynamical law in thermodynamics and causal inference (2015, background): “More precisely, K(s) is the length of the shortest program on a universal Turing machine that generates s and stops then [19, 20].”
Causal Markov condition for submodular information measures (2010, background): “Note that defining R(s) := K(s) implies that the conditional information reads R(s|t) = K(s|t ∗) due to (Chaitin, 1975) K(s, t) + = K(t) + K(s|t∗) , see also (Gács et al.”
Causal Inference Using the Algorithmic Markov Condition (2008, background): “The importance of the causal Markov condition lies in the fact that it links causal terms like “direct causes” and “non-effects” to informational relevance of observables.”
First Experiments with PowerPlay (2012, background): “Thus, any network topology in which there exists a path from the online or task inputs to the halt neuron can run self-delimiting programs [10, 3, 26, 21] studied in the theory of Kolmogorov complexity and algorithmic probability [27, 8].”
Optimal Ordered Problem Solver (2002, neutral): “Note that unlike the traditional Turing machine-based setup by Levin (1974) and Chaitin (1975) (always yielding binary programs q with probability 2 − l ( q ) ) this framework of self-generated continuation probabilities allows for token selection probabilities close to 1.0, that is, even long…”
Self-Delimiting Neural Networks (2012, background): “One reason for the current lack of AOPS-based RNNs may be that traditional AOPS variants are designed to search a space of sequential self-delimiting (SLIM) programs [42, 3] (Section 1.2).”
Information-geometric approach to inferring causal directions (2012, background): “This measure will never appear explicitly and should not be confused with reference probability distributions that occur all over the article.”
On initial segment complexity and degrees of randomness (2008, background): “Chaitin [2] proposed the halting probability Ω of the universal prefix-free machine U as a natural example of a 1-random real.”
Justifying Additive Noise Model-Based Causal Discovery via Algorithmic Information Theory (2009, background): “Let s, t be two binary strings that describe the observed objects and let K ( s ) denote the algorithmic information (or “Kolmogorov complexity”), i.e., the length of the shortest program that generates s on a universal Turing machine [7, 15, 2, 1].”
Goedel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements (2003, background): “1 that searches only among self-delimiting [23, 6] proof techniques starting with the most recently frozen proof technique.”
The Nature of Chance and Probability (2005, background): “Kolmogorov and Chaitin’s vision (1975) of a random sequence is a highly irregular or complex sequence that cannot be reproduced from a set of instructions which is shorter that the sequence itself (Zabell, 1992, Delahaye, 1999).”
Computability and randomness (2009, background): “14, which we will call the Machine Existence Theorem (it is also refered to in the literature as the Kraft-Chaitin Theorem). Unlike 2.1.14, it is non-trivial. It will be an important tool in future constructions. First we discuss Kraft’s Theorem. Then we introduce our tool which is an effectivizatio”