TOPICS
Search

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

 Omega_U=sum_(p halts)2^(-|p|)
(1)

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

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 Omega_U 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 Omega_U for a certain universal Turing machine as

Omega_U=0.0000001000000100000110..._2
(2)
=0.00787499699...
(3)

(OEIS A079365 and A100264).

Medallion presented to Gregory Chaitin for his 60th birthday by Stephen Wolfram

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

Omega_(U2)=0.0001000000010000101001110111000011111010..._2
(4)
Omega_(U16)=0.0001000000010000101001110111000100000101110..._2.
(5)

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


See also

Computable Number, Halting Problem, Turing Machine, Universal Turing Machine

Explore with Wolfram|Alpha

References

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, p. 145, 2003.Calude, C. S.; Dinneen, M. J.; and Shu, C.-K. "Computing a Glimpse of Randomness." Exper. Math. 11, 361-370, 2002.Calude, C. S. and Dinneen, M. J. "Exact Approximations of Omega Numbers." Int. J. Bifur. Chaos 17, 1937-1954, 2007.Chaitin, G. J. "A Theory of Program Size Formally Identical to Information Theory." J. Assoc. Comput. Mach. 22, 329-340, 1975.Chaitin, G. J. "How Much Information Can There be in a Real Number?" Int. J. Bifur. Chaos 17, 1933-1935, 2007.Chaitin, G. Meta Math!:The Quest for Omega. New York: Pantheon Books, 2005.Finch, S. R. "Chaitin's Constant." §1.11 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 81-83, 2003.Gardner, M. "The Random Number Omega Bids Fair to Hold the Mysteries of the Universe." Sci. Amer. 241, 20-34, Nov. 1979.Gardner, M. "Chaitin's Omega." Ch. 21 in Fractal Music, Hypercards, and More Mathematical Recreations from Scientific American Magazine. New York: W. H. Freeman, pp. 307-319, 1992.Kobayashi, K. "Sigma(N)O-Complete Properties of Programs and Lartin-Lof Randomness." Information Proc. Let. 46, 37-42, 1993.Sloane, N. J. A. Sequences A079365 and A100264 in "The On-Line Encyclopedia of Integer Sequences."Solovay, R. M. "A Version of Omega for Which ZFC Cannot Predict a Single Bit." In Finite Versus Infinite. Contributions to an Eternal Dilemma (Ed. C. Calude and G. Păun). London: Springer-Verlag, pp. 323-334, 2000.

Referenced on Wolfram|Alpha

Chaitin's Constant

Cite this as:

Weisstein, Eric W. "Chaitin's Constant." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ChaitinsConstant.html

Subject classifications