The halting problem is the decision problem of determining whether a specified program, running on a specified input, eventually stops or continues indefinitely. A foundational result in computer science establishes that no algorithm can always terminate and answer this question correctly for every possible program and input. The problem is therefore undecidable: its limitation concerns what can be computed in principle, rather than merely what can be computed efficiently. (courses.cs.cornell.edu)
Formal definition
The problem is commonly formulated using a Turing machine, an abstract computational device with a finite description and potentially unbounded working memory. Let (M) denote such a machine, (w) its input, and (\langle M,w\rangle) an effective encoding of both as a finite string. The halting language is
[ \mathrm{HALT}={\langle M,w\rangle\mid M\text{ halts on input }w}. ]
A decider would have to return “yes” for every member of this set and “no” for every nonmember, finishing after finitely many steps in either case. Halting includes both accepting and rejecting an input; it does not imply that the program produces a desired result. (cs.cornell.edu)
Programs can themselves be represented as data. A universal Turing machine can read an encoded machine and simulate its execution. This allows questions about program behavior to become ordinary computational inputs, including inputs that describe the program examining them. (cs.cornell.edu)
Historical background
Alan Turing established fundamental undecidability results in his 1936–1937 paper, On Computable Numbers, with an Application to the Entscheidungsproblem. He introduced his machine model, described universal simulation, and proved that certain questions about machines could not be decided mechanically. These results supplied a negative answer to the Entscheidungsproblem, the search for a general decision procedure for first-order logic. (cs.virginia.edu)
Historical terminology requires care. Turing’s original “circle-free” question concerned whether a machine produces infinitely many designated output symbols, not simply whether it stops. His paper also proved the undecidability of determining whether a machine ever prints a specified symbol. This latter problem yields the modern halting result: a simulator can print that symbol precisely when the simulated computation halts. Thus the modern theorem follows from his work, although today’s standard formulation and proof are not verbatim presentations of the original paper. (cs.virginia.edu)
Proof by diagonalization
The standard proof combines proof by contradiction with diagonalization, a technique related to Cantor’s diagonal argument. Suppose a program (H(P,x)) always finishes and correctly determines whether program (P) halts on input (x). Construct a second program (D), expressed in pseudocode:
D(p):
if H(p, p) says "halts":
loop forever
else:
halt
Now run (D) on its own description, (d). If (H(d,d)) predicts that this execution halts, (D) deliberately runs forever. If it predicts nontermination, (D) halts. Either answer is incorrect, contradicting the assumed correctness of (H). Consequently, no universal halting decider exists. (courses.cs.cornell.edu)
The argument does not require a program to discover its own source code automatically: its description is supplied as input. Nor does it prohibit deciding particular cases. It rules out a single procedure satisfying all three requirements—universal applicability, correctness, and guaranteed termination. (courses.cs.cornell.edu)
Recognizability and nontermination
Although undecidable, the halting problem is computably enumerable, also called recognizable or semidecidable. A recognizer simulates (M) on (w) and answers “yes” if the simulation stops. Every halting execution is eventually detected, but a nonhalting execution leaves the recognizer running indefinitely. This distinguishes recognition from decision. (cs.cornell.edu)
The complement, consisting of nonhalting machine–input pairs, is not recognizable. If both halting and nonhalting had recognizers, one could alternate their simulation steps until one accepted, thereby deciding the problem. This asymmetry does not prevent proofs of nontermination for individual programs; it prevents a recognizer that eventually confirms every nonhalting case without accepting any halting case. (cs.cornell.edu)
Reductions and related results
The theorem provides a starting point for computability theory. Through a computable reduction, instances of the halting problem are transformed into instances of another problem. If a decider for the latter would produce a halting decider, the latter must also be undecidable. The direction matters: the known undecidable problem is reduced to the problem under investigation. (cs.cornell.edu)
Rice’s theorem extends this limitation to every nontrivial property of the languages recognized by arbitrary Turing machines. Here “nontrivial” means that some recognized languages possess the property and others do not. It concerns semantic properties, not every property of a machine’s syntax or execution: inspecting its written description or simulating a fixed number of steps can be decidable. (cs.cornell.edu)
Scope and software analysis
The result applies to Turing-complete computational systems, including general-purpose programming languages interpreted with unbounded resources. It constrains formal verification and automatic program analysis: a termination analyzer for unrestricted programs cannot always finish with a correct definitive answer. Restricted analyses can instead leave some cases unresolved or use conservative approximations. (cs.cornell.edu)
Undecidability differs from computational complexity. An extremely slow decider would still be a decider; the halting theorem excludes every such algorithm. A bounded question—whether a program halts within a supplied number of steps—is decidable by finite simulation, but failure to halt within that bound does not establish that it will run forever. (courses.cs.cornell.edu)