info prev up next book cdrom email home

Halting Problem

The determination of whether a Turing Machine will come to a halt given a particular input program. This problem is formally Undecidable, as first proved by Turing.

See also Busy Beaver, Chaitin's Constant, Turing Machine, Undecidable


Chaitin, G. J. ``Computing the Busy Beaver Function.'' §4.4 in Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath). New York: Springer-Verlag, pp. 108-112, 1987.

Davis, M. ``What It a Computation.'' In Mathematics Today: Twelve Informal Essays (Ed. L. A. Steen). New York: Springer-Verlag, pp. 241-267, 1978.

Penrose, R. The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics. Oxford, England: Oxford University Press, pp. 63-66, 1989.

© 1996-9 Eric W. Weisstein