# Alonzo Church

Alonzo Church (14 juin 1903 Washington - 11 août 1995 Hudson) est un mathématicien (logicien) américain à qui l'on doit certains des fondements de l'informatique théorique.

## Biographie

Alonzo Church est né le 14 juin 1903 à Washington. Il est le fils de Samuel Robbins Church, juge auprès de la cour de district de Columbia, et de Mildred Hannah Letterman Parker. Son arrière grand-père Alonzo S. Church (en) a été professeur de mathématiques et d'astronomie puis président du Franklin College, l'actuelle Université de Géorgie, pendant trente ans. Son grand-père Alonzo Webster Church fut bibliothécaire et bibliographe du Sénat des États-Unis et conseiller général pour le Chicago & Alton Railroad.
Quand le déclin de la vue et de l'audition de son père l'obligent à abandonner son poste, la famille déménage en Virginie où Alonzo Church et son jeune frère Randolph grandissent. L'oncle d'Alonzo (également nommé Alonzo Church) vivant à Newark dans le New Jersey, apporte une aide financière à la famille et participe à l'éducation des enfants. Un accident avec un pistolet à air comprimé fait perdre un œil à Church. Church poursuit ses études à l'école de Ridgefield, un établissement pour garçon dans le Connecticut réputé pour sa grande rigueur. Il en sort diplômé en 1920.

### Princeton

Church s'inscrit à l'université de Princeton, établissement que ses oncles ont également fréquenté. Sa première publication, Uniqueness of the Lorentz Transformation, parue en 1924, fut écrite pendant ses études de premier cycle universitaire. Il obtient sa licence la même année.
Il continue ses études universitaires à Princeton, où il épouse une jeune élève infirmière, Mary Julia Kuczinski, le 25 août 1925$^,$. De leur union naîtront trois enfants Alonzo Church, Jr. (1929), Mary Ann (1933)$^,$ et Mildred (1938). Il obtient son doctorat en trois ans en 1927 sous la direction d'Oswald Veblen. Dans sa thèse intitulée Alternatives to Zermelo's Assumption, il étudie une logique dans laquelle l'axiome du choix, proposé en 1904 par Zermelo, serait faux.
Avec son doctorat, il reçoit une bourse de recherche nationale qu'il utilise pour voyager. Ainsi, durant l'été 1927, il est instructeur à l'Université de Chicago. Il passe deux ans à l'Université Harvard (1927-1928), puis se rend à l'Université de Göttingen où il rencontre David Hilbert et Paul Bernays, puis à l'Université d'Amsterdam où il rencontre Luitzen Egbertus Jan Brouwer (1928-1929). Son fils Alonzo Church Junior naît le 9 septembre 1929 dans cette même ville.
Au terme de sa bourse de recherche, Church retourne à Princeton. Il y devient professeur assistant de 1929 à 1939, puis professeur associé de 1939 à 1947, puis professeur de 1947 à 1967
Vers 1934, Church commence la rédaction d'un compendium dans lequel il rassemble l'ensemble des œuvres disponibles en logique sur la période courant de 1666 à 1935. Celles-ci y sont référencées par auteur et par sujet. Il intitule son œuvre A bibliography of symbolic logic. Elle sera publiée par la suite par l'intermédiaire de l'Association for Symbolic Logic dans le premier volume du Journal of Symbolic Logic en 1936.
Dans les années 1930, Princeton est un lieu propice aux échanges en logique car John von Neumann s'y trouve, ainsi que trois étudiants brillants de Church : Stephen Kleene, John Barkley Rosser et Alan Turing. Kurt Gödel, après plusieurs déplacements à l'Institute for Advanced Study entre 1933 et 1935, y donne plusieurs conférences sur son théorème d'incomplétude, et s'y installe définitivement vers 1940. L'Association for Symbolic Logic y naît ; il en est nommé le président en 1936. Church en sera l'un des éditeurs. Il édite quinze volumes entre 1936 et 1950. Il est également le rédacteur en chef de la partie Review du Journal of Symbolic Logic dans laquelle il apporte une relecture et une critique analytique des thèses qui lui sont soumises, une tâche qu'il accomplit pour les 44 premiers volumes entre 1936 et 1979.

### UCLA

En 1967, Church décide de quitter l'université de Princeton pour rejoindre l'Université de Californie à Los Angeles, car l’université de Princeton n'est plus disposée à accueillir l'équipe du Journal of Symbolic Logic alors que celle de Californie s'engage à la soutenir tant que Church en restera le rédacteur en chef. À la mort de son épouse Mary en 1976, Church partage sa fonction dans le journal avec le logicien William Craig (en). Alonzo Church est élu membre de la National Academy of Sciences en 1978.
En 1979 Church arrête de rédiger ses critiques dans le Journal of Symbolic Logic. Church est fait docteur honoris causa de plusieurs universités, et reçoit un diplôme d'honneur de son alma mater en 1985. Il est membre correspondant de la British Academy et membre de l’Académie américaine des arts et des sciences. En 1990, à 87 ans, Church met fin à 63 ans de carrière universitaire en quittant l'UCLA.

