|
|
|
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
References
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.