The halting problem
Is there an algorithm that, given the code of any program and an input, correctly decides whether the program eventually halts on that input? Prove your answer.
History and references
Solved in 1936 by Alan Turing.
Hilbert's Entscheidungsproblem, formulated in 1928, asked for a mechanical procedure to decide statements of first-order logic. In 1936 Alonzo Church and Alan Turing independently showed that no such procedure exists, and Turing's paper On Computable Numbers, received in May 1936 and published in early 1937, introduced what are now called Turing machines. The modern halting argument is a diagonalization. If a decider existed, one could write a program that runs on its own code and then does the opposite of what predicts, which is a contradiction. Turing never used the words halt or halting, and the name halting problem was introduced by Martin Davis in the 1950s. It is the basic example of an undecidable problem, and many others are proved undecidable by reducing it to them.
References
Solutions 0
Sign in or create an account to publish a solution