View source for Church–Turing thesis

{{Short description|Thesis on the nature of computability}}
{{Redirect|Church's thesis|the axiom CT in constructive mathematics|Church's thesis (constructive mathematics)}}
{{Use dmy dates|date=August 2022|cs1-dates=y}}
In [[Computability theory (computation)|computability theory]], the '''Church–Turing thesis''' (also known as '''computability thesis''',<ref>[[Robert Soare]], [http://www.people.cs.uchicago.edu/~soare/History/turing.pdf "Turing Oracle Machines, Online Computing, and Three Displacements in Computability Theory"]</ref> the  '''Turing–Church thesis''',<ref>{{cite video |author-last=Rabin |author-first=Michael O. |author-link=Michael O. Rabin |title=Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View |date=June 2012 |url=http://videolectures.net/turing100_rabin_turing_church_goedel/ |access-date=2021-12-05 |time=9:36 }}<!-- backup urls: YouTube https://www.youtube.com/watch?v=ofyXXOpRB0U Slides https://www.bu.edu/cphs/files/2013/08/Rabin.pdf --></ref> the '''Church–Turing conjecture''', '''Church's thesis''', '''Church's conjecture''', and '''Turing's thesis''') is a [[wiktionary:thesis|thesis]] about the nature of [[computable function]]s. It states that a [[function (mathematics)|function]] on the [[natural numbers]] can be calculated by an [[effective method]] if and only if it is computable by a [[Turing machine]]. The thesis is named after American mathematician [[Alonzo Church]] and the British mathematician [[Alan Turing]]. Before the precise definition of computable function, mathematicians often used the informal term [[effectively calculable]] to describe functions that are computable by paper-and-pencil methods. In the 1930s, several independent attempts were made to [[formal system|formalize]] the notion of [[computability]]:
* In 1933, [[Kurt Gödel]], with [[Jacques Herbrand]], formalized the definition of the class of [[general recursive function]]s: the smallest class of functions (with arbitrarily many arguments) that is closed under [[function composition|composition]], [[recursion]], and [[μ operator|minimization]], and includes [[zero function|zero]], [[successor function|successor]], and all [[projection function|projections]].
* In 1936, [[Alonzo Church]] created a method for defining functions called the [[Lambda calculus|λ-calculus]]. Within λ-calculus, he defined an encoding of the natural numbers called the [[Church numerals]]. A function on the natural numbers is called [[Lambda-recursive function|λ-computable]] if the corresponding function on the Church numerals can be represented by a term of the λ-calculus.
* Also in 1936, before learning of Church's work,{{r|TuringLearn|r=Church's paper was presented to the American Mathematical Society on 19 April 1935 and published on 15 April 1936. Turing, who had made substantial progress in writing up his own results, was disappointed to learn of Church's proof upon its publication.{{r|TuringNewman|r=Correspondence between [[Max Newman]] and Church in [https://findingaids.princeton.edu/collections/C0948/c00385 Alonzo Church papers]}}{{r|EssentialTuring|r={{cite book |last1=Turing |first1=Alan |title=The essential Turing : seminal writings in computing, logic, philosophy, artificial intelligence, and artificial life, plus the secrets of Enigma |date=2004 |publisher=Clarendon Press |location=Oxford |isbn=9780198250791 |page=44 |url=http://www.cse.chalmers.se/~aikmitr/papers/Turing.pdf |access-date=6 December 2021}}}} Turing quickly completed his paper and rushed it to publication; it was received by the ''Proceedings of the London Mathematical Society'' on 28 May 1936, read on 12 November 1936, and published in series 2, volume 42 (1936–1937); it appeared in two sections: in Part 3 (pages 230–240), issued on 30 November 1936 and in Part 4 (pages 241–265), issued on 23 December 1936; Turing added corrections in volume 43 (1937), pp. 544–546.{{r|name=Soare|page=45}}}} [[Alan Turing]] created a theoretical model for machines, now called Turing machines, that could carry out calculations from inputs by manipulating symbols on a tape. Given a suitable encoding of the natural numbers as sequences of symbols, a function on the natural numbers is called [[computable function|Turing computable]] if some Turing machine computes the corresponding function on encoded natural numbers.
Church,<ref>{{harvnb|Church|1936a }}</ref> [[Stephen Cole Kleene|Kleene]],<ref>{{harvnb|Kleene|1936 }}</ref> and Turing<ref>{{harvnb|Turing|1937a}}</ref>{{#tag:ref|{{harvnb|Turing|1937b}}. Proof outline on p.&nbsp;153: <math>\lambda\mbox{-definable}</math> <math>\stackrel{triv}{\implies}</math> <math>\lambda\mbox{-}K\mbox{-definable}</math> <math>\stackrel{160}{\implies}</math> <math>\mbox{Turing computable}</math> <math>\stackrel{161}{\implies}</math> <math>\mu\mbox{-recursive}</math> <math>\stackrel{Kleene}{\implies}</math><ref>{{harvnb|Kleene|1936}}</ref> <math>\lambda\mbox{-definable}</math>}} proved that these three formally defined classes of computable functions coincide: a function is λ-computable if and only if it is Turing computable, and if and only if it is ''general recursive''. This has led mathematicians and computer scientists to believe that the concept of computability is accurately characterized by these three equivalent processes. Other formal attempts to characterize computability have subsequently strengthened this belief (see [[#Success of the thesis|below]]).
On the other hand, the Church–Turing thesis states that the above three formally-defined classes of computable functions coincide with the ''informal'' notion of an effectively calculable function. Although the thesis has near-universal acceptance, it cannot be formally proven, as the concept of effective calculability is only informally defined.
Since its inception, variations on the original thesis have arisen, including statements about what can physically be realized by a computer in our universe ([[physical Church-Turing thesis]]) and what can be efficiently computed ([[#complexity-theoretic Church–Turing thesis|Church–Turing thesis (complexity theory)]]). These variations are not due to Church or Turing, but arise from later work in [[Computational complexity theory|complexity theory]] and [[digital physics]]. The thesis also has implications for the [[philosophy of mind]] (see [[#Philosophical implications|below]]).
==Statement in Church's and Turing's words==
{{See also|Effective method}}
{{harvs|txt=yes|author-link=J. Barkley Rosser|first=J. B.|last=Rosser|date=1939}} addresses the notion of "effective computability" as follows: "Clearly the existence of CC and RC (Church's and Rosser's proofs) presupposes a precise definition of 'effective'. 'Effective method' is here used in the rather special sense of a method each step of which is precisely predetermined and which is certain to produce the answer in a finite number of steps".<ref>{{harvnb|Rosser|1939}} in {{harvcolnb|Davis|1965|page=225}}.</ref> Thus the adverb-adjective "effective" is used in a sense of "1a: producing a decided, decisive, or desired effect", and "capable of producing a result".<ref>{{cite dictionary |entry=effective |dictionary=Merriam Webster's New Collegiate Dictionary |edition=9th}}</ref><ref>See also {{cite dictionary |url=http://www.merriam-webster.com/dictionary/effective |entry=effective |dictionary=Merriam-Webster's Online Dictionary |edition=11th |access-date=2014-07-26 |postscript=,}} which also gives these definitions for "effective" – the first ["producing a decided, decisive, or desired effect"] as the definition for sense "1a" of the word "effective", and the second ["capable of producing a result"] as part of the "Synonym Discussion of EFFECTIVE" there, (in the introductory part, where it summarizes the similarities between the meanings of the words "effective", "effectual", "efficient", and "efficacious").</ref>
In the following, the words "effectively calculable" will mean "produced by any intuitively 'effective' means whatsoever" and "effectively computable" will mean "produced by a Turing-machine or equivalent mechanical device". Turing's "definitions" given in a footnote in his 1938 Ph.D. thesis ''[[Systems of Logic Based on Ordinals]]'', supervised by Church, are virtually the same:
<blockquote>{{sup|†}} We shall use the expression "computable function" to mean a function calculable by a machine, and let "effectively calculable" refer to the intuitive idea without particular identification with any one of these definitions.<ref name="Turing_1938_thesis_p8">{{cite thesis |author-first=A. M. |author-last=Turing |date=1938 |url=https://webspace.princeton.edu/users/jedwards/Turing%20Centennial%202012/Mudd%20Archive%20files/12285_AC100_Turing_1938.pdf |title=Systems of Logic Based on Ordinals |type=PhD |publisher=Princeton University |page=8 |access-date=2012-06-23 |archive-url=https://web.archive.org/web/20121023103503/https://webspace.princeton.edu/users/jedwards/Turing%20Centennial%202012/Mudd%20Archive%20files/12285_AC100_Turing_1938.pdf |archive-date=2012-10-23 |url-status=dead}}</ref></blockquote>
The thesis can be stated as: ''Every effectively calculable function is a computable function''.<ref>{{harvcoltxt|Gandy|1980|page=123}} states it this way: ''What is effectively calculable is computable.'' He calls this "Church's Thesis".</ref>
Church also stated that "No computational procedure will be considered as an algorithm unless it can be represented as a Turing Machine".{{citation needed|date=November 2019}}
Turing stated it this way:
<blockquote>It was stated&nbsp;... that "a function is effectively calculable if its values can be found by some purely mechanical process". We may take this literally, understanding that by a purely mechanical process one which could be carried out by a machine. The development&nbsp;... leads to&nbsp;... an identification of computability{{sup|†}} with effective calculability. [{{sup|†}} is the footnote quoted above.]<ref name="Turing_1938_thesis_p8"/></blockquote>
==History==
{{Main|History of the Church–Turing thesis}}
One of the important problems for logicians in the 1930s was the [[Entscheidungsproblem]] of [[David Hilbert]] and [[Wilhelm Ackermann]],<ref>David Hilbert and Wilhelm Ackermann: Grundzüge der theoretischen Logik, Berlin, Germany, Springer, 1st ed. 1928. (6th ed. 1972, {{ISBN|3-540-05843-5}}) English Translation:
David Hilbert and Wilhelm Ackermann: Principles of Mathematical Logic, AMS Chelsea Publishing, Providence, Rhode Island, USA, 1950.</ref> which asked whether there was a mechanical procedure for separating mathematical truths from mathematical falsehoods. This quest required that the notion of "algorithm" or "effective calculability" be pinned down, at least well enough for the quest to begin.<ref>Davis's commentary before Church 1936 ''An Unsolvable Problem of Elementary Number Theory'' in Davis 1965:88. Church uses the words "effective calculability" on page 100ff.</ref> But from the very outset [[Alonzo Church]]'s attempts began with a debate that continues to this day.<ref>In his review of ''Church's Thesis after 70 Years'' edited by Adam Olszewski et al. 2006, Peter Smith's criticism of a paper by Muraswski and Wolenski suggests 4 "lines" re the status of the Church–Turing Thesis: (1) empirical hypothesis (2) axiom or theorem, (3) definition, (4) explication. But Smith opines that (4) is indistinguishable from (3), cf. Smith (2007-07-11) ''Church's Thesis after 70 Years'' at http://www.logicmatters.net/resources/pdfs/CTT.pdf</ref> {{clarify span|Was|reason=It should be made clear who asked the question (Peter Smith, mentioned in the previous footnote?).  (revised March 2024)|date=March 2019}} the notion of "effective calculability" to be (i) an "axiom or axioms" in an axiomatic system, (ii) merely a ''definition'' that "identified" two or more propositions, (iii) an ''empirical hypothesis'' to be verified by observation of natural events, or (iv) just ''a proposal'' for the sake of argument (i.e. a "thesis")?
=== 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>cf. 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 NJ (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>Sieg 1997:160 quoting from the 1935 letter written by Church to Kleene, cf. Footnote 3 in 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 [[Entscheidungsproblem]] is unsolvable: there is no algorithm that can determine whether a [[well formed formula]] has a [[beta normal form]].<ref>cf. Church 1936 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 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 [[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>cf. 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… 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 Davis 1952:291.</ref> This idea was "sharply" criticized by Church.<ref>Sieg 1997:171 and 176–177.</ref>
Thus Post in his 1936 paper was also discounting [[Kurt 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">Sieg 1997:160.</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 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). And 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.</ref> Thus, by 1939, both Church (1934) and Turing (1939) had individually proposed that their "formal systems" should be ''definitions'' of "effective calculability";<ref>cf. 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. Kleene 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>
=== Later developments ===
An attempt to better understand the notion of "effective computability" led [[Robin Gandy]] (Turing's student and friend) in 1980 to analyze ''machine'' computation (as opposed to human-computation acted out by a Turing machine). Gandy's curiosity about, and analysis of, [[cellular automata]] (including [[Conway's game of life]]), parallelism, and crystalline automata, led him to propose four "principles (or constraints)&nbsp;... which it is argued, any machine must satisfy".<ref>{{harvcolnb|Gandy|1980|pages=123ff.}}</ref> His most-important fourth, "the principle of causality" is based on the "finite velocity of propagation of effects and signals; contemporary physics rejects the possibility of instantaneous action at a distance".<ref>{{harvcolnb|Gandy|1980|page=135}}</ref> From these principles and some additional constraints—(1a) a lower bound on the linear dimensions of any of the parts, (1b) an upper bound on speed of propagation (the velocity of light), (2) discrete progress of the machine, and (3) deterministic behavior—he produces a theorem that "What can be calculated by a device satisfying principles I–IV is computable."<ref>{{harvcolnb|Gandy|1980|page=126}}</ref>
In the late 1990s [[Wilfried Sieg]] analyzed Turing's and Gandy's notions of "effective calculability" with the intent of "sharpening the informal notion, formulating its general features axiomatically, and investigating the axiomatic framework".<ref>Sieg 1998–1999 in {{harvcolnb|Sieg|Sommer|Talcott|2002|pages=390ff.}}; also Sieg 1997:154ff.</ref> In his 1997 and 2002 work Sieg presents a series of constraints on the behavior of a ''computor''—"a human computing agent who proceeds mechanically". These constraints reduce to:
*"(B.1) (Boundedness) There is a fixed bound on the number of symbolic configurations a computor can immediately recognize.
*"(B.2) (Boundedness) There is a fixed bound on the number of internal states a computor can be in.
*"(L.1) (Locality) A computor can change only elements of an observed symbolic configuration.
*"(L.2) (Locality) A computor can shift attention from one symbolic configuration to another one, but the new observed configurations must be within a bounded distance of the immediately previously observed configuration.
*"(D) (Determinacy) The immediately recognizable (sub-)configuration determines uniquely the next computation step (and id [instantaneous description])"; stated another way: "A computor's internal state together with the observed configuration fixes uniquely the next computation step and the next internal state."<ref>In a footnote Sieg breaks Post's 1936 (B) into (B.1) and (B.2) and (L) into (L.1) and (L.2) and describes (D) differently. With respect to his proposed [[Gandy machine]] he later adds LC.1, LC.2, GA.1 and GA.2. These are complicated; see Sieg 1998–1999 in {{harvcolnb|Sieg|Sommer|Talcott|2002|pages=390ff.}}.</ref>
The matter remains in active discussion within the academic community.<ref>A collection of papers can be found in {{harvtxt|Olszewski|Woleński|Janusz|2006}}. Also a review of this collection: {{cite web |author-first=Peter |author-last=Smith |date=2007-07-11 |title=Church's Thesis after 70 Years |url=http://www.logicmatters.net/resources/pdfs/CTT.pdf}}</ref><ref>See also {{cite web |url=http://www.turing.org.uk/publications/ct70.pdf |title=Did Church and Turing Have a Thesis about Machines? |author-last=Hodges |author-first=Andrew |date=2005 |access-date=2014-07-27 |archive-url=https://web.archive.org/web/20160304032827/http://www.turing.org.uk/publications/ct70.pdf |archive-date=2016-03-04 |url-status=dead}}</ref>
=== The thesis as a definition ===
The thesis can be viewed as nothing but an ordinary mathematical definition. Comments by Gödel on the subject suggest this view, e.g. "the correct definition of mechanical computability was established beyond any doubt by Turing".<ref>{{cite book |author-last=Gödel |author-first=Kurt |author-link=Kurt Gödel |orig-date=193? |section=Undecidable Diophantine Propositions |section-url={{google books|gDzbuUwma5MC|page=164|plainurl=yes}} |title=Collected Works |url={{google books|gDzbuUwma5MC|plainurl=yes}} |volume=3 |page=[{{google books|gDzbuUwma5MC|page=168|plainurl=yes}} 168] |editor-last=Feferman |editor-first=Solomon |editor-link=Solomon Feferman |date=1995 |publisher=[[Oxford University Press]] |location=New York |isbn=978-0-19-507255-6 |oclc=928791907}}</ref> The case for viewing the thesis as nothing more than a definition is made explicitly by [[Robert I. Soare]],<ref name="Soare">{{cite journal |author-first=Robert I. |author-last=Soare |author-link=Robert I. Soare |date=September 1996 |title=Computability and Recursion |journal=Bulletin of Symbolic Logic |volume=2 |issue=3 |pages=284–321 |doi=10.2307/420992 |jstor=420992 |citeseerx=10.1.1.35.5803|s2cid=5894394 }}</ref> where it is also argued that Turing's definition of computability is no less likely to be correct than the epsilon-delta definition of a [[continuous function]].
==Success of the thesis==
Other formalisms (besides recursion, the [[Lambda calculus|λ-calculus]], and the [[Turing machine]]) have been proposed for describing effective calculability/computability. Kleene (1952) adds to the list the functions "''reckonable'' in the system S<sub>1</sub>" of [[Kurt Gödel]] 1936, and [[Emil Post]]'s (1943, 1946) "''canonical'' [also called ''normal''] ''systems''".<ref>Kleene 1952:320</ref> In the 1950s [[Hao Wang (academic)|Hao Wang]] and [[Martin Davis (mathematician)|Martin Davis]] greatly simplified the one-tape Turing-machine model (see [[Post–Turing machine]]). [[Marvin Minsky]] expanded the model to two or more tapes and greatly simplified the tapes into "up-down counters", which Melzak and [[Joachim Lambek|Lambek]] further evolved into what is now known as the [[counter machine]] model. In the late 1960s and early 1970s researchers expanded the counter machine model into the [[register machine]], a close cousin to the modern notion of the [[computer]]. Other models include [[combinatory logic]] and [[Markov algorithm]]s. Gurevich adds the [[pointer machine]] model of Kolmogorov and Uspensky (1953, 1958): "...&nbsp;they just wanted to&nbsp;... convince themselves that there is no way to extend the notion of computable function."<ref>Gurevich 1988:2</ref>
All these contributions involve proofs that the models are computationally equivalent to the Turing machine; such models are said to be [[Turing complete]]. Because all these different attempts at formalizing the concept of "effective calculability/computability" have yielded equivalent results, it is now generally assumed that the Church–Turing thesis is correct. In fact, Gödel (1936) proposed something stronger than this; he observed that there was something "absolute" about the concept of "reckonable in S<sub>1</sub>":
{{quote|It may also be shown that a function which is computable ['reckonable'] in one of the systems S<sub>i</sub>, or even in a system of transfinite type, is already computable [reckonable] in S<sub>1</sub>. Thus the concept 'computable' ['reckonable'] is in a certain definite sense 'absolute', while practically all other familiar metamathematical concepts (e.g. provable, definable, etc.) depend quite essentially on the system to which they are defined&nbsp;...<ref>Translation of Gödel (1936) by Davis in ''The Undecidable'' p. 83, differing in the use of the word 'reckonable' in the translation in Kleene (1952) p. 321</ref>}}<!--
In the early twentieth century, mathematicians often used the informal phrase ''effectively computable'', so it was important to find a good formalization of the concept. Modern mathematicians instead use the well-defined term ''Turing computable'' (or ''computable'' for short). Since the undefined terminology has faded from use, the question of how to define it is now less important.-->
== Informal usage in proofs ==
Proofs in computability theory often invoke the Church–Turing thesis in an informal way to establish the computability of functions while avoiding the (often very long) details which would be involved in a rigorous, formal proof.<ref>Horsten in {{harvcolnb|Olszewski|Woleński|Janusz|2006|page=256}}.</ref> To establish that a function is computable by Turing machine, it is usually considered sufficient to give an informal English description of how the function can be effectively computed, and then conclude "by the Church–Turing thesis" that the function is Turing computable (equivalently, partial recursive).
Dirk van Dalen gives the following example for the sake of illustrating this informal use of the Church–Turing thesis:<ref>{{harvcolnb|Gabbay|2001|page=284}}</ref>
{{quote|1=Example: Each infinite [[recursively enumerable]] (RE) set contains an infinite [[recursive set]].
Proof: Let A be infinite RE. We list the elements of A effectively, n<sub>0</sub>, n<sub>1</sub>, n<sub>2</sub>, n<sub>3</sub>, ...
From this list we extract an increasing sublist: put m<sub>0</sub>&nbsp;= n<sub>0</sub>, after finitely many steps we find an n<sub>k</sub> such that n<sub>k</sub> > m<sub>0</sub>, put m<sub>1</sub>&nbsp;= n<sub>k</sub>. We repeat this procedure to find m<sub>2</sub> > m<sub>1</sub>, etc. this yields an effective listing of the subset B={m<sub>0</sub>, m<sub>1</sub>, m<sub>2</sub>,...} of A, with the property m<sub>i</sub> < m<sub>i+1</sub>.
''Claim''. B is decidable. For, in order to test k in B we must check if k&nbsp;= m<sub>i</sub> for some i. Since the sequence of m<sub>i</sub>'s is increasing we have to produce at most k+1 elements of the list and compare them with k. If none of them is equal to k, then k not in B. Since this test is effective, B is decidable and, '''by Church's thesis''', recursive.}}
In order to make the above example completely rigorous, one would have to carefully construct a Turing machine, or λ-function, or carefully invoke recursion axioms, or at best, cleverly invoke various theorems of computability theory. But because the computability theorist believes that Turing computability correctly captures what can be computed effectively, and because an effective procedure is spelled out in English for deciding the set B, the computability theorist accepts this as proof that the set is indeed recursive.
== Variations ==
The success of the Church–Turing thesis prompted variations of the thesis to be proposed. For example, the '''physical Church–Turing thesis''' states: "All physically computable functions are Turing-computable."<ref>{{cite journal |author-link=Gualtiero Piccinini |author-last=Piccinini |author-first=Gualtiero |date=January 2007 |url=http://www.umsl.edu/~piccininig/Computationalism_Church-Turing_Thesis_Church-Turing_Fallacy.pdf |archive-url=https://web.archive.org/web/20080424151259/http://www.umsl.edu/~piccininig/Computationalism_Church-Turing_Thesis_Church-Turing_Fallacy.pdf |archive-date=2008-04-24 |url-status=live |title=Computationalism, the Church–Turing Thesis, and the Church–Turing Fallacy |doi=10.1007/s11229-005-0194-z |journal=Synthese |volume=154 |issue=1 |pages=97–120 |citeseerx=10.1.1.360.9796 |s2cid=494161}}</ref>{{rp|page=101}}
{{anchor|complexity-theoretic Church–Turing thesis}}The Church–Turing thesis says nothing about the efficiency with which one model of computation can simulate another. It has been proved for instance that a (multi-tape) [[universal Turing machine]] only suffers a logarithmic slowdown factor in simulating any Turing machine.<ref>{{cite book |author-last1=Arora |author-first1=Sanjeev |author-last2=Barak |author-first2=Boaz |url=http://www.cs.princeton.edu/theory/complexity/ |title=Complexity Theory: A Modern Approach |publisher=[[Cambridge University Press]] |date=2009 |isbn=978-0-521-42426-4}} Sections 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9".</ref>
A variation of the Church–Turing thesis addresses whether an arbitrary but "reasonable" model of computation can be efficiently simulated. This is called the '''feasibility thesis''',<ref>{{cite web |title=Official Problem Description |url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf |archive-date=2005-11-24 |archive-url=https://web.archive.org/web/20051124084833/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf}}</ref> also known as the ('''classical''') '''complexity-theoretic Church–Turing thesis''' or the '''extended Church–Turing thesis''', which is not due to Church or Turing, but rather was realized gradually in the development of [[Computational complexity theory|complexity theory]]. It states:<ref name="kaye">{{cite book |author-first1=Phillip |author-last1=Kaye |author-first2=Raymond |author-last2=Laflamme |author-first3=Michele |author-last3=Mosca |title=An introduction to quantum computing |publisher=Oxford University Press |date=2007 |isbn=978-0-19-857049-3 |pages=5–6}}</ref> "A [[probabilistic Turing machine]] can efficiently simulate any realistic model of computation." The word 'efficiently' here means up to [[polynomial-time reduction]]s. This thesis was originally called '''computational complexity-theoretic Church–Turing thesis''' by Ethan Bernstein and [[Umesh Vazirani]] (1997). The complexity-theoretic Church–Turing thesis, then, posits that all 'reasonable' models of computation yield the same class of problems that can be computed in polynomial time. Assuming the conjecture that probabilistic polynomial time ([[Bounded-error probabilistic polynomial|BPP]]) equals deterministic polynomial time ([[P (complexity)|P]]), the word 'probabilistic' is optional in the complexity-theoretic Church–Turing thesis. A similar thesis, called the '''invariance thesis''', was introduced by Cees F. Slot and Peter van Emde Boas. It states: {{"'}}Reasonable' machines can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space."<ref>{{cite book |author-first=Peter |author-last=van Emde Boas |chapter=Machine Models and Simulations |title=Handbook of Theoretical Computer Science A |publisher=[[Elsevier]] |date=1990 |page=5}}</ref> The thesis originally appeared in a paper at [[Symposium on Theory of Computing|STOC]]'84, which was the first paper to show that polynomial-time overhead and constant-space overhead could be ''simultaneously'' achieved for a simulation of a [[Random Access Machine]] on a Turing machine.<ref>{{cite conference |author-first1=C. |author-last1=Slot |author-first2=P. |author-last2=van Emde Boas |title=On tape versus core: an application of space efficient perfect hash functions to the invariance of space |conference=[[Symposium on Theory of Computing|STOC]] |date=December 1984}}</ref>
If [[BQP]] is shown to be a strict superset of [[Bounded-error probabilistic polynomial|BPP]], it would invalidate the complexity-theoretic Church–Turing thesis. In other words, there would be efficient [[quantum algorithms]] that perform tasks that do not have efficient [[probabilistic algorithms]]. This would not however invalidate the original Church–Turing thesis, since a quantum computer can always be simulated by a Turing machine, but it would invalidate the classical complexity-theoretic Church–Turing thesis for efficiency reasons. Consequently, the '''quantum complexity-theoretic Church–Turing thesis''' states:<ref name="kaye"/> "A [[quantum Turing machine]] can efficiently simulate any realistic model of computation."
Eugene Eberbach and Peter Wegner claim that the Church–Turing thesis is sometimes interpreted too broadly,
stating "Though [...] Turing machines express the behavior of algorithms, the broader assertion that algorithms precisely capture what can be computed is invalid".<ref>{{harvnb|Eberbach|Wegner|2003|page=287}}.</ref> They claim that forms of computation not captured by the thesis are relevant today,
terms which they call [[hypercomputation|super-Turing computation]].
==Philosophical implications==
Philosophers have interpreted the Church–Turing thesis as having implications for the [[philosophy of mind]].<ref>{{cite journal |author-last=Abramson |author-first=Darren |title=Philosophy of mind is (in part) philosophy of computer science. |journal=Minds and Machines |date=2011 |volume=21 |issue=2 |pages=203–219 |doi=10.1007/s11023-011-9236-0 |s2cid=32116031 |url=https://dl.acm.org/doi/abs/10.1007/s11023-011-9236-0}}</ref><ref>{{Cite SEP |author-last=Copeland |author-first=B. Jack |author-link=Jack Copeland |date=2017-11-10 |title=The Church-Turing Thesis |url-id=church-turing}}</ref><ref>For a good place to encounter original papers see {{cite book |editor-first=David J. |editor-last=Chalmers |editor-link=David Chalmers |date=2002 |title=Philosophy of Mind: Classical and Contemporary Readings |publisher=Oxford University Press |location=New York |isbn=978-0-19-514581-6 |oclc=610918145}}</ref> [[Jack Copeland|B. Jack Copeland]] states that it is an open empirical question whether there are actual deterministic physical processes that, in the long run, elude simulation by a Turing machine; furthermore, he states that it is an open empirical question whether any such processes are involved in the working of the human brain.<ref>{{cite book |author-first=B. Jack |author-last=Copeland |author-link=Jack Copeland |section=Computation |editor-first=Luciano |editor-last=Floridi |editor-link=Luciano Floridi |title=The Blackwell guide to the philosophy of computing and information |publisher=Wiley-Blackwell |date=2004 |isbn=978-0-631-22919-3 |page=15}}</ref> There are also some important open questions which cover the relationship between the Church–Turing thesis and physics, and the possibility of [[hypercomputation]]. When applied to physics, the thesis has several possible meanings:
#The universe is equivalent to a Turing machine; thus, computing [[Computable_function|non-recursive functions]] is physically impossible. This has been termed the strong Church–Turing thesis, or [[Church–Turing–Deutsch principle]], and is a foundation of [[digital physics]].
#The universe is not equivalent to a Turing machine (i.e., the laws of physics are not Turing-computable), but incomputable physical events are not "harnessable" for the construction of a [[hypercomputation|hypercomputer]]. For example, a universe in which physics involves random [[real numbers]], as opposed to [[computable number|computable real]]s, would fall into this category.
#The universe is a [[hypercomputation|hypercomputer]], and it is possible to build physical devices to harness this property and calculate non-recursive functions. For example, it is an open question whether all [[quantum mechanics|quantum mechanical]] events are Turing-computable, although it is known that rigorous models such as [[quantum Turing machine]]s are equivalent to deterministic Turing machines. (They are not necessarily efficiently equivalent; see above.) [[John Lucas (philosopher)|John Lucas]] and [[Roger Penrose]] have suggested that the human mind might be the result of some kind of quantum-mechanically enhanced, "non-algorithmic" computation.<ref>cf. {{cite book |author-last=Penrose |author-first=Roger |author-link=Roger Penrose |date=1990 |chapter=Algorithms and Turing machines <!--|section=The Church–Turing Thesis--> |pages=47–49 |title=The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics |publisher=Oxford University Press |location=Oxford |oclc=456785846 |isbn=978-0-19-851973-7 |title-link=The Emperor's New Mind}}</ref><ref>Also the description of "the non-algorithmic nature of mathematical insight", {{cite book |author-last=Penrose |author-first=Roger |author-link=Roger Penrose |date=1990 |chapter=Where lies the physics of mind? |pages=416–418 |title=The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics |publisher=Oxford University Press |location=Oxford |oclc=456785846 |isbn=978-0-19-851973-7 |title-link=The Emperor's New Mind}}</ref>
There are many other technical possibilities which fall outside or between these three categories, but these serve to illustrate the range of the concept.
Philosophical aspects of the thesis, regarding both physical and biological computers, are also discussed in Odifreddi's 1989 textbook on recursion theory.<ref>{{cite book |author=Piergiorgio Odifreddi |author-link=Piergiorgio Odifreddi |title=Classical Recursion Theory |location=Amsterdam, Netherlands |publisher=North Holland |series=Studies in Logic and the Foundations of Mathematics |volume=125 |date=1989}}</ref>{{rp|pages=101–123}}
== Non-computable functions ==
{{One source section|date=November 2017}}
One can formally define functions that are not computable. A well-known example of such a function is the [[Busy Beaver]] function. This function takes an input ''n'' and returns the largest number of symbols that a [[Turing machine]] with ''n'' states can print before halting, when run with no input. Finding an upper bound on the busy beaver function is equivalent to solving the [[halting problem]], a problem known to be unsolvable by Turing machines. Since the busy beaver function cannot be computed by Turing machines, the Church–Turing thesis states that this function cannot be effectively computed by any method.
Several computational models allow for the computation of (Church-Turing) non-computable functions. These are known as
[[hypercomputation|hypercomputers]].
Mark Burgin argues that [[super-recursive algorithm]]s such as inductive Turing machines disprove the Church–Turing thesis.<ref>{{cite book |last=Burgin |first=Mark |date=2005 |title=Super-Recursive Algorithms |series=Monographs in Computer Science |publisher=Springer |location=New York |isbn=978-0-387-95569-8 |oclc=990755791 }}</ref>{{page needed|date=November 2017}} His argument relies on a definition of algorithm broader than the ordinary one, so that non-computable functions obtained from some inductive Turing machines are called computable. This interpretation of the Church–Turing thesis differs from the interpretation commonly accepted in computability theory, discussed above. The argument that super-recursive algorithms are indeed algorithms in the sense of the Church–Turing thesis has not found broad acceptance within the computability research community.{{citation needed|date=May 2020}}
==See also==
* [[Abstract machine]]
* [[Church's thesis (constructive mathematics)|Church's thesis in constructive mathematics]]
* [[Church–Turing–Deutsch principle]], which states that every [[physical process]] can be simulated by a universal computing device
* [[Computability logic]]
* [[Computability theory (computation)|Computability theory]]
* [[Decidability (logic)|Decidability]]
* [[Hypercomputation]]
* [[Model of computation]]
* [[Oracle (computer science)]]
* [[Super-recursive algorithm]]
* [[Turing completeness]]
== Footnotes ==
{{Reflist}}
==References==
{{refbegin}}
* {{cite book |editor1-link=Jon Barwise |editor1-last=Barwise |editor1-first=Jon |editor2-link=H. J. Keisler |editor2-last=Keisler |editor2-first=H.J. |editor3-link=Kenneth Kunen |editor3-last=Kunen |editor3-first=Kenneth |date=1980 |title=The Kleene Symposium |publisher=North-Holland Publishing Company |location=Amsterdam |isbn=978-0-444-85345-5}}
* {{cite journal|last=Ben-Amram|first=A. M.|date=2005|title=The Church-Turing Thesis and its Look-Alikes|journal=[[SIGACT News]]|volume=36|issue=3|pages=113–116|doi=10.1145/1086649.1086651|url=http://www2.mta.ac.il/~amirben/downloadable/church-turing.ps|format=PS|citeseerx=10.1.1.74.7308|s2cid=13566703|access-date=2017-10-24 |archive-date=2017-07-06 |archive-url=https://web.archive.org/web/20170706063735/http://www2.mta.ac.il/~amirben/downloadable/church-turing.ps|url-status=dead}}
* {{cite journal|last1=Bernstein|first1=E.|author-last2=Vazirani |author-first2=U.|date=1997|title=Quantum complexity theory|journal=[[SIAM Journal on Computing]]|volume=26|issue=5|pages=1411–1473|doi=10.1137/S0097539796300921|citeseerx=10.1.1.655.1186}}
* {{cite journal|last1=Blass|first1=Andreas|author1-link=Andreas Blass|author2-link=Yuri Gurevich|last2=Gurevich|first2=Yuri|date=October 2003|title=Algorithms: A Quest for Absolute Definitions|journal=Bulletin of European Association for Theoretical Computer Science|issue=81|url=http://research.microsoft.com/~gurevich/Opera/164.pdf|archive-url=https://web.archive.org/web/20040727024450/http://research.microsoft.com/~gurevich/Opera/164.pdf|archive-date=2004-07-27|url-status=live}}{{Page needed|date=November 2017}}
* {{cite book|last=Burgin|first=Mark|title=Monographs in computer science|publisher=Springer|date=2005|chapter=Super-recursive algorithms|isbn=978-0-387-95569-8}}
* {{cite journal|last=Church|first=Alonzo|date=1932|title=A set of Postulates for the Foundation of Logic|journal=Annals of Mathematics|issue=2|volume=33|pages=346–366| jstor=1968337|doi=10.2307/1968337}}
* {{cite journal|last=Church|first=Alonzo|date=April 1936a|title=An Unsolvable Problem of Elementary Number Theory|journal=American Journal of Mathematics|issue=2|pages=345–363|jstor=2371045|volume=58|doi=10.2307/2371045|s2cid=14181275|url=https://pdfs.semanticscholar.org/ee95/8b752cdfc62c16289cd8d3b7274a2e09b14e.pdf|archive-url=https://web.archive.org/web/20200227091349/https://pdfs.semanticscholar.org/ee95/8b752cdfc62c16289cd8d3b7274a2e09b14e.pdf|url-status=dead|archive-date=2020-02-27}}
* {{cite journal|last=Church|first=Alonzo|date=June 1936b|title=A Note on the Entscheidungsproblem|journal=Journal of Symbolic Logic|volume=1|issue=1|pages=40–41|doi=10.2307/2269326|jstor=2269326|s2cid=42323521 }}
* {{cite journal|last=Church|first=Alonzo|date=March 1937|title=Review: A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem|journal=Journal of Symbolic Logic|volume=2|issue=1|pages=42–43|doi=10.2307/2268810|jstor=2268810}}
*{{cite book|last=Church|first=Alonzo|title=The Calculi of Lambda-Conversion|publisher=Princeton University Press|location=Princeton|date=1941}}
* {{cite book|last=Cooper|first=S. B.|author2=Odifreddi, P.|title=Computability and Models: Perspectives East and West|editor=S. B. Cooper |editor2=S. S. Goncharov|publisher=Kluwer Academic/Plenum Publishers|date=2003|pages=137–160|chapter=Incomputability in Nature}}
* {{cite book|title=The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions|url=https://archive.org/details/undecidablebasic0000davi|url-access=registration|editor-link=Martin Davis (mathematician)|editor-last=Davis|editor-first=Martin|publisher=Raven Press|location=New York|date=1965}} Includes original papers by Gödel, Church, Turing, Rosser, Kleene, and Post mentioned in this section.
* {{cite book|last=Dawson |first=John W. Jr. |date=1997 |title=Logical Dilemmas: The Life and Work of Kurt Gödel |publisher=[[A. K. Peters]] |location=Wellesley, Massachusetts, US}}
* {{cite journal|last1=Eberbach|first1=E.|last2=Wegner|first2=P.|date=October 2003|title=Beyond Turing Machines|journal=Bulletin of the European Association for Theoretical Computer Science|issue=81|pages=279–304|url=http://eatcs.org/images/bulletin/beatcs81.pdf#page=287|archive-url=https://web.archive.org/web/20160315185357/http://eatcs.org/images/bulletin/beatcs81.pdf|archive-date=2016-03-15|url-status=live|citeseerx=10.1.1.61.9759}}
* {{cite book|last=Gabbay|first=D. M.|date=2001|title=Handbook of Philosophical Logic|edition=2nd|volume=1}}
* {{cite book|last=Gandy|first=Robin|title=The Kleene Symposium|editor=H. J. Barwise |editor2=H. J. Keisler |editor3=K. Kunen|publisher=North-Holland Publishing Company|date=1980|pages=123–148|chapter=Church's Thesis and the Principles for Mechanisms|author-link=Robin Gandy}}
* {{cite book|last=Gandy|first=Robin|title=The universal Turing Machine: A Half-Century Survey|editor-first=Rolf |editor-last=Herken|publisher=Wien Springer–Verlag|location=New York|date=1994|pages=51ff|isbn=978-3-211-82637-9}}
* {{cite book|last=Gödel|first=Kurt|others=Kleene and Rosser (lecture note-takers); Institute for Advanced Study (lecture sponsor)|title=The Undecidable|url=https://archive.org/details/undecidablebasic0000davi|url-access=registration|editor-last=Davis|editor-first=Martin|publisher=Raven Press|location=New York|date=1965|chapter=On Undecidable Propositions of Formal Mathematical Systems|orig-date=1934}}
* {{cite journal|first=Kurt|last=Gödel|title=Über die Lāange von Beweisen|trans-title=On The Length of Proofs|date=1936|journal=Ergenbnisse Eines Mathematishen Kolloquiums|publisher=Heft|issue=7|pages=23–24|language=de}} Cited by {{harvtxt|Kleene|1952}}.
* {{cite journal|last=Gurevich|first=Yuri|date=June 1988|title=On Kolmogorov Machines and Related Issues|journal=Bulletin of European Association for Theoretical Computer Science|issue=35|pages=71–82|author-link=Yuri Gurevich}}
* {{cite journal|last=Gurevich|first=Yuri|date=July 2000|title=Sequential Abstract State Machines Capture Sequential Algorithms|journal=ACM Transactions on Computational Logic|volume=1|issue=1|pages=77–111|url=http://research.microsoft.com/~gurevich/Opera/141.pdf|archive-url=https://web.archive.org/web/20031016105643/http://research.microsoft.com/~gurevich/Opera/141.pdf|archive-date=2003-10-16|url-status=live|doi=10.1145/343369.343384|citeseerx=10.1.1.146.3017|s2cid=2031696}}
* {{cite journal|last=Herbrand|first=Jacques|date=1932|title=Sur la non-contradiction de l'arithmétique|journal=Journal für die Reine und Angewandte Mathematik|language=fr|volume=166|pages=1–8|doi=10.1515/crll.1932.166.1 |s2cid=116636410 |author-link=Jacques Herbrand}}
* {{cite book|last=Hofstadter|first=Douglas R.|title=Gödel, Escher, Bach: an Eternal Golden Braid|chapter=Chapter XVII: Church, Turing, Tarski, and Others|author-link=Douglas Hofstadter|title-link=Gödel, Escher, Bach: an Eternal Golden Braid |date=5 February 1999 |edition=Twentieth-anniversary |publisher=[[Basic Books]] |pages=559–585 |isbn=0-465-02656-7}}
* {{cite journal|last=Kleene|first=Stephen Cole|date=January 1935|title=A Theory of Positive Integers in Formal Logic|journal=American Journal of Mathematics|issue=1|pages=153–173 & 219–244|author-link=Stephen Cole Kleene|jstor=2372027|volume=57|doi=10.2307/2372027}}
* {{cite journal|last=Kleene|first=Stephen Cole|date=1936|title=Lambda-Definability and Recursiveness|journal=[[Duke Mathematical Journal]]|volume=2|issue=2|pages=340–353|doi=10.1215/s0012-7094-36-00227-2 }}
* {{cite journal|last=Kleene|first=Stephen Cole|title= Recursive Predicates and Quantifiers|journal=Transactions of the American Mathematical Society |volume=  53| issue =  1 |pages=41–73|date=1943 |doi= 10.2307/1990131|jstor=1990131 |doi-access=free}} Reprinted in [[#{{harvid|Davis|1965}}|''The Undecidable'']], p.&nbsp;255ff. Kleene refined his definition of "general recursion" and proceeded in his chapter "12. Algorithmic theories" to posit "Thesis I" (p.&nbsp;274); he would later repeat this thesis (in {{harvcolnb|Kleene|1952|page=300}}) and name it "Church's Thesis" {{harvcol|Kleene|1952|page=317}} (i.e., the [[Church thesis]]).
* {{cite book|last=Kleene|first=Stephen Cole|title=Introduction to Metamathematics|publisher=North-Holland|date=1952|oclc=523942}}
* {{cite book|last=Knuth|first=Donald|title=The Art of Computer Programming|publisher=Addison–Wesley|date=1973|edition=2nd|volume=1/Fundamental Algorithms|author-link=Donald Knuth}}
* {{cite journal|last=Kugel|first=Peter|date=November 2005|journal=Communications of the ACM|title=It's time to think outside the computational box|volume=48|issue=11|pages=32–37|doi=10.1145/1096000.1096001|citeseerx=10.1.1.137.6939|s2cid=29843806}}
* {{cite book|author=Lewis, H.R.|author-link=Harry R. Lewis|author2=Papadimitriou, C.H. |author-link2=Christos H. Papadimitriou |title=Elements of the Theory of Computation|publisher=Prentice-Hall|location=Upper Saddle River, New Jersey, US|date=1998}}
*{{cite book|last=Manna|first=Zohar|title=Mathematical Theory of Computation|location=Dover|orig-date=1974|isbn=978-0-486-43238-0|date=2003|author-link=Zohar Manna}}
*{{cite journal|last=Markov|first=A. A.|date=1960|title=The Theory of Algorithms|journal=American Mathematical Society Translations|volume=2|issue=15|pages=1–14|orig-date=1954|author-link=Andrey Markov Jr.}}
* {{cite book|editor1-last=Olszewski|editor1-first=Adam |editor2-last=Woleński |editor2-first=Jan |editor3-last=Janusz |editor3-first=Robert |date=2006 |title=Church's Thesis After 70 Years |publisher=Ontos |location=Frankfurt |isbn=978-3-938793-09-1 |oclc=909679288 }}
* {{cite book|author=Pour-El, M. B.|author-link=Marian Pour-El|author2=Richards, J.I.|title=Computability in Analysis and Physics|title-link= Computability in Analysis and Physics |publisher=[[Springer Verlag]]|date=1989}}
* {{cite journal|last=Rosser|first=J. B.|date=1939|title=An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem|journal=The Journal of Symbolic Logic|volume=4|pages=53–60|author-link=J. B. Rosser|doi=10.2307/2269059|jstor=2269059|issue=2|s2cid=39499392 }}
* {{cite book |editor1-last=Sieg |editor1-first=Wilfried |editor2-first=Richard |editor2-last=Sommer |editor3-first=Carolyn |editor3-last=Talcott |date=2002 |title=Reflections on the Foundations of Mathematics: Essays in Honor of Solomon Feferman |series=Lecture Notes in Logic |volume=15 |publisher=[[A. K. Peters, Ltd.]] |isbn=978-1-56881-169-7 }}
* {{cite book|last=Syropoulos|first=Apostolos|date=2008|title=Hypercomputation: Computing Beyond the Church–Turing Barrier|publisher=Springer|isbn=978-0-387-30886-9}}
* {{Citation | last = Turing | first = A. M. | author-link = Alan Turing | date = 1937a | title = On Computable Numbers, with an Application to the Entscheidungsproblem | orig-date = Delivered to the Society November 1936 | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 42 | pages = 230–265 | doi = 10.1112/plms/s2-42.1.230 | s2cid = 73712 | url = http://www.comlab.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf }} and {{Cite news| last = Turing | first = A. M. | publication-date = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 43 | pages = 544–546 | doi = 10.1112/plms/s2-43.6.544 | date = 1938 }} (See also: {{harvcolnb|Davis|1965|pages=115ff.}})
* {{cite journal | first=Alan Mathison | last=Turing | title=Computability and λ-Definability | journal=Journal of Symbolic Logic | volume=2 | number=4 | pages=153&ndash;163 | date=December 1937b | jstor=2268280 | doi=10.2307/2268280 | s2cid=2317046 | url=http://pdfs.semanticscholar.org/ee8c/779e7823814a5f1746d883ca77b26671b617.pdf | archive-url=https://web.archive.org/web/20200809215242/http://pdfs.semanticscholar.org/ee8c/779e7823814a5f1746d883ca77b26671b617.pdf | url-status=dead | archive-date=2020-08-09 }}
{{refend}}
==External links==
* {{SEP|church-turing|The Church–Turing Thesis|[[Jack Copeland|B. Jack Copeland]]}}.
* {{SEP|computation-physicalsystems|Computation in Physical Systems|[[Gualtiero Piccinini]]}}—a comprehensive philosophical treatment of relevant issues.
* {{cite journal |last=Kaznatcheev |first=Artem |date=2014-09-11 |url=https://egtheory.wordpress.com/2014/09/11/transcendental-idealism-and-posts-variant-of-the-church-turing-thesis/ |title=Transcendental idealism and Post's variant of the Church-Turing thesis |issue=3 |pages=103–105 |journal=Journal of Symbolic Logic |volume=1 }}
* A [https://projecteuclid.org/euclid.ndjfl/1093637642 special issue] (Vol. 28, No. 4, 1987) of the ''[[Notre Dame Journal of Formal Logic]]'' was devoted to the Church–Turing thesis.
{{Alonzo Church}}
{{Mathematical logic}}
{{Metalogic}}
{{Authority control}}
{{DEFAULTSORT:Church-Turing Thesis}}
[[Category:Computability theory]]
[[Category:Alan Turing]]
[[Category:Theory of computation]]
[[Category:Philosophy of computer science]]