Editing Church–Turing thesis (section)

=== Circa 1930–1952 ===
In the course of studying the problem, Church and his student [[Stephen Cole Kleene|Stephen Kleene]] introduced the notion of [[Lambda calculus|λ-definable functions]], and they were able to prove that several large classes of functions frequently encountered in number theory were λ-definable.<ref>Footnote 3 in {{harvnb|Church|1936a}} ''An Unsolvable Problem of Elementary Number Theory'', in {{harvcolnb|Davis|1965|page=89}}.</ref> The debate began when Church proposed to Gödel that one should define the "effectively computable" functions as the λ-definable functions. Gödel, however, was not convinced and called the proposal "thoroughly unsatisfactory".<ref>{{harvcolnb|Dawson|1997|page=99}}.</ref> Rather, in correspondence with Church (c. 1934–1935), Gödel proposed ''axiomatizing'' the notion of "effective calculability"; indeed, in a 1935 letter to Kleene, Church reported that:

{{Blockquote|His [Gödel's] only idea at the time was that it might be possible, in terms of effective calculability as an undefined notion, to state a set of axioms which would embody the generally accepted properties of this notion, and to do something on that basis.<ref name="sieg160"/>}}

But Gödel offered no further guidance. Eventually, he would suggest his recursion, modified by Herbrand's suggestion, that Gödel had detailed in his 1934 lectures in Princeton, New Jersey (Kleene and [[J. B. Rosser|Rosser]] transcribed the notes). But he did not think that the two ideas could be satisfactorily identified "except heuristically".<ref>{{harvcolnb|Sieg|1997|p=160}},{{missing long citation|date=March 2025}} quoting from the 1935 letter written by Church to Kleene, Footnote 3 in {{harvnb|Gödel|1934}} in {{harvcolnb|Davis|1965|page=44}}.</ref>

Next, it was necessary to identify and prove the equivalence of two notions of effective calculability. Equipped with the λ-calculus and "general" recursion, Kleene with help of Church and [[J. Barkley Rosser]] produced proofs (1933, 1935) to show that the two calculi are equivalent. Church subsequently modified his methods to include use of Herbrand–Gödel recursion and then proved (1936) that the {{lang|de|[[Entscheidungsproblem]]}} is unsolvable: there is no algorithm that can determine whether a [[well formed formula]] has a [[beta normal form]].<ref>{{harvnb|Church|1936}}{{ambiguous|date=March 2025}} in {{harvcolnb|Davis|1965|pages=105ff.}}</ref>

Many years later in a letter to Davis (c. 1965), Gödel said that "he was, at the time of these [1934] lectures, not at all convinced that his concept of recursion comprised all possible recursions".<ref>Davis's commentary before {{harvnb|Gödel|1934}} in {{harvcolnb|Davis|1965|page=40}}.</ref> By 1963–1964 Gödel would disavow Herbrand–Gödel recursion and the λ-calculus in favor of the Turing machine as the definition of "algorithm" or "mechanical procedure" or "formal system".<ref>For a detailed discussion of Gödel's adoption of Turing's machines as models of computation, see {{cite book |last=Shagrir |first=Oron |author-link=Oron Shagrir | title=Church's Thesis After 70 Years |chapter=Gödel on Turing on Computability |publisher=De Gruyter | date=2006-06-15 |pages=393–419 |isbn=978-3-11-032494-5 | doi=10.1515/9783110325461.393 |chapter-url=http://moon.cc.huji.ac.il/oron-shagrir/papers/Goedel_on_Turing_on_Computability.pdf |access-date=2016-02-08 |url-status=dead |archive-url=https://web.archive.org/web/20151217145831/http://moon.cc.huji.ac.il/oron-shagrir/papers/Goedel_on_Turing_on_Computability.pdf |archive-date=2015-12-17}}</ref>

'''A hypothesis leading to a natural law?''': In late 1936 [[Alan Turing]]'s paper (also proving that the {{lang|de|[[Entscheidungsproblem]]}} is unsolvable) was delivered orally, but had not yet appeared in print.<ref name="On Computable">{{Harvnb|Turing|1937a}}.</ref> On the other hand, [[Emil Post]]'s 1936 paper had appeared and was certified independent of Turing's work.<ref>Editor's footnote to Post 1936 ''Finite Combinatory Process. Formulation I.'' at {{harvcolnb|Davis|1965|page=289}}.</ref> Post strongly disagreed with Church's "identification" of effective computability with the λ-calculus and recursion, stating:

{{quote|Actually the work already done by Church and others carries this identification considerably beyond the working hypothesis stage. But to mask this identification under a definition&nbsp;... blinds us to the need of its continual verification.<ref>Post 1936 in {{harvcolnb|Davis|1965|page=291}}, footnote 8.</ref>}}

Rather, he regarded the notion of "effective calculability" as merely a "working hypothesis" that might lead by [[inductive reasoning]] to a "[[natural law]]" rather than by "a definition or an axiom".<ref>Post 1936 in {{harvcolnb|Davis|1952|p=291}}.</ref> This idea was "sharply" criticized by Church.<ref>{{harvcolnb|Sieg|1997|pp=171 and 176–177}}.{{missing long citation|date=March 2025}}</ref>

Thus Post in his 1936 paper was also discounting Gödel's suggestion to Church in 1934–1935 that the thesis might be expressed as an axiom or set of axioms.<ref name="sieg160">{{harvcolnb|Sieg|1997|p=160}}.{{missing long citation|date=March 2025}}</ref>

'''Turing adds another definition, Rosser equates all three''': Within just a short time, Turing's 1936–1937 paper "On Computable Numbers, with an Application to the {{lang|la|italic=no|Entscheidungsproblem}}"<ref name="On Computable"/> appeared. In it he stated another notion of "effective computability" with the introduction of his a-machines (now known as the [[Turing machine]] abstract computational model). In a proof-sketch added as an appendix to his 1936–1937 paper, Turing showed that the classes of functions defined by λ-calculus and Turing machines coincided.<ref>Turing 1936–1937 in {{harvcolnb|Davis|1965|pages=263ff.}}</ref> Church was quick to recognise how compelling Turing's analysis was. In his review of Turing's paper he made clear that Turing's notion made "the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately".<ref>{{harvnb|Church|1937}}.</ref>

In a few years (1939) Turing would propose, like Church and Kleene before him, that ''his'' formal definition of mechanical computing agent was the correct one.<ref>Turing 1939 in Davis:160.{{year needed|date=March 2025}}</ref> Thus, by 1939, both Church (1934) and Turing (1939) had individually proposed that their "formal systems" should be ''definitions'' of "effective calculability";<ref>Church 1934 in {{harvcolnb|Davis|1965|page=100}}, also Turing 1939 in {{harvcolnb|Davis|1965|page=160}}.</ref> neither framed their statements as ''theses''.

Rosser (1939) formally identified the three notions-as-definitions:

{{quote|All three ''definitions'' are equivalent, so it does not matter which one is used.<ref>Italics added, {{harvnb|Rosser|1939}} in {{harvcolnb|Davis|1965|page=226}}.</ref>}}

'''Kleene proposes ''Thesis I''''': This left the overt expression of a "thesis" to Kleene. In 1943 Kleene proposed his "Thesis I":<ref name="Davis274">{{harvnb|Kleene|1943|page=60}} in {{harvcolnb|Davis|1965|page=274}}. Footnotes omitted.</ref>

{{quote|This heuristic fact [general recursive functions are effectively calculable]&nbsp;... led Church to state the following thesis. The same thesis is implicit in Turing's description of computing machines.
{{quote|style=font-size:inherit;quotes:none;|Thesis I. ''Every effectively calculable function (effectively decidable predicate) is general recursive'' [Kleene's italics]}}
Since a precise mathematical definition of the term effectively calculable (effectively decidable) has been wanting, we can take this thesis&nbsp;... as a definition of it&nbsp;...}}
{{quote|...the thesis has the character of an hypothesis—a point emphasized by Post and by Church. If we consider the thesis and its converse as definition, then the hypothesis is an hypothesis about the application of the mathematical theory developed from the definition. For the acceptance of the hypothesis, there are, as we have suggested, quite compelling grounds.}}

'''The Church–Turing Thesis''': Stephen Kleene, in ''Introduction to Metamathematics'', finally goes on to formally name "Church's Thesis" and "Turing's Thesis", using his theory of recursive realizability, having switched from presenting his work in the terminology of Church–Kleene lambda definability to that of Gödel–Kleene recursiveness (partial recursive functions). In this transition, Kleene modified Gödel's general recursive functions to allow for proofs of the unsolvability of problems in the intuitionism of E. J. Brouwer. In his graduate textbook on logic, "Church's thesis" is introduced and basic mathematical results are demonstrated to be unrealizable. Next, Kleene proceeds to present "Turing's thesis", where results are shown to be uncomputable, using his simplified derivation of a Turing machine based on the work of Emil Post. Both theses are proven equivalent by use of "Theorem XXX".

{{quote|style=font-size:inherit;quotes:none|Thesis I. ''Every effectively calculable function (effectively decidable predicate) is general recursive''.<ref>{{harvcolnb|Kleene|1952|page=300}}.</ref>}}

{{quote|style=font-size:inherit;quotes:none|Theorem XXX: The following classes of partial functions are coextensive, i.e. have the same members: (a) the partial recursive functions, (b) the computable functions&nbsp;...<ref name="Kleene_1952_p376">{{harvcolnb|Kleene|1952|page=376}}.</ref>}}

{{quote|style=font-size:inherit;quotes:none|Turing's thesis: Turing's thesis that every function which would naturally be regarded as computable is computable under his definition, i.e. by one of his machines, is equivalent to Church's thesis by Theorem XXX.<ref name="Kleene_1952_p376"/>}}

Kleene, finally, uses for the first time the term the "Church-Turing thesis" in a section in which he helps to give clarifications to concepts in Alan Turing's paper "The Word Problem in Semi-Groups with Cancellation", as demanded in a critique from William Boone.<ref>{{harvcolnb|Kleene|1952|pages=382, 536}}</ref>