The halting problem is the determination of whether a Turing machine will come to a halt given a particular input program. It 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 because it includes machines iterating congruential functions like the one in the Collatz conjecture, 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.Veritasium. "The Simplest Math Problem No One Can Solve-Collatz Conjecture." Jul. 30, 2021. https://www.youtube.com/watch?v=094y1Z2wpJg.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 1136-1138, 2002.Referenced on Wolfram|Alpha
Halting ProblemCite this as:
Weisstein, Eric W. "Halting Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HaltingProblem.html