Chaitin's Constant

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 that is optimal: simulation of any other prefix-free Turing machine increases program length by at most a constant independent of the program. 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 noncomputable (Chaitin 1975).

A Chaitin 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 noncomputable numbers. They are also known to be transcendental.

For the register machine and its canonical compressed encoding defined by Calude et al. (2002, §5), let count the halting programs of total length bits, including both program and data encoded in 7-bit characters. Programs with run-time errors are excluded. The initial counts, starting at , are 1, 1, 3, 8, 50, 311, 1012, 4382, 19164, 99785, 515279, 2559837, ... (OEIS A400878; Calude et al. 2002, Table 1). These counts are specific to this machine and encoding.

Each data bit occupies a 7-bit character in this encoding, so the simulation overhead is not the constant additive overhead required above. The following value is the halting probability of this encoding and must be distinguished from a Chaitin omega number.

Grouping the halting programs by total length gives the weighted sum

(2)

The sum through is a lower bound for . Calude et al. (2002, §7) bounded the contribution of longer programs to establish the first 64 bits of , whose binary expansion and decimal expansion begin

			(3)
			(4)

(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

			(5)
			(6)

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