See also: Church

Alonzo Church June 14th 1903 - August 11th 1995 was a Mathématicien (logician) American with which one owes some of the bases of the theoretical Informatique.

It is known mainly for the development of the Lambda-calculation, its application to the concept of recursive function, for the first demonstration of the existence of a problem indécidable and for its role in the creation of the Journal off Symbolic Logic . Work of its team (Church, Kleenne and Rosser) precedes work by Alan Turing on the Problème of the stop. It is Church which it first with the idea that one can define the concept of function calculable in a very broad direction, this idea had already interview by Herbrand, but its untimely death had not enabled him to push it further. Church had the idea by lambda-calculation of it. Church shows in 1936 the existence of an insoluble problem by average mechanics. Kleene shows that the Lambda-calculation of Church, the recursive general functions (model known as of Herbrand- Gödel) and the machines of Turing have equivalent capacities. Equivalence shown then that a certain number of mathematical formalizations of the concept of treatment by mechanical processes have aptitudes in all similar points confirms the intuition of Church. This observation leads to the thesis of Church (also called thesis of thesis of Church-Turing ). It is called “thesis” because it is about a result which cannot be proven, because he affirms equivalence between an intuitive concept, namely the mechanically calculable functions, and a formal concept, namely, the various definitions of the recursive functions. It is called the “thesis of Church” since it is him which had the first of it the idea. It is called the “thesis of Church-Turing” since the machines of Turing give a true idea of what “mechanical” wants to say.

Among its students with Princeton, it had logicians become famous, namely C. Anthony Anderson, Peter Andrews, Martin Davis, Leon Henkin, John George Kemeny, Stephen Kleene, Michael O. Rabin, Hartley Rogers, Jr, J. Barkley Rosser, Dana Scott, Raymond Smullyan and Alan Turing. See.

Its work influenced the languages of functional Programmation.

Sources and references

• Stephen Kleene Origins off Recursive Function Theory in Annals off the History off Computing , vol. 3 No January 1st, th and th 1981. This article tells the period which with seen in Princeton the emergence of the concept of recursive function.

• Wilfried Sieg Step By Recursive Step: Church' S Analysis Off Effective Calculability (1997), The Bulletin off Symbolic Logic, flight 3, n°2. Discuss emergence of the concept of recursivity in the thought of Church.

• a discussion with Church over its period with Princeton (in English)

See too

• Problem of the decision

Random links:

Laryngectomy | Alan Freed | Arnaville | Starling of Bourbon | BETTINA Wiegmann