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.
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.
Each halting probability is Martin-Löf random, meaning there is not even any algorithm which can reliably guess its digits.
The definition of a halting probability relies on the existence of a prefix-free universal computable function.
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.
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 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.
Let PF be the domain of a prefix-free universal computable function F. The constant ΩF is then defined as
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 be prefix-free, together with Kraft's inequality, ensures that this sum converges to a real number between 0 and 1.
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.
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 for a universal language.
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.
[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.
This is equivalent to the existence of a program that enumerates the digits of the real number.
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.
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.
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 1 or 0 within that system.
So there is a short non-halting algorithm whose output converges (after finite time) onto the first n bits of Ω.
[7] For an alternative "Super Ω", the universality probability of a prefix-free universal Turing machine (UTM) – namely, the probability that it remains universal even when every input of it (as a binary string) is prefixed by a random binary string – can be seen as the non-halting probability of a machine with oracle the third iteration of the halting problem (i.e., O(3) using Turing jump notation).