TOPICS
Halting Problem
The halting problem is the problem of determining whether a given program eventually halts on a given input. For Turing machines, it is recursively undecidable. No algorithm correctly answers this question for every program and input (Turing 1937; Wolfram 2002, pp. 1136-1138).
The absence of a general algorithm does not prevent resolving particular finite collections of programs.
For example, Calude et al. (2002, pp. 366-367) determined which compressed
programs halt for a particular register
machine with total program and data length at most
84 bits. The counts at lengths 
bits, starting at 
, are 1, 1, 3, 8, 50, 311, ... (OEIS A400878;
Calude et al. 2002, p. 367). The machine's encoding
and treatment of run-time errors are part of the specification. The corresponding
weighted sum gives its halting
probability, a Chaitin's constant.
See also
Busy Beaver, Chaitin's Constant, Halting Probability, Recursively Undecidable, Register Machine, Turing MachineExplore with Wolfram|Alpha
References
Calude, C. S.; Dinneen, M. J.; and Shu, C.-K. "Computing a Glimpse of Randomness." Exper. Math. 11, 361-370, 2002. https://doi.org/10.1080/10586458.2002.10504481.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.Sloane, N. J. A. Sequence A400878 in "The On-Line Encyclopedia of Integer Sequences."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: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions (Ed. M. Davis). Hewlett, NY: Raven Press, pp. 116-151, 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