Halting 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. The problem is formally defined using a Turing machine as the model of computation, which includes all programs in Turing-equivalent languages. In this abstract framework, there are no limits on memory or execution time; a program may run arbitrarily long and consume arbitrarily large storage before halting. The proof demonstrates that for any program that might determine whether programs halt, a pathological program exists that passes its own source and input to that detector and does the opposite of what the detector predicts. This behavior shows undecidability, meaning no general algorithm can correctly solve the problem for all possible program–input pairs. The halting problem is decidable for linear bounded automata or deterministic machines with finite memory, because such a machine has finitely many possible configurations, so any deterministic program must eventually either halt or repeat a configuration. For nondeterministic finite memory machines, it is also decidable whether the machine halts on none, some, or all possible sequences of nondeterministic decisions. The problem is Turing equivalent to Davis's printing problem and to the printing problem considered in Turing's 1936 paper, though this equivalence does not mean the problems are identical.

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. The problem asks whether, given any program and input, a general algorithm can determine if the program will eventually halt or run forever. Alan Turing proved in 1937 that no such algorithm exists, using a proof that constructs a pathological program that passes its own source code to any candidate halting decider and does the opposite of what it predicts, forcing a contradiction. This result is often discussed in computability because it shows a limit on what can be computed. The formal statement relies on a mathematical model of computation, typically a Turing machine, with no limits on time or memory. Simple cases, like an infinite loop versus a program that prints a message, are easy to decide, but complex programs are not. The term "halting problem" did not appear in Turing's original 1936 paper; it was introduced later, with Martin Davis using it in his 1958 book and stating he had referred to it since 1952. The problem is Turing equivalent to Davis's printing problem and to the printing problem in Turing's 1936 paper, though equivalence does not mean the problems are identical.

Did You Know?

• The halting problem is decidable for linear bounded automata.
• The problem shows some functions are definable but not computable.