Editing Church–Turing thesis (section)

==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.-->