Chaitin's constant
This article includes a list of general references, but it lacks sufficient corresponding inline citations. (November 2011) |
In the computer science subfield of algorithmic information theory, a Chaitin constant (Chaitin omega number)[1] or halting probability is a real number that, informally speaking, represents the probability that a randomly constructed program will halt. These numbers are formed from a construction due to Gregory Chaitin.
Although there are infinitely many halting probabilities, one for each (universal, see below) method of encoding programs, it is common to use the letter Ω to refer to them as if there were only one. Because Ω depends on the program encoding used, it is sometimes called Chaitin's construction when not referring to any specific encoding.
Each halting probability is a normal and transcendental real number that is not computable, which means that there is no algorithm to compute its digits. Each halting probability is Martin-Löf random, meaning there is not even any algorithm which can reliably guess its digits.
Background
The definition of a halting probability relies on the existence of a prefix-free universal computable function. Such a function, intuitively, represents a programming language with the property that no valid program can be obtained as a proper extension of another valid program.
Suppose that F is a partial function that takes one argument, a finite binary string, and possibly returns a single binary string as output. The function F is called computable if there is a Turing machine that computes it, in the sense that for any finite binary strings x and y, F(x) = y if and only if the Turing machine halts with y on its tape when given the input x.
The function F is called
The domain of F is the set of all inputs p on which it is defined. For F that are universal, such a p can generally be seen both as the concatenation of a program part and a data part, and as a single program for the function F.
The function F is called prefix-free if there are no two elements p, p′ in its domain such that p′ is a proper extension of p. This can be rephrased as: the domain of F is a
The domain of any universal computable function is a computably enumerable set but never a computable set. The domain is always Turing equivalent to the halting problem.
Definition
Let PF be the domain of a prefix-free universal computable function F. The constant ΩF is then defined as
- ,
where denotes the length of a string p. This is an
Relationship to the halting problem
Knowing the first N bits of Ω, one could calculate the halting problem for all programs of a size up to N. Let the program p for which the halting problem is to be solved be N bits long. In dovetailing fashion, all programs of all lengths are run, until enough have halted to jointly contribute enough probability to match these first N bits. If the program p hasn't halted yet, then it never will, since its contribution to the halting probability would affect the first N bits. Thus, the halting problem would be solved for p.
Because many outstanding problems in number theory, such as Goldbach's conjecture, are equivalent to solving the halting problem for special programs (which would basically search for counter-examples and halt if one is found), knowing enough bits of Chaitin's constant would also imply knowing the answer to these problems. But as the halting problem is not generally solvable, and therefore calculating any but the first few bits of Chaitin's constant is not possible in a very concise language, this just reduces hard problems to impossible ones, much like trying to build an oracle machine for the halting problem would be.
Interpretation as a probability
The
The probability measure on Cantor space, sometimes called the fair-coin measure, is defined so that for any binary string x the set of sequences that begin with x has measure 2−|x|. This implies that for each natural number n, the set of sequences f in Cantor space such that f(n) = 1 has measure 1/2, and the set of sequences whose nth element is 0 also has measure 1/2.
Let F be a prefix-free universal computable function. The domain P of F consists of an infinite set of binary strings
- .
Each of these strings pi determines a subset Si of Cantor space; the set Si contains all sequences in cantor space that begin with pi. These sets are disjoint because P is a prefix-free set. The sum
represents the measure of the set
- .
In this way, ΩF represents the probability that a randomly selected infinite sequence of 0s and 1s begins with a bit string (of some finite length) that is in the domain of F. It is for this reason that ΩF is called a halting probability.
Properties
Each Chaitin constant Ω has the following properties:
- It is algorithmically random (also known as Martin-Löf random or 1-random).[2]This means that the shortest program to output the first n bits of Ω must be of size at least n − O(1). This is because, as in the Goldbach example, those n bits enable us to find out exactly which programs halt among all those of length at most n.
- As a consequence, it is a normal number, which means that its digits are equidistributed as if they were generated by tossing a fair coin.
- It is not a computable number; there is no computable function that enumerates its binary expansion, as discussed below.
- The set of recursion theory.
- The set of rational numbers q such that q > Ω is not computably enumerable. (Reason: every left-c.e. real with this property is computable, which Ω isn't.)
- Ω is an arithmetical number.
- It is Turing equivalent to the halting problem and thus at level of the arithmetical hierarchy.
Not every set that is Turing equivalent to the halting problem is a halting probability. A finer equivalence relation, Solovay equivalence, can be used to characterize the halting probabilities among the left-c.e. reals.[4] One can show that a real number in [0,1] is a Chaitin constant (i.e. the halting probability of some prefix-free universal computable function) if and only if it is left-c.e. and algorithmically random.[4] Ω is among the few definable algorithmically random numbers and is the best-known algorithmically random number, but it is not at all typical of all algorithmically random numbers.[5]
Uncomputability
A real number is called computable if there is an algorithm which, given n, returns the first n digits of the number. This is equivalent to the existence of a program that enumerates the digits of the real number.
No halting probability is computable. The proof of this fact relies on an algorithm which, given the first n digits of Ω, solves Turing's halting problem for programs of length up to n. Since the halting problem is undecidable, Ω cannot be computed.
The algorithm proceeds as follows. Given the first n digits of Ω and a k ≤ n, the algorithm enumerates the domain of F until enough elements of the domain have been found so that the probability they represent is within 2−(k+1) of Ω. After this point, no additional program of length k can be in the domain, because each of these would add 2−k to the measure, which is impossible. Thus the set of strings of length k in the domain is exactly the set of such strings already enumerated.
Algorithmic randomness
A real number is random if the binary sequence representing the real number is an algorithmically random sequence. Calude, Hertling, Khoussainov, and Wang showed[6] that a recursively enumerable real number is an algorithmically random sequence if and only if it is a Chaitin's Ω number.
Incompleteness theorem for halting probabilities
For each specific consistent effectively represented
Super Omega
As mentioned above, the first n bits of
For an alternative "Super Ω", the
See also
References
- mathworld.wolfram.com, Chaitin's Constant. Retrieved 28 May 2012
- ^ Downey & Hirschfeldt 2010, Theorem 6.1.3.
- ^ Downey & Hirschfeldt 2010, Theorem 5.1.11.
- ^ a b Downey & Hirschfeldt 2010, p. 405.
- ^ Downey & Hirschfeldt 2010, pp. 228–229.
- (PDF) from the original on 19 January 2004, retrieved 20 March 2022
- PMID 22711870.
Works cited
- Calude, Cristian S. (2002). Information and Randomness: An Algorithmic Perspective (second ed.). Springer. ISBN 3-540-43466-6.
- Downey, R.; Hirschfeldt, D. (2010). Algorithmic Randomness and Complexity. Springer-Verlag.
- Li, Ming; Vitányi, Paul (1997). An Introduction to Kolmogorov Complexity and Its Applications. Springer. Introduction chapter full-text.
- . Preprint: Algorithmic Theories of Everything (arXiv: quant-ph/ 0011122)
External links
- Aspects of Chaitin's Omega Survey article discussing recent advances in the study of Chaitin's Omega.
- Omega and why maths has no TOEs article based on one written by Gregory Chaitin which appeared in the August 2004 edition of Mathematics Today, on the occasion of the 50th anniversary of Alan Turing's death.
- The Limits of Reason, Gregory Chaitin, originally appeared in Scientific American, March 2006.
- Limit-computable Super Omega more random than Omega and generalizations of algorithmic information, by Jürgen Schmidhuber