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 construction by Gregory Chaitin which describes the probability that a randomly generated program for a given model of computation or programming language will halt. It is usually denoted with Ω.
It is a normal and transcendental number which can be defined but cannot be completely computed. This means one can prove that there is no algorithm which produces the digits of Ω, although its first few digits can be calculated in simple cases.[1]
The proof of the uncomputability of Ω 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.
As Ω depends on the program encoding used, it should be called Chaitin's construction instead of Chaitin's constant when not referring to any specific encoding.
Contents |
[edit] Definition
To define Ω formally, we first need to fix a (Turing-complete) model of computation, for instance Turing machines or Lisp or Pascal programs. (Here, program means the concatenation of executable code and input.) We then need to specify an instantaneous encoding of programs as bit strings. This encoding has the property that if w encodes a syntactically correct program, then no proper prefix of w encodes a syntactically correct program. Given an arbitrary Turing machine M, this can always be achieved by using the following algorithm:
- Read a bit of the input z.
- Before reading any more, simulate M on all possible extensions y (including the empty one) of z simultaneously until some extension halts, if ever.
- If y = z, then halt and output M(y); otherwise go to step 1.
Let P be the set of all programs which halt. The constant Ω is then defined as:
This is an infinite sum which has one summand for every syntactically correct program which halts. |p| stands for the length of the bit string of p. The requirement that programs be prefix-free, together with Kraft's inequality, ensures that this sum converges to a real number between 0 and 1.
[edit] Notes
It can then be shown that Ω represents the probability that a randomly selected infinite sequence of 0s and 1s begins with a bit string (of any finite length) that represents a halting program. It is for this reason that Ω is called a halting probability.
If you fix, in addition to the computation model and encoding mentioned above, a specific consistent axiomatic system for the natural numbers, say Peano's axioms, then there exists a constant N such that no bit of Ω after the N-th can be proven to be one or zero within that system. (The constant N heavily depends on the encoding choices and does not reflect the complexity of the axiomatic system in any way.) This is an incompleteness result akin to Gödel's incompleteness theorem and Chaitin's own result mentioned under algorithmic information theory.
Chaitin's constant is uncompressible (others may say irreducible, or algorithmically random). This means that in a particular programming language, a program which will write the first n bits of Ω for that language must be at least n bits itself, including any input data.
Chaitin's constant is a normal number (as if its binary digits were generated by coin tossing). Although “most” numbers are normal, Chaitin's construct is an important one, so the recently mentioned article gives a detailed description on it.
[edit] Calculation of the start of a Chaitin Ω
Cristian S. Calude, Michael J. Dinneen, and Chi-Kou Shu[1] have calculated the first 64 bits of a Chaitin ΩU for a particular machine: they in fact calculated 84 bits, but only the first 64 are reliable. These are, in binary notation
- 0.0000001000000100000110001000011010001111110010111011101000010000...
or in decimal notation
- 0.0078749969978123844...
However, they also confirm the more important strong result in the opposite direction mentioned above, that in general only a finite number of digits of Ω may be calculated or, equivalently, that from some point in the binary expansion onwards none of the digits of Ω may be calculated. 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, but for some digits of Ω it is impossible to determine which program is correct.
[edit] See also
[edit] Notes
- ^ a b Computing a Glimpse of Randomness by Cristian S. Calude, Michael J. Dinneen, and Chi-Kou Shu
[edit] External links
- Omega and why math 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, Scientific American, March 2006
- The Limits of Reason, Free version of above article without all pictures from Chaitin's own webpage.
