Chaitin's Constant

Chaitin's constant, also called a Chaitin omega number, introduced by Chaitin (1975), is the halting probability of a prefix-free (self-delimiting) universal 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 algorithmically random sequence), hence noncomputable (Chaitin 1975).

A Chaitin constant can therefore be defined as

(1)

which gives the probability that a stream of independent fair random bits begins with a halting program for , where is the length in bits of program .

The value of a Chaitin constant is highly machine-dependent. Solovay (2000, p. 323) constructed an optimal prefix-free universal Turing machine for which ZFC, assuming it is arithmetically sound, cannot prove the value of any individual bit of its halting probability. Arithmetic soundness means that every arithmetical statement proved by the theory is true.

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.

This encoding uses an alphabet of 49 characters, each occupying 7 bits, including each data bit. The encoded machine does not satisfy the constant additive program-length overhead required above. Denote its halting probability by .

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 the halting probabilities for two data encodings of a prefix-free Turing machine that is optimal in program length, using 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.