Halting problem
https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Machine_that_always_halts
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.
Last updated