Halting Problem

The halting problem asks whether it is possible to write a single general algorithm that, given the description of any computer program together with a specific input, can always correctly determine whether that program will eventually finish running, or halt, or will instead continue running forever. British mathematician Alan Turing proved in a 1936 paper, introducing what is now called the Turing machine as a formal model of computation, that no such general algorithm can exist: the halting problem is undecidable for the class of all possible program-input pairs. Turing's proof works by a diagonalization argument, similar in structure to the one Georg Cantor used to show some infinities are larger than others, showing that assuming a halting-decider program exists leads directly to a logical contradiction. The result is foundational to the theory of computability, establishing that there are precisely defined problems no computer program can ever solve in general, regardless of how much computing power or time is available, a limit inherent to the nature of computation itself rather than a limitation of any particular machine or programming language.