## Travaux

Il est connu principalement pour le développement du lambda-calcul, son application à la notion de fonction récursive, pour la première démonstration de l'indécidabilité de l'arrêt. Il a aussi dirigé le Journal of Symbolic Logic, dont il est l'un des fondateurs en 1936.

### Les débuts de la calculabilité

Church en 1936 publie « An Unsolvable Problem of Elementary Number Theory » (avec l'aide de ses élèves Kleene et Rosser) sur les fonctions de nombres entiers que l'on peut calculer mécaniquement. C'est-à-dire les fonctions dont on peut calculer les valeurs par un algorithme en un nombre fini d'étapes. Il les appelle des « fonctions effectivement calculables ». La notion de « mécaniquement calculable » étant intuitive et floue — puisqu'elle fait appel aux machines présentes et à venir —, il cherche à donner une définition précise de ces fonctions. Il va faire deux propositions.
La première consiste à utiliser le lambda-calcul, qu'il vient d'inventer en 1932. Les fonctions effectivement calculables seront alors les fonctions lambda-définissables, c'est à dire les fonctions que l'on définir grâce au lambda-calcul. La proposition se justifie puisqu'il est clair que les valeurs des fonctions lambda-définissables peuvent être déterminées par un algorithme en un nombre fini d'étapes.
La seconde proposition consiste à utiliser les fonctions que Gödel a définies dans les leçons qu'il a données à Princeton en 1934 et qu'il a appelées « fonctions récursives ». L'intérêt de cette notion avait déjà été entrevu par Herbrand — et communiqué par celui-ci à Gödel — mais la mort prématurée en 1931 du logicien français avait interrompu ses recherches.
Church ne parle pas des travaux de Turing sur les machines qui portent désormais son nom puisqu'ils ne seront publiés qu'en 1937. Mais elles constitueront un troisième moyen de définir les fonctions effectivement calculables.
Dans son article de 1936, Church démontre l'existence d'un problème insoluble par des fonctions effectivement calculables.
Les fonctions étudiées par Church peuvent sembler très particulière puisqu'elles portent sur des variables entières mais il suffit de penser au fonctionnement d'un ordinateur — dont la mémoire n'est constituée que de nombres entiers et dont le processeur ne traitent que des nombres entiers — pour réaliser que ces fonctions sont en fait très générales.
Cette notion est également cruciale en logique puisqu'elle conditionne la possibilité de calculer mécaniquement — et non par une démonstration, laquelle fait appel à l'imagination — la vérité d'un théorème.

### La thèse de Church

Kleene et Turing démontrent ensuite que le lambda-calcul de Church, les fonctions générales récursives (modèle dit de Herbrand-Gödel) et les machines de Turing ont des capacités équivalentes : les fonctions définissables par chacun de ces trois moyens sont les mêmes.
Cette constatation aboutit à la thèse de Church (appelée aussi thèse de Church-Turing) : les fonctions calculables mécaniquement sont les fonctions effectivement définissables. Proposition indémontrable — d'où le nom de thèse— puisque s'il est clair que les fonctions lambda définissables, les fonctions récursives de Gödel ou les fonctions définies par une machine de Turing peuvent être calculées par un procédé mécanique, le contraire reste improuvable à cause du flou qui entoure la notion de procédé mécanique. Elle s'appelle la « thèse de Church » puisque c'est lui qui en a eu le premier l'idée.
La « thèse de Church » s'appelle encore la « thèse de Church-Turing » puisque les machines de Turing donnent l'idée la plus claire de ce que « mécanique » veut dire.

## Influence et étudiants

Parmi ses étudiants à Princeton, il eut des logiciens devenus célèbres, à savoir C. Anthony Anderson, Peter Andrews (en), Martin Davis, Leon Henkin (en), Maurice L'Abbé, John George Kemeny, Stephen Kleene, Michael O. Rabin, Hartley Rogers, Jr (en), J. Barkley Rosser, Dana Scott, Raymond Smullyan et Alan Turing.
Ses travaux influencèrent les langages de programmation fonctionnelle.

## Publications

* Alonzo Church, Introduction to Mathematical Logic (ISBN 978-0-691-02906-1).
* Alonzo Church, The Calculi of Lambda-Conversion (ISBN 978-0-691-08394-0).
* Alonzo Church, A Bibliography of Symbolic Logic, 1666–1935 (ISBN 978-0-8218-0084-3).