The thesis of Church thesis of Church-Turing was suggested only by Robert I. Soare: Computability and recursion . Bulletin off Symbolic Logic 2 (3): 284-321 (1996), but it does not seem to rest on any historical base. More precisely, Church emitted its principle in the years 1930, but the undeniable validity of this principle was confirmed only during the appearance of the model of Turing. --> - name of the mathematician Alonzo Church - is the basic principle of the Calculabilité. In its most ordinary form, she affirms that any realizable treatment mechanically can be accomplished by a computer (more precisely in its idealized form than is a Machine of Turing). In a more elaborate form, she affirms that an intuitive concept, the effective calculability , coincides with a formal and mathematical concept, the calculability , definite in several ways which one could show mathematically that they are equivalent.

Stephen Kleene called the first “thesis of Church” (in 1943 and 1952) what the latter presented like a definition of the effective calculability. It is known more recently under the name of thesis of Church-Turing terminology suggested by certain specialists in the years 1990, although Church is without any doubt the first, with the beginning of the year 1930, to have thought of being able to define the intuitive calculability formally (by the λ-definissability). However it is the article of Turing of 1936 and its mechanical model of calculability, which definitively carried adhesion, according to Gödel, Kleene and Church itself.

Equivalent forms of the thesis

The thesis is formulated by saying that the machines of Turing (the λ-definable functions, the recursive Fonctions) formalize correctly the concept of effective method of calculation . It is generally considered that an effective method must satisfy the following obligations:

1. the algorithm consists of a finished whole of simple and precise instructions which are described with a limited number of symbols;
2. the algorithm must always produce the result in a finished number of stages;
3. the algorithm can in theory be followed by human with only of paper and a pencil;
4. the execution of the algorithm does not require intelligence of human except that which is necessary to include/understand and carry out the instructions.

An example of such a method is the Algorithme of Euclide to determine the highest common factor of natural entireties or that which determines for an entirety N the length of the continuation of Goodstein which starts in N .

It is of a rather clear intuitive definition, but not a formal definition, fault of having specified what one understands by “simple and precise instruction” or by “the necessary intelligence to carry out the instructions”. One can on the other hand define formally what is an algorithm and for this reason one has the choice of various formalisms. At this stage, the thesis of Church affirms that the two concepts, intuitive “effective” and formal “method algorithm”, agree.

Success of the thesis

At the beginning of the 20th century, the mathematicians used abstract expressions like indeed realizable , it was thus important to find a formalization rigorous of this concept. Since the year 1940, the mathematicians use thanks to the thesis of Church a well defined concept, that of calculable function.

The thesis was initially formulated for the Lambda-calculation, but of other formalisms were proposed to model the calculable functions, for example the recursive functions, the machine of Turing, the machines of Post and the machines with meters. More surprising is probably that proposed by Yuri Matiyasevich by solving the Tenth problem of Hilbert. One can show that all these definitions, although founded on rather different ideas, describe exactly the same whole of functions. These systems, which have the same capacity of expression that any of these equivalent definitions, are known as Turing-complete Turing-equivalents or .

The fact that all these attempts to formalize the concept of algorithm led to equivalent results is the argument which returns the thesis of Church impossible to circumvent.

History

In its article of 1943 recursive Predicates and quantifiers (original title Recursive Predicates and Quantifiers ) Stephen Kleene (included in Indécidable , original title The Undecidable ) proposed for the first statement of the thesis of Church which it calls “THESIS I”:

“This heuristic fact general recursive functions are indeed calculable… led Church to state the following thesis 22 of Kleene. The same thesis is implicit in the description of the machines of Turing 23 of Kleene.

“ THESIS I. Each indeed calculable function (each predicate indeed décidable) is recursive general Italic are of Kleene

“Since we seek a precise mathematical definition of the indeed calculable expression (indeed décidable), we will take this thesis like his definition…” (Kleene in the indécidable , P. 274)

The note 22 of Kleene refers to the article of Church while its note 23 refers to the article of Alan Turing. It continues by noting that

“… the thesis is only one assumption -- a observation already underlined by Post and Church” note 24, in '' the indécidable '', P. 274. It refers to the articlde of Post (1936) and to the formal definitions of the article of Church Formal definitions in the theory off ordinal numbers, Fund. Maths. vol. 28 (1936) pp.11-21 (see ref. 2, P. 286, of the indécidable )].

In its article of 1936 “on calculable numbers, with an application to the Entscheidungsproblem” (original title “One Computable Numbers, with year Application to the Entscheidungsproblem ”) Turing formalized the concept of algorithm (then called “effective calculability”), by introducing the machines known as maintaining of Turing. In this article he writes in particular on page 239:

“a calculable continuation γ is determined by a description of a machine which calculates γ… and, in fact, any calculable continuation is likely to be described in term of a table of a machine of Turing.” what is the version of Turing of the thesis of Church, that he did not know at the time.

Church had shown to him also a few months earlier the insolvency of the problem of the decision in “a note on Entscheidungsproblem” for that it had used the recursive functions and the λ-definable functions for to describe the effective calculability formally. The λ-definable functions had been introduced by Alonzo Church and Stephen Kleene (Church 1932,1936a, 1941, Kleene 1935) and the recursive functions had been introduced by Kurt Gödel and Jacques Herbrand (Gödel 1934, Herbrand 1932). These two formalisms describe the same whole of functions, as that was shown in the case of the functions on the positive entireties by Church and Kleene (Church 1936a, Kleene 1936). After having heard of the proposal of Church, Turing quickly could outline a demonstration which its machines of Turing describe in fact the same whole of functions (Turing 1936,263 and following ). In a article published in 1937 it shows the equivalence of the three models: λ-definable functions, machines of Turing and general functions recursive within the meaning of Herbrand and Gödel. Rosser summarizes the feelings of the protagonists:

“Once the equivalence of the general recursivity and the established λ-definsissability, Church, Kleene and me we waited until Gödel join us to support the thesis of Church. Gödel however had still reserves and that is only at least two or three years later, after work of Turing, that Gödel became finally a follower (as became to it also Turing). ”

Turing writes in 1937:

“the identification of “the indeed calculable” functions with the calculable functions defined by a machine of Turing is perhaps more convincing than the identification with the λ-definable or recursive functions general. For those which adopt this point of view, the formal demonstration of equivalence provides a justification of the calculation of Church and makes it possible to replace the “machines” which generate calculable functions by the λ-definitions which are more convenient. ”

Noncalculable functions and numbers

One can very formally define functions (for example on the natural entireties) which are not calculable. They in general take so large values which one cannot calculate them and consequently one cannot even “express” the values that they take, because it is their definition which says it. Most known known as of the busy Castor is that. To simplify, it is a question of the size of the greatest work which a machine of Turing can make when one gives him a resource limited by N . As its definition is obtained as a limit of what the machines of Turing could do, the number which it produces cannot be calculated, nor even its expressed exact value, at most the researchers manage to give numbers which are lower to him for the smallest values of N (2, 3,4,5, painfully 6).

The number Oméga of Chaitin is a perfectly definite real number which is not calculable, precisely because its construction depends on the answers to the semi-décidable problem of the stopping of the machines of Turing.

See too

References