The determination of whether a Turing machine will come to a halt given a particular input program. The halting problem is solvable for machines with less than four states. However, the four-state case is open, and the five-state case is almost certainly unsolvable due to the fact that it includes machines iterating Collatz-like congruential functions, and such specific problems are currently open. The problem of whether a general Turing machine halts is undecidable, as first proved by Turing (Wolfram 2002, pp. 1136-1138).
Halting Problem
See also
Busy Beaver, Chaitin's Constant, Turing Machine, UndecidableExplore with Wolfram|Alpha
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 Is 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.Turing, A. M. "On Computable Numbers, with an Application to the Entscheidungsproblem." Proc. London Math. Soc. Ser. 2 42, 230-265, 1937. Reprinted in The Undecidable (Ed. M. David). Hewlett, NY: Raven Press, 1965.Turing, A. M. "Correction to: On Computable Numbers, with an Application to the Entscheidungsproblem." Proc. London Math. Soc. Ser. 2 43, 544-546, 1938.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 1136-1138, 2002.Cite this as:
Weisstein, Eric W. "Halting Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HaltingProblem.html