History of the Church–Turing thesis

The history of the Church–Turing thesis ("thesis") involves the history of the development of the study of the nature of functions whose values are effectively calculable; or, in more modern terms, functions whose values are algorithmically computable. It is an important topic in modern mathematical theory and computer science, particularly associated with the work of Alonzo Church and Alan Turing.

The debate and discovery of the meaning of "computation" and "recursion" has been long and contentious. This article provides detail of that debate and discovery from Peano's axioms in 1889 through recent discussion of the meaning of "axiom".

In 1889, Giuseppe Peano presented his The principles of arithmetic, presented by a new method, based on the work of Dedekind. Soare proposes that the origination of "primitive recursion" began formally with the axioms of Peano, although

Observe that in fact Peano's axioms are 9 in number and axiom 9 is the recursion/induction axiom.

At the International Congress of Mathematicians (ICM) in 1900 in Paris the famous mathematician David Hilbert posed a set of problems – now known as Hilbert's problems – his beacon illuminating the way for mathematicians of the twentieth century. Hilbert's 2nd and 10th problems introduced the Entscheidungsproblem (the "decision problem"). In his 2nd problem he asked for a proof that “arithmetic” is “consistent”. Kurt Gödel would prove in 1931 that, within what he called “P” (nowadays called Peano Arithmetic), “there exist undecidable sentences [propositions]”. Because of this, “the consistency of P is unprovable in P, provided P is consistent”. While Gödel’s proof would display the tools necessary for Alonzo Church and Alan Turing to resolve the Entscheidungsproblem, he himself would not answer it.

...
Wikipedia