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.