Halting problem
No algorithm can decide if any program halts.
The halting problem is a decision problem in computability theory: given an arbitrary computer program and an input, determine whether the program will eventually halt or run forever.
- field
- Computability theory
- known_for
- Undecidability of the halting problem
- proved_by
- Alan Turing
- type
- Decision problem
Lore & Background
The halting problem asks whether a given program, run with a particular input, will eventually finish or loop forever. Simple cases, like a program that prints 'Hello, world!' and halts, are easy to decide, but Turing showed that no single algorithm works for all cases. His proof constructs a 'pathological' program that uses any candidate halting detector to produce a contradiction.
Reader's Guide
The halting problem is central to computability theory because it demonstrates that some mathematically definable functions are not computable. Its undecidability has practical consequences: in hard real-time computing, programmers use restricted languages like MISRA C, SPARK, and Rocq to ensure subroutines finish before deadlines. The problem is decidable for finite-memory machines such as linear bounded automata, though the number of possible states can be astronomically large.
Did You Know?
- The halting problem is decidable for linear bounded automata.
- The problem shows some functions are definable but not computable.
More in Mathematical Logic And Computation 1-21
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record