# 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. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://mandober.gitbook.io/math-debrief/600-toc/630-computability-theory/halting-problem.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.