In thecomputer science subfield ofalgorithmic information theory, aChaitin constant (Chaitin omega number)^[1] orhalting probability is areal number that, informally speaking, represents theprobability that a randomly constructed program will halt. These numbers are formed from a construction due toGregory 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 calledChaitin's construction when not referring to any specific encoding.

Each halting probability is anormal andtranscendental real number that is notcomputable, which means that there is noalgorithm to compute its digits. Each halting probability isMartin-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. 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 thatF is apartial function that takes one argument, a finite binary string, and possibly returns a single binary string as output. The functionF is calledcomputable if there is aTuring machine that computes it, in the sense that for any finite binary stringsx andy,F(x) =y if and only if the Turing machine halts withy on its tape when given the inputx.

The functionF is calleduniversal if for every computable functionf of a single variable there is a stringw such that for allx,F(w x) =f(x); herew x represents theconcatenation of the two stringsw andx. This means thatF can be used to simulate any computable function of one variable. Informally,w represents a "script" for the computable functionf, andF represents an "interpreter" that parses the script as a prefix of its input and then executes it on the remainder of input.

Thedomain ofF is the set of all inputsp on which it is defined. ForF that are universal, such ap can generally be seen both as the concatenation of a program part and a data part, and as a single program for the functionF.

The functionF is called prefix-free if there are no two elementsp,p′ in its domain such thatp′ is a proper extension ofp. This can be rephrased as: the domain ofF is aprefix-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 acomputably enumerable set but never acomputable set. The domain is alwaysTuring equivalent to thehalting problem.

LetP_F be the domain of a prefix-free universal computable functionF. The constantΩ_F is then defined as

$${\displaystyle {\mathrm{\Omega }}_F=\sum _{p\in P_F}{2}^{-|p|},}$$

where|p| denotes the length of a stringp. This is aninfinite sum which has one summand for everyp in the domain ofF. The requirement that the domain be prefix-free, together withKraft's inequality, ensures that this sum converges to areal number between 0 and 1. IfF is clear from context thenΩ_F may be denoted simplyΩ, although different prefix-free universal computable functions lead to different values ofΩ.

Knowing the firstN bits ofΩ, one could calculate thehalting problem for all programs of a size up toN. Let the programp for which the halting problem is to be solved beN bits long. Indovetailing fashion, all programs of all lengths are run, until enough have halted to jointly contribute enough probability to match these firstN bits. If the programp has not halted yet, then it never will, since its contribution to the halting probability would affect the firstN bits. Thus, the halting problem would be solved forp.

Because many outstanding problems in number theory, such asGoldbach'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 anoracle machine for the halting problem would be.

TheCantor space is the collection of all infinite sequences of 0s and 1s. A halting probability can be interpreted as themeasure of a certain subset of Cantor space under the usualprobability 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 stringx the set of sequences that begin withx has measure2^−|x|. This implies that for each natural numbern, the set of sequencesf in Cantor space such thatf(n) = 1 has measure⁠1/2⁠, and the set of sequences whosenth element is 0 also has measure⁠1/2⁠.

LetF be a prefix-free universal computable function. The domainP ofF consists of an infinite set of binary strings

$${\displaystyle P=\{p_1,p_2,\dots \}.}$$

Each of these stringsp_i determines a subsetS_i of Cantor space; the setS_i contains all sequences in cantor space that begin withp_i. These sets are disjoint becauseP is a prefix-free set. The sum

$${\displaystyle \sum _{p\in P}{2}^{-|p|}}$$

represents the measure of the set

$${\displaystyle \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 ofF. It is for this reason thatΩ_F is called a halting probability.

Each Chaitin constantΩ has the following properties:

• It isalgorithmically random (also known as Martin-Löf random or 1-random).^[2] This means that the shortest program to output the firstn bits ofΩ must be of size at leastn − O(1). This is because, as in the Goldbach example, thosen bits enable us to find out exactly which programs halt among all those of length at mostn.
• As a consequence, it is anormal number, which means that its digits are equidistributed as if they were generated by tossing a fair coin.
• It is not acomputable number; there is no computable function that enumerates its binary expansion, as discussed below.
• The set ofrational numbersq such thatq < Ω iscomputably enumerable;^[3] a real number with such a property is called a left-c.e. real number inrecursion theory.
• The set of rational numbersq such thatq > Ω is not computably enumerable. (Reason: every left-c.e. real with this property is computable, whichΩ is not.)
• It is anarithmetical number.
• It isTuring equivalent to thehalting problem and thus at levelΔ 0
  2  of thearithmetical hierarchy.

Not every set that is Turing equivalent to the halting problem is a halting probability. Afiner 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 fewdefinable algorithmically random numbers and is the best-known algorithmically random number, but it is not at all typical of all algorithmically random numbers.^[5]

A real number is called computable if there is an algorithm which, givenn, returns the firstn 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 firstn digits ofΩ, solves Turing'shalting problem for programs of length up ton. Since the halting problem isundecidable,Ω cannot be computed.

The algorithm proceeds as follows. Given the firstn digits ofΩ and ak ≤n, the algorithm enumerates the domain ofF until enough elements of the domain have been found so that the probability they represent is within2^−(k+1) ofΩ. After this point, no additional program of lengthk can be in the domain, because each of these would add2^−k to the measure, which is impossible. Thus the set of strings of lengthk in the domain is exactly the set of such strings already enumerated.

A real number is random if the binary sequence representing the real number is analgorithmically 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.

For each specific consistent effectively representedaxiomatic system for thenatural numbers, such asPeano arithmetic, there exists a constantN such that no bit ofΩ after theNth can be proven to be 1 or 0 within that system. The constantN depends on how theformal system is effectively represented, and thus does not directly reflect the complexity of the axiomatic system. This incompleteness result is similar toGödel's incompleteness theorem in that it shows that no consistent formal theory for arithmetic can be complete.

The firstn bits ofGregory Chaitin's constantΩ are random or incompressible in the sense that they cannot be computed by a halting algorithm with fewer thann − 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 firstn 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 firstn bits ofΩ. In other words, theenumerable firstn bits ofΩ are highly compressible in the sense that they arelimit-computable by a very short algorithm; they are notrandom with respect to the set of enumerating algorithms.Jürgen Schmidhuber constructed a limit-computable "SuperΩ" which in a sense is much more random than the original limit-computableΩ, as one cannot significantly compress the SuperΩ by any enumerating non-halting algorithm.^[7]

For an alternative "SuperΩ", theuniversality probability of aprefix-freeuniversal Turing machine (UTM) – namely, the probability that it remains universal even when every input of it (as abinary 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 thehalting problem (i.e.,O⁽³⁾ usingTuring jump notation).^[8]

• Gödel's incompleteness theorems
• Kolmogorov complexity

• 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.
• Li, Ming; Vitányi, Paul (1997).An Introduction to Kolmogorov Complexity and Its Applications. Springer.

• Aspects of Chaitin's Omega Survey article discussing recent advances in the study of Chaitin'sΩ.
• Omega and why maths has no TOEs article based on one written byGregory Chaitin which appeared in the August 2004 edition ofMathematics Today, on the occasion of the 50th anniversary of Alan Turing's death.
• The Limits of Reason, Gregory Chaitin, originally appeared inScientific American, March 2006.
• Limit-computable Super Omega more random than Omega and generalizations of algorithmic information, byJürgen Schmidhuber

• Algorithmic information theory
• Theory of computation
• Real transcendental numbers

• Articles with short description
• Short description is different from Wikidata
• Use dmy dates from December 2020