Chaitin's Constant

A Chaitin's constant, also called a Chaitin omega number, introduced by Chaitin (1975), is the halting probability of a universal prefix-free (self-delimiting) Turing machine. Every Chaitin constant is simultaneously computably enumerable (the limit of a computable, increasing, converging sequence of rationals), and algorithmically random (its binary expansion is an algorithmic random sequence), hence uncomputable (Chaitin 1975).

A Chaitin's constant can therefore be defined as

(1)

which gives the probability that for any set of instructions, a particular prefix-free universal Turing machine will halt, where is the size in bits of program .

The value of a Chaitin constant is highly machine-dependent. In some cases, it can even be proved that not a single bit can be computed (Solovay 2000).

Chaitin constants are perhaps the most obvious specific example of uncomputable numbers. They are also known to be transcendental.

Calude et al. (2002) computed the first 64 bits of Chaitin's constant for a certain universal Turing machine as

			(2)
			(3)

(OEIS A079365 and A100264).

Calude and Dinneen (2007) subsequently computed the first 43 and 40 bits of another prefix-free Turing machine which is universal when used with data in base 16 and 2, respectively, as

			(4)
			(5)

The binary result is engraved on the medallion presented to Gregory Chaitin for his 60th birthday by Stephen Wolfram, illustrated above.