info prev up next book cdrom email home

Chaitin's Constant

An Irrational Number $\Omega$ which gives the probability that for any set of instructions, a Universal Turing Machine will halt. The digits in $\Omega$ are random and cannot be computed ahead of time.

See also Halting Problem, Turing Machine, Universal Turing Machine


References

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/chaitin/chaitin.html

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, 1992.

Kobayashi, K. ``Sigma(N)O-Complete Properties of Programs and Lartin-Lof Randomness.'' Information Proc. Let. 46, 37-42, 1993.




© 1996-9 Eric W. Weisstein
1999-05-26