> For the complete documentation index, see [llms.txt](https://mandober.gitbook.io/math-debrief/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mandober.gitbook.io/math-debrief/600-toc/630-computability-theory/halting-problem.md). # Halting problem In computability theory, the halting problem is about determining whether an arbitrary Turing machine halts on a given input. In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. In 1936, Alan Turing has proved that a general algorithm to solve the halting problem, for all possible program-input pairs, cannot exist. > The halting problem is *undecidable*. For any program `f` that might determine if programs halt or not, a deviously designed program `g`, invoked with some appropriate input, can pass its own source and its input to `f`, and then specifically do the opposite of what `f` predicts it will do. Therefore, there cannot exists a decider program `f` that can handle this case. A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; *the halting problem is undecidable over Turing machines*. Turing's proof is one of the first cases of *decision problems* to be closed. The theoretical conclusion that it is not solvable is significant to practical computing efforts, defining a class of applications which no programming invention can possibly perform perfectly.