Editing Church–Turing thesis (section)

{{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>{{Cite journal |last=Soare |first=Robert I. |date=2009-09-01 |title=Turing oracle machines, online computing, and three displacements in computability theory |url=https://linkinghub.elsevier.com/retrieve/pii/S0168007209000128 |journal=Annals of Pure and Applied Logic |series=Computation and Logic in the Real World: CiE 2007 |volume=160 |issue=3 |pages=368–399 |doi=10.1016/j.apal.2009.01.008 |issn=0168-0072}}</ref> the  '''Turing–Church thesis''',<ref>{{cite journal |last1=Conrad |first1=Michael |title=On design principles for a molecular computer |journal=Communications of the ACM |date=May 1985 |volume=28 |issue=5 |pages=464–480 |doi=10.1145/3532.3533}}</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]]).