halting

Halting refers to termination of a computational process. In programming, a program halts when it finishes executing and outputs a result or ends in a final state. Halting is distinct from simply running: a program may run indefinitely if it loops.

The halting problem asks: given a description of a program and an input, will the program eventually halt on that input? Introduced by Alan Turing in 1936 as part of the Entscheidungsproblem. He showed that a general algorithm to solve this problem for all program-input pairs cannot exist for Turing machines.

The result is a fundamental limitation on formal reasoning about algorithms. The halting problem is recursively enumerable (semi-decidable): there is an algorithm that halts on inputs where the program halts and reports yes, but no algorithm can correctly decide for all inputs that do halt or do not halt. The classical proof uses diagonalization and self-reference, constructing a machine that leads to a contradiction with a supposed halting-decider.

Variants and related ideas. In restricted models or with additional information, the problem can be decidable: for instance, finite automata always halt on a given input, or programs with known bounds. In practice, termination analysis and static analysis aim to reason about whether code terminates for all inputs or under certain conditions. The halting problem is closely linked to concepts of computability, decidability, and recognizability.