In the theory of computation
, a problem is said to be undecidable
if it is a yes/no problem with infinitely many instances, and no algorithm
exists that answers the problem for all instances correctly.
Alan Turing invented the Turing machine in order to prove the existence of undecidable problems; in particular, the undecideability of the halting problem, the question whether or not a given Turing machine will eventually halt its operation on a given input.
His work, published in 1936, is closely related to Kurt Gödel's earlier (1930) work on the incompleteness of mathematical logic.