Chaitin's constant (halting probability)
Statement
For a fixed universal prefix-free Turing machine U, Chaitin's constant Ω is defined as ∑_{U(p) halts} 2^{-|p|}, the halting probability of a randomly chosen program bits. Ω is a real number strictly between 0 and 1 that is maximally incompressible: its initial segments have near-maximal Kolmogorov (prefix) complexity. Ω encodes halting information and is uncomputable; Chaitin also proved incompleteness results showing that no consistent formal system of bounded complexity can prove statements of the form "K(x) > n" for all sufficiently large n. Together with Solomonoff and Kolmogorov, this completes the classical triangle of algorithmic information theory.
Formula
Ω = ∑_{U(p)↓} 2^{-|p|}; K(Ω↾n) ≥ n − O(1)
Equation
Halting probability; algorithmic randomness of Ω
Proof sketch
Chaitin, "A Theory of Program Size Formally Identical to Information Theory," J. ACM 22 (1975). Uses prefix machines, Kraft inequality, and connections between program-size complexity and Gödel incompleteness.
Source
Chaitin, G. J. A theory of program size formally identical to information theory. Journal of the ACM 22 (1975), 329–340.
Domains
mathematics, computer-science