Chaitin's constant

From Wikipedia, the free encyclopedia

In the computer science subfield of algorithmic information theory a Chaitin constant or halting probability is a real number that informally represents the probability that a randomly-chosen program will halt. These numbers are formed from a construction due to Gregory Chaitin.

Although there are infinitely many halting probabilities, 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 instead of Chaitin's constant when not referring to any specific encoding.

Each halting probability is a normal and transcendental real number which is not computable, which means that there is no halting algorithm that enumerates its digits.

Contents

[edit] Background

The definition of a halting probability relies on the existence of prefix-free universal computable functions. 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 a function F takes two arguments, each of which is a finite binary string, and returns a single binary string as output. The function F is called computable if there is a Turing machine that computes it.

The function F is called universal if the following property holds: for every computable function f of a single variable x there is a constant p such that for all x, F(p,x) = f(x). This means that F can be used to simulate any computable function of one variable. Informally, p represents a "program" for the computable function f, and F represents an emulator that takes the program as input and then executes it. Note that for any fixed p the function f(x) = F(p,x) is computable; thus the universality property states that all computable functions of one variable can be obtained in this fashion.

The domain of F is the set of all programs p such that for at least one value of x the value of F(p,x) is defined. 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 an instantaneous code on the set of finite binary strings. 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.

[edit] Definition of halting probabilities

Let PF be the domain of a prefix-free universal computable function F. The constant ΩF is then defined as

\Omega_F = \sum_{p \in P_F} 2^{-|p|},

where | p | denotes the length of a string p. This is an infinite sum which has one summand for every p in the domain of F. The requirement that the domain is prefix-free, together with Kraft's inequality, ensures that this sum converges to a real number between 0 and 1. If F is clear from context then ΩF may be denoted simply Ω, although different prefix-free universal computable functions lead to different values of Ω.

[edit] Use of Chaitin's constant in proving unsolved problems in number theory

Chaitin's constant can be used, in principle, to solve many outstanding problems in number theory, including Goldbach's conjecture and the Riemann hypothesis.[1] Goldbach's conjecture says every even number greater than 2 is the sum of two primes. For a given even number, let a computer program search for corresponding two primes. If Goldbach's conjecture is true, the program advances to the next even number and the search is continued. If there are no two primes that add to the even number, a counterexample has been found, the program halts and Goldbach's conjecture has been disproved. Let this program be N bits long. Given unlimited resources and time, Chaitin's number can be used to prove Goldbach's conjecture as follows. In parallel, all of the programs of N+1 bits or less are run. If the N bit Goldbach program halts, then the conjecture is proven false. If, on the other hand, enough of the other programs stop such that one more program stopping would result in a number exceeding Chaitin's number, then if a program hasn't halted, it will never halt and Goldbach's conjecture is proved. To use this procedure, we only require the first N+1 bits of Chaitin's number.

The same Chaitin constant can be used to prove (or disprove) the Riemann hypothesis and many other of the unsolved problems in mathematics.

[edit] Interpretation as a probability

The Cantor space is the collection of all infinite sequences of 0s and 1s. A halting probability can be interpreted as the measure of a certain subset of Cantor space under the usual probability measure on Cantor space. It is from this interpretation that halting probabilities take their name.

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

P = \{p_1,p_2,\ldots\}.

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

\sum_{p \in P} 2^{-|p|}

represents the measure of the set

\bigcup_{i \in \mathbb{N}} S_i.

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.

[edit] Properties

Each Chaitin constant Ω has the following properties:

  • It is algorithmically random. This means that for each particular programming language there is a constant C such that for each n any halting program in that language that outputs the first n bits must have length no shorter than (n — C).
  • 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 rational numbers q such that q ≤ Ω is computably enumerable; a real number with such a property is called a left-c.e. real number in recursion theory.
  • It is Turing equivalent to the halting problem and thus at level \Sigma^0_1 of the arithmetical hierarchy.

Not every set 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.

[edit] Uncomputability of halting probabilities

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, Ω can not 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.

[edit] Incompleteness theorem for halting probabilities

Main article: Kolmogorov complexity#Chaitin's incompleteness theorem

For each specific consistent effectively represented axiomatic system for the natural numbers, such as Peano arithmetic, there exists a constant N such that no bit of Ω after the Nth can be proven to be one or zero within that system. The constant N depends on how the formal system is effectively represented, and thus does not directly reflect the complexity of the axiomatic system. This incompleteness result is similar to Gödel's incompleteness theorem in that it shows that no consistent formal theory for arithmetic can be complete.

[edit] Calculation of the start of a Chaitin Ω

Calude, Dinneen, and Shu have calculated the first 64 bits of a Chaitin ΩU for a particular machine. These are, in binary notation

0.0000001000000100000110001000011010001111110010111011101000010000...

or in decimal notation

0.0078749969978123844...

Note that the notion of whether a specific digit of Ω can be correctly calculated is different from the notion of computability: any specific digit of any number is computable since for any integer there is a program printing it.

[edit] Super Omega

As mentioned above, the first n bits of Gregory Chaitin's constant Omega are random or incompressible in the sense that we cannot compute them by a halting algorithm with fewer than n-O(1) bits. However, consider the short but never halting algorithm which systematically lists and runs all possible programs; whenever one of them halts its probability gets added to the output (initialized by zero). After finite time the first n bits of the output will never change any more (it does not matter that this time itself is not computable by a halting program). So there is a short non-halting algorithm whose output converges (after finite time) onto the first n bits of Omega, for any n. In other words, the enumerable first n bits of Omega are highly compressible in the sense that they are limit-computable by a very short algorithm; they are not random with respect to the set of enumerating algorithms. Jürgen Schmidhuber (2000) constructed a limit-computable "Super Omega" which in a sense is much more random than the original limit-computable Omega, as one cannot significantly compress the Super Omega by any enumerating non-halting algorithm.

[edit] See also

[edit] References

  1. ^ Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd Edition, Wiley-Interscience, 2006.
  • Cristian S. Calude (2002). Information and Randomness: An Algorithmic Perspective, second edition. Springer. ISBN 3-5404-3466-6
  • Cristian S. Calude, Michael J. Dinneen, and Chi-Kou Shu. Computing a Glimpse of Randomness.
  • R. Downey, and D. Hirschfeldt (200?), Algorithmic Randomness and Complexity, monograph in preparation, Springer-Verlag. Preliminary version can be found online.
  • Ming Li and Paul Vitányi (1997). An Introduction to Kolmogorov Complexity and Its Applications. Springer. Introduction chapter full-text.
  • Jürgen Schmidhuber (2000). Algorithmic Theories of Everything (arXiv: quant-ph/ 0011122). Journal reference: J. Schmidhuber (2002). Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit. International Journal of Foundations of Computer Science 13(4):587-612.

[edit] External links