home | alphabetical index | |||||

## Church-Turing thesisIn computer science, theChurch-Turing thesis states in its most common form that every effective computation or algorithm can be carried out by a Turing machine. Any computer program in any of the conventional programming languages can be translated into a Turing machine, and any Turing machine can be translated into most programming languages, so the thesis is equivalent to saying that the conventional programming languages are sufficient to express any algorithm. The thesis, which is now generally assumed to be true, is also known as Church's thesis or Church's conjecture (named after Alonzo Church) and Turing's thesis (named after Alan Turing).
The thesis might be rephrased as saying that the notion of - The method consists of a finite set of simple and precise instructions that are described with a finite number of symbols.
- The method will always produce the result in a finite number of steps.
- The method can in principle be carried out by a human being with only paper and pencil.
- The execution of the method requires no intelligence of the human being except that which is needed to understand and execute the instructions.
The notion of "effective method" 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.)
In his 1936 paper Since that time many other formalisms for describing effective computability have been proposed such as register machines, Emil Post's systems, combinatory definability and Markov algorithms (Markov 1960). 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 does not have the status of a theorem and cannot be proven; it is conceivable but unlikely that it could be disproven by exhibiting a method which is universally accepted as being an effective algorithm but which cannot be performed on a Turing machine.
In fact, the Church-Turing thesis has been so successful, that it is now almost moot. In the early twentieth century, mathematicians often used the informal phrase 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:
- The universe is a Turing machine (and thus, computing non-recursive functions is physically impossible). This has been termed the
*strong Church-Turing thesis*. - 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 realss, 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 as to 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 this proposition is epistemologically dubious. At this stage, it seems unlikely that physics will admit harnessable hypercomputation.
## References:- Church, A. 1932.
*A set of Postulates for the Foundation of Logic*. Annals of Mathematics, second series, 33, 346-366. - Church, A. 1936a.
*An Unsolvable Problem of Elementary Number Theory*. American Journal of Mathematics, 58, 345-363. - Church, A. 1936b.
*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*. Proceedings of the London Mathematical Society, Series 2, 42 (1936-37), pp.230-265. Available online at http://www.abelard.org/turpap2/tp2-ie.asp . - Pour-El, M.B. & Richards, J.I. 1989.
*Computability in Analysis and Physics*. Springer Verlag.
| |||||

copyright © 2004 FactsAbout.com |