Church-Turing thesis

The Church-Turing thesis states in its most common form that every effective computation or algorithm can be carried out by a Turing machine. The thesis, which is now generally assumed to be true, is also known as Church's thesis (named after [Alonzo Church]?) and Turing's thesis (named after Alan Turing).

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:

1. The method consists of a finite set of simple and precise instructions that are described with a finite number of symbols.
2. The method will always produce the result in a finite number of steps.
3. The method can in principle be carried out by a human being with only paper and pencil.
4. The execution of the method 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 "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.

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 'Einscheidungsproblem' 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 function]? and Lambda-definable function 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 Godel 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 such as [register machines]?s, [Emile Post]?'s systems?, [combinatory definability]? and [Markov algorithm]?s (Markov 1960). Because all these systems have been shown to describe essentially the same set of functions, 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 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.

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.