Church–Turing thesis

In computability theory the Church–Turing thesis (also known as the Church's thesis, Church's conjecture and Turing's thesis) is a hypothesis about the nature of computers, such as a digital computer or a human with a pencil and paper following a set of rules. The thesis claims that any calculation that is possible can be performed by an algorithm running on a computer, provided that sufficient time and storage space are available. The thesis may be regarded as a physical law or as a definition, as it has not been mathematically proven.

Informally the Church-Turing thesis states that our notion of algorithm can be made precise and computers can run those algorithms. Furthermore, a computer can theoretically run any algorithm; in other words, all ordinary computers are equivalent to each other in terms of theoretical computational power, and it is not possible to build a calculation device that is more powerful than a computer. (Note that this formulation of power disregards practical factors such as speed or memory capacity; it considers all that is theoretically possible, given unlimited time and memory.)

The thesis was first proposed by Stephen C. Kleene in 1943, but named after Alonzo Church and Alan Turing.

Formal Statement

The thesis can be stated as:

"Every 'function which would naturally be regarded as computable' can be computed by a Turing machine."

Due to the vagueness of the concept of a "function which would naturally be regarded as computable", the thesis cannot formally be proven. Disproof would be possible only if humanity found ways of building hypercomputers whose results should "naturally be regarded as computable".

Any non-interactive computer program can be translated into a Turing machine, and any Turing machine can be translated into any Turing complete programming language, so the thesis is equivalent to saying that any Turing complete programming language is sufficient to express any algorithm.

Various variations of the thesis exist; for example, the Physical Church–Turing thesis (PCTT) states:

"Every function that can be physically computed can be computed by a Turing machine."

Another variation is the Strong Church–Turing thesis (SCTT), which states (cf. Bernstein, Vazirani 1997):

"Any 'reasonable' model of computation can be efficiently simulated on a probabilistic Turing machine."

Some argue that quantum computing possibly invalidates the strong Church-Turing thesis since a number of tasks which can be performed with efficient quantum algorithms are not known to admit efficient probabilistic algorithms. Whether or not quantum Turing machines form a reasonable model of computation is debatable given the technical challenge of physically implementing such a machine.

History

In his 1943 paper Recursive Predicates and Quantifiers (reprinted in The Undecidable, p. 255) Stephen Kleene first proposed his "THESIS I":

"This heuristic fact recursive functions are effectively calculable...led Church to state the following thesis footnote 22. The same thesis is implicit in Turing's description of computing machines footnote 23.

"THESIS I. Every effectively calculable function (effectively decidable predicate) is general recursive italics

"Since a precise mathematical definition of the term effectively calculable (effectively decidable) has been wanting, we can take this thesis ... as a definition of it..." (Kleene in Undecidable, p. 274)

Kleene's footnote 22 references the paper by Alonzo Church and his footnote 23 references the paper by Alan Turing. He goes on to note that:

"...the thesis has the character of an hypothesis -- a point emphasized by Post and by Church" footnote 24, The Undecidable, p. 274. His references are to Post's paper (1936) and to Church's paper Formal definitions in the theory of ordinal numbers, Fund. Math. vol 28 (1936) pp.11-21 )(see ref. #2, p. 286, Undecidable).

In his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem" Turing tried to capture the notion of algorithm (then called "effective computability"), with the introduction of Turing machines. In that paper he showed that the 'Entscheidungsproblem' could not be solved. A few months earlier Church had proven a similar result in "A Note on the Entscheidungsproblem" but he used the notions of recursive functions and lambda-definable functions to formally describe effective computability. Lambda-definable functions were introduced by Alonzo Church and Stephen Kleene (Church 1932, 1936a, 1941, Kleene 1935), and recursive functions were introduced by Kurt Gödel and Jacques Herbrand (Gödel 1934, Herbrand 1932). These two formalisms describe the same set of functions, as was shown in the case of functions of positive integers by Church and Kleene (Church 1936a, Kleene 1936). After hearing of Church's proposal, Turing was quickly able to show that his Turing machines in fact describe the same set of functions (Turing 1936, 263ff).

Success of the thesis

Since that time, many other formalisms for describing effective computability have been proposed, including recursive functions, the lambda calculus, register machines, Post systems, combinatory logic, and Markov algorithms. All these systems have been shown to compute the same functions as Turing machines; systems like this are called Turing-complete. Because all these different attempts of formalizing the concept of algorithm have yielded equivalent results, it is now generally assumed that the Church–Turing thesis is correct. However, the thesis is a definition and not a theorem, and hence cannot be proved true. The physical version could, however, be disproved if a method could be exhibited which is universally accepted as being an effective algorithm but which cannot be performed on a Turing machine.

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.

The success of the Church–Turing thesis prompted supertheses that extend the thesis, including the strong Church-Turing thesis mentioned earlier.

Philosophical implications

The Church–Turing thesis has been alleged to have some profound implications for the philosophy of mind. 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 (and thus, computing non-recursive functions is physically impossible). This has been termed the strong Church–Turing thesis (not to be confused with the previously mentioned SCTT) and is a foundation of digital physics.
The universe is not 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 hypercomputer. For example, a universe in which physics involves real numbers, as opposed to computable reals, might fall into this category.
The universe is a 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 mechanical events are Turing-computable, although it has been proved that any system built out of qubits is (at best) Turing-complete. John Lucas (and more famously, Roger Penrose) have suggested that the human mind might be the result of quantum hypercomputation, although there is little scientific evidence for this theory.

There are many other technical possibilities which fall outside or between these three categories, but these serve to illustrate the range of the concept.

References

Bernstein, E. & Vazirani, U. Quantum complexity theory, SIAM Journal on Computing 26(5) (1997) 1411?1473
Church, A., 1932, "A set of Postulates for the Foundation of Logic", Annals of Mathematics, second series, 33, 346-366.
Church, A., 1936, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics, 58, 345-363.
Church, A., 1936, "A Note on the Entscheidungsproblem", Journal of Symbolic Logic, 1, 40-41.
Church, A., 1941, The Calculi of Lambda-Conversion, Princeton: Princeton University Press.
Fouché, W., Arithmetical representations of Brownian motion, J. Symbolic Logic 65 (2000) 421-442
Gödel, K., 1934, "On Undecidable Propositions of Formal Mathematical Systems", lecture notes taken by Kleene and Rosser at the Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, The Undecidable, New York: Raven.
Herbrand, J., 1932, "Sur la non-contradiction de l'arithmétique", Journal fur die reine und angewandte Mathematik, 166, 1-8.
Hofstadter, Douglas R., an Eternal Golden Braid, Chapter 17.
Kleene, S.C., 1935, "A Theory of Positive Integers in Formal Logic", American Journal of Mathematics, 57, 153-173, 219-244.
Kleene, S.C., 1936, "Lambda-Definability and Recursiveness", Duke Mathematical Journal 2, 340-353.
Knuth, Donald E.,The Art of Computer Prograamming, Second Edition, Volume 1/Fundamental Algorithms, Addison-Wesley, 1973.
Markov, A.A., 1960, "The Theory of Algorithms", American Mathematical Society Translations, series 2, 15, 1-14.
Turing, A.M., 1936, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, 42 (1936-37), pp.230-265.
Pour-El, M.B. & Richards, J.I., 1989, Computability in Analysis and Physics, Springer Verlag.
Martin Davis editor, The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. All the original papers are here including those by Gödel, Church, Turing, Rosser, Kleene, and Post mentioned in this section. Valuable commentary by Davis prefaces most papers.

External links

Detailed info on the Church–Turing Hypothesis (Stanford Encyclopedia of Philosophy)

Recursion theory | Alan Turing | Theory of computation