Kurt Gödel’s Incompleteness Theorem was inspired by David Hilbert’s question “Are the axioms of a formal system sufficient to derive every statement that is true in all models of the system?” Hilbert played the same role regarding Alan Turing’s proof of the halting problem. Hilbert had asked: “Is there some mechanical procedure [an algorithm] for answering all mathematical problems, belonging to some broad, but well-defined class?” In German this is called Entscheidungsproblem – the decision problem.
Turing found that he could answer this question by framing it in terms of a Turing machine – could there be a program that could determine whether any other arbitrary computer program and input would eventually stop or just loop forever? This was called the halting problem.
“Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.”