In computability theory the Church-Turing thesis, Church's thesis, Church's conjecture or Turing's thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, like computers, and what kind of algorithms they can perform.

It is generally assumed that an algorithm must satisfy the following requirements:

1. The algorithm consists of a finite set of simple and precise instructions that are described with a finite number of symbols.
2. The algorithm will always produce the result in a finite number of steps.
3. The algorithm can in principle be carried out by a human being with only paper and pencil.
4. The execution of the algorithm requires no intelligence of the human being except that which is needed to understand and execute the instructions.

An example of such a method is the Euclidean algorithm for determining the greatest common divisor of two natural numbers.

The notion of algorithm is intuitively clear but is not formally defined since it is not exactly clear what a "simple and precise instruction" is, and what exactly the "required intelligence to execute these instructions" is. (See for example effective results in number theory for cases well beyond the Euclidean algorithm.)

Informally the thesis states that our notion of algorithm can be made precise (in the form of computable function) and computers can run those algorithms. Furthermore any computer can theoretically run any algorithm, that is the theoretic computational power of each computer is the same and it is not possible to build a calculation device which is more powerful than a computer. (Note that this formulation has implicit in it the idea that memory/storage is separate from device; any actual computer has finite memory, but the formulation always assumes that memory can be added at will.)

The thesis may be regarded as a physical law as it cannot be mathematically proven.

Church-Turing thesis

The thesis, in Turing's own words, 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 can neither be proven nor disproven formally.

Any computer program can be translated into a Turing machine, and any Turing machine can be translated into any general-purpose programming language, so the thesis is equivalent to saying that any general-purpose 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.

This stronger statement was proven false in 2002 when William Fouché discovered that a Turing machine cannot effectively approximate any of the values of one-dimensional Brownian motion at rational points in time almost surely (with respect to Wiener measure; see reference below)

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.

History

The thesis is named after mathematicians Alonzo Church and Alan Turing. In his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem" Alan 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 Alonzo 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 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). When 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 essentially 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 proven true. It could, however, be disproven 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 conjecture that there is a polynomial transformation from the representation of computable functions in one formalization to their representation in another, and the conjecture that every model of computation can be step-by-step simulated by a Turing machine.

Philosophical implications

The Church-Turing thesis has 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:

1. 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 and is assumed in digital physics.
2. The universe is not a Turing machine (ie, 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.
3. 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 famously, Roger Penrose) have suggested that the human mind might be the result of quantum hypercomputation, although a lack of physical or neurological evidence renders this theory scientifically dubious.

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

Additional reading

• Hofstadter, Douglas R., Gödel, Escher, Bach: an Eternal Golden Braid, Chapter 17.

References

• 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.
• 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'arithmetique", Journal fur die reine und angewandte Mathematik, 166, 1-8.
• 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.
• 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 (http://www.abelard.org/turpap2/tp2-ie.asp)", 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.
• William Fouché, Arithmetical representations of Brownian motion, J. Symbolic Logic 65 (2000) 421-442
• E. Bernstein, U. Vazirani, Quantum complexity theory, SIAM Journal on Computing 26(5) (1997) 1411–1473

External links

• Detailed info on the Church-Turing Hypothesis (http://plato.stanford.edu/entries/church-turing/) (Stanford Encyclopedia of Philosophy)

See also

• Computability logic
• Interactive computation
• Computability theory