Chaitin's constant

Template:Short description Template:Redirect Template:Use dmy dates In the computer science subfield of algorithmic information theory, a Chaitin constant (Chaitin omega number)<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> 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 Template:Math to refer to them as if there were only one. Because Template:Math 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 program in a programming language with the property that no valid program can be obtained as a proper extension of another valid program.

Suppose that Template:Mvar is a partial function that takes one argument, a finite binary string, and possibly returns a single binary string as output. The function Template:Mvar is called computable if there is a Turing machine that computes it, in the sense that for any finite binary strings Template:Mvar and Template:Mvar, Template:Math if and only if the Turing machine halts with Template:Mvar on its tape when given the input Template:Mvar.

The function Template:Mvar is called universal if for every computable function Template:Mvar of a single variable there is a string Template:Mvar such that for all Template:Mvar, Template:Math; here Template:Math represents the concatenation of the two strings Template:Mvar and Template:Mvar. This means that Template:Mvar can be used to simulate any computable function of one variable. Informally, Template:Mvar represents a "script" for the computable function Template:Mvar, and Template:Mvar represents an "interpreter" that parses the script as a prefix of its input and then executes it on the remainder of input.

The domain of Template:Mvar is the set of all inputs Template:Mvar on which it is defined. For Template:Mvar that are universal, such a Template:Mvar can generally be seen both as the concatenation of a program part and a data part, and as a single program for the function Template:Mvar.

The function Template:Mvar is called prefix-free if there are no two elements Template:Mvar, Template:Mvar in its domain such that Template:Mvar is a proper extension of Template:Mvar. This can be rephrased as: the domain of Template:Mvar is a prefix-free code (instantaneous code) on the set of finite binary strings. A simple way to enforce prefix-free-ness is to use machines whose means of input is a binary stream from which bits can be read one at a time. There is no end-of-stream marker; the end of input is determined by when the universal machine decides to stop reading more bits, and the remaining bits are not considered part of the accepted string. Here, the difference between the two notions of program mentioned in the last paragraph becomes clear: one is easily recognized by some grammar, while the other requires arbitrary computation to recognize.

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 Template:Math be the domain of a prefix-free universal computable function Template:Mvar. The constant Template:Math is then defined as

<math display="block">\Omega_F = \sum_{p \in P_F} 2^{-|p|},</math>

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

Relationship to the halting problem

Knowing the first Template:Mvar bits of Template:Math, one could calculate the halting problem for all programs of a size up to Template:Mvar. Let the program Template:Mvar for which the halting problem is to be solved be Template:Mvar 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 Template:Mvar bits. If the program Template:Mvar has not halted yet, then it never will, since its contribution to the halting probability would affect the first Template:Mvar bits. Thus, the halting problem would be solved for Template:Mvar.

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, calculating any but the first few bits of Chaitin's constant is not possible for a universal language. This 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 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 Template:Mvar the set of sequences that begin with Template:Mvar has measure Template:Math. This implies that for each natural number Template:Mvar, the set of sequences Template:Mvar in Cantor space such that Template:Math = 1 has measure Template:Sfrac, and the set of sequences whose Template:Mvarth element is 0 also has measure Template:Sfrac.

Let Template:Mvar be a prefix-free universal computable function. The domain Template:Mvar of Template:Mvar consists of an infinite set of binary strings

<math display="block">P = \{p_1,p_2,\ldots\}.</math>

Each of these strings Template:Math determines a subset Template:Math of Cantor space; the set Template:Math contains all sequences in cantor space that begin with Template:Math. These sets are disjoint because Template:Mvar is a prefix-free set. The sum

<math display="block">\sum_{p \in P} 2^{-|p|}</math>

represents the measure of the set

<math display="block">\bigcup_{i \in \mathbb{N}} S_i.</math>

In this way, Template:Math 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 Template:Mvar. It is for this reason that Template:Math is called a halting probability.

Properties

Each Chaitin constant Template:Math has the following properties:

• It is algorithmically random (also known as Martin-Löf random or 1-random).Template:Sfn This means that the shortest program to output the first Template:Mvar bits of Template:Math must be of size at least Template:Math. This is because, as in the Goldbach example, those Template:Mvar bits enable us to find out exactly which programs halt among all those of length at most Template:Mvar.
• 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 rational numbers Template:Mvar such that Template:Math is computably enumerable;Template:Sfn a real number with such a property is called a left-c.e. real number in recursion theory.
• The set of rational numbers Template:Mvar such that Template:Math is not computably enumerable. (Reason: every left-c.e. real with this property is computable, which Template:Math is not.)
• It is an arithmetical number.
• It is Turing equivalent to the halting problem and thus at level Template:Math 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.Template:Sfn One can show that a real number in Template:Math 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.Template:Sfn Template:Math 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.Template:Sfn

Uncomputability

A real number is called computable if there is an algorithm which, given Template:Mvar, returns the first Template:Mvar 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 Template:Mvar digits of Template:Math, solves Turing's halting problem for programs of length up to Template:Mvar. Since the halting problem is undecidable, Template:Math cannot be computed.

The algorithm proceeds as follows. Given the first Template:Mvar digits of Template:Math and a Template:Math, the algorithm enumerates the domain of Template:Mvar until enough elements of the domain have been found so that the probability they represent is within Template:Math of Template:Math. After this point, no additional program of length Template:Mvar can be in the domain, because each of these would add Template:Math to the measure, which is impossible. Thus the set of strings of length Template:Mvar 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<ref>Template:Cite conference</ref> that a recursively enumerable real number is an algorithmically random sequence if and only if it is a Chaitin's Template:Math number.

Incompleteness theorem for halting probabilities

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}}

For each specific consistent effectively represented axiomatic system for the natural numbers, such as Peano arithmetic, there exists a constant Template:Mvar such that no bit of Template:Math after the Template:Mvarth can be proven to be 1 or 0 within that system. The constant Template:Mvar 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.

Super Omega

The first Template:Mvar bits of Gregory Chaitin's constant Template:Math are random or incompressible in the sense that they cannot be computed by a halting algorithm with fewer than Template:Math 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 Template:Mvar 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 Template:Mvar bits of Template:Math. In other words, the enumerable first Template:Mvar bits of Template:Math 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 constructed a limit-computable "Super Template:Math" which in a sense is much more random than the original limit-computable Template:Math, as one cannot significantly compress the Super Template:Math by any enumerating non-halting algorithm.<ref>Template:Cite journal</ref>

For an alternative "Super Template:Math", the universality probability of a prefix-free universal Turing machine (UTM)Template:Snd namely, the probability that it remains universal even when every input of it (as a binary string) is prefixed by a random binary stringTemplate:Snd can be seen as the non-halting probability of a machine with oracle the third iteration of the halting problem (i.e., Template:Math using Turing jump notation).<ref>Template:Cite journal</ref>

See also

• Gödel's incompleteness theorems
• Kolmogorov complexity

References

<references />

Works cited

• Template:Cite book
• Template:Cite book
• Template:Cite book

External links

• Aspects of Chaitin's Omega Survey article discussing recent advances in the study of Chaitin's Template:Math.
• 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