The halting problem is a decision problem in computability theory that asks whether a given program, when executed with a particular input, will eventually stop running (halt) or continue to execute indefinitely. Formally, the problem can be expressed as: given a description of a Turing machine $M$ and an input string $w$, determine whether $M$ halts when started on $w$.
Historical background
The problem was first articulated by Alan Turing in his 1936 paper “On Computable Numbers, with an Application to the Entscheidungsproblem.” Turing proved that a general algorithm for solving the halting problem cannot exist. This result established the existence of undecidable problems—problems for which no algorithm can provide a correct yes‑or‑no answer for all possible inputs.
Proof of undecidability
Turing’s proof proceeds by contradiction. Assuming the existence of a hypothetical universal halting decider $H$ that correctly returns “yes” if a program halts on an input and “no” otherwise, one can construct a new program $D$ that uses $H$ to produce a paradoxical behavior: $D$ takes its own code as input and halts if and only if $H$ predicts that $D$ does not halt. This leads to a logical contradiction, demonstrating that $H$ cannot exist.
Significance and implications
- Foundational impact – The undecidability of the halting problem is a cornerstone of theoretical computer science, illustrating intrinsic limits on what can be computed.
- Complexity theory – The halting problem is complete for the class of recursively enumerable (r.e.) sets under many‑one reducibility, making it a canonical r.e.-complete problem.
- Program analysis – Practical static analysis tools can often determine termination for restricted subsets of programs, but the general problem remains unsolvable.
- Related results – Variants such as the partial halting problem (determining whether a machine halts on at least one input) and the uniform halting problem (deciding halting for all inputs) are likewise undecidable.
Formal definition
Let $\Sigma$ be a finite alphabet and let $\langle M, w\rangle$ denote an encoding of a Turing machine $M$ and an input string $w$. Define the language
$$ \text{HALT} = {,\langle M, w\rangle \mid M \text{ halts on input } w ,}. $$
$\text{HALT}$ is recursively enumerable but not recursive; that is, there exists a Turing machine that enumerates all members of $\text{HALT}$, but no Turing machine decides membership for every possible $\langle M, w\rangle$.
Limitations
The undecidability result applies to any computational model that is at least as powerful as a Turing machine (e.g., modern programming languages, lambda calculus). It does not preclude the existence of decidable halting criteria for specific, constrained languages or program fragments.
See also
- Decidability
- Recursive enumerability
- Rice’s theorem
- Gödel’s incompleteness theorems
- Computational complexity classes (e.g., $ \mathsf{RE}$, $ \mathsf{coRE}$)
References
- A. M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, vol. 2, pp. 230–265, 1936.
- M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2012.
- H. Rogers, Theory of Recursive Functions and Effective Computability, MIT Press, 1987.