# Chaitin's constant

In the computer science subfield of algorithmic information theory the**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 Ω.

It is a normal and transcendental number which can be defined but cannot be computed. This means one can prove that there is no algorithm which produces the digits of Ω

As Ω depends on the program encoding used it should be called **Chaitin construction** instead of **Chaitin constant** when not referring to any specific encoding.

## Definition

To define Ω formally, we first need to fix a (Turing-complete) model of computation, for instance Turing machines or Lisp or Pascal programs. We then need to specify an unambiguous encoding of programs (or machines) as bit strings. This encoding must have the property that if *w* encodes a syntactically correct program, then no proper prefix of *w* encodes a syntactically correct program. This can always be achieved by using a special end symbol. We only consider programs that don't require any input.

Let *P* be the set of all programs which halt. Ω is then defined as:

*p*| stands for the length of the bit string of

*p*. The above requirement that programs be prefix-free ensures that this sum converges to a real number between 0 and 1.

## Notes

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 digit 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.