 |
|
| ||||||||||||||||||||||||||
|
|
| ||||||||||||||||||||||||||
|
|
|
|
|
| ||||||||
The Church-Turing thesis is an idea in computer science named after the mathematicians Alonzo Church and Alan Turing. In its most common form, it states 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 and Turing's thesis.
The thesis might be rephrased as saying that the notion of effective or mechanical method in logic and mathematics is captured by Turing machines. It is generally assumed that such methods must satisfy the following requirements:
An example of such a method is the Euclidean algorithm for determining the greatest common divisor of two natural numbers.
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 "On Computable Numbers, with an Application to the Entscheidungsproblem" Alan Turing tried to capture this notion formally 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).
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.
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:
There are actually many technical possibilities which fall outside or between these three categories, but these should serve to illustrate the concept.
|
||||
| View Live Article | This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License | |
||
