Alonzo Church

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Alonzo et Church.

Alonzo Church

alt=Description de l'image Alonzo Church Princeton.jpg.
Naissance 14 juin 1903
Washington (États-Unis)
Décès 11 août 1995 (à 92 ans)
Hudson (États-Unis)
Nationalité Drapeau des États-Unis Américain
Champs mathématiques, logique
Institutions Université de Princeton, UCLA.
Diplôme Université de Princeton
Renommé pour lambda-calcul, thèse de Church, propriété de Church-Rosser

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

Biographie[modifier | modifier le code]

Alonzo Church est élu membre de la National Academy of Sciences en 1978[1]. Il est membre correspondant de la British Academy et membre de l’Académie américaine des arts et des sciences[1].

Church a été fait docteur honoris causa de plusieurs universités, dont un doctorat de science de Princeton[2] en 1985.

Travaux[modifier | modifier le code]

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'existence d'un problème indécidable et pour son rôle dans la création du Journal of Symbolic Logic.

Les débuts de la calculabilité[modifier | modifier le code]

Les travaux de son équipe (Church, Kleenne et Rosser) précèdent le travail d'Alan Turing sur le problème de l'arrêt. C'est Church qui le premier a l'idée que l'on peut définir le concept de fonction calculable dans un sens très large, cette idée avait déjà été entrevue par Herbrand, mais sa mort prématurée ne lui avait pas permis de la pousser plus loin. Church en a eu l'idée par le lambda-calcul. Church démontre en 1936 l'existence d'un problème insoluble par des moyens mécaniques.

Le thèse de Church[modifier | modifier le code]

Kleene démontre 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. L'équivalence démontrée ensuite qu'un certain nombre de formalisations mathématiques de la notion de traitement par des processus mécaniques ont des aptitudes en tous points semblables confirme l'intuition de Church. Cette constatation aboutit à la thèse de Church (appelée aussi thèse de Church-Turing). Elle s'appelle « thèse » parce qu'il s'agit d'un résultat qui ne peut pas être prouvé, car il affirme l'équivalence entre un concept intuitif, à savoir les fonctions mécaniquement calculables, et un concept formel, à savoir, les diverses définitions des fonctions récursives. Elle s'appelle la « thèse de Church » puisque c'est lui qui en a eu le premier l'idée. Elle s'appelle la « thèse de Church-Turing » puisque les machines de Turing donnent une véritable idée de ce que « mécanique » veut dire.

Influence et étudiants[modifier | modifier le code]

Parmi ses étudiants à Princeton, il eut des logiciens devenus célèbres, à savoir C. Anthony Anderson (en), Peter Andrews, 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[1].

Ses travaux influencèrent les langages de programmation fonctionnelle.

Publications[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. a, b et c H. B. Enderton, « IN MEMORIAM: ALONZO CHURCH 1903–1995 », The Bulletin of Symbolic Logic, vol. 1, no 4,‎ 4 décembre 1995, p. 488. (lire en ligne)
  2. (en) « Princeton University - Honorary Degrees » (since 1948) sur Princeton.edu
  3. ORRIN FRINK, JR., The calculi of lambda-conversion. By Alonzo Church. (Annals of Mathematics Studies, no. 6.) Princeton, Princeton University Press; London, Humphrey Milford and Oxford University Press, 1941. p. 169-172.

Bibliographie[modifier | modifier le code]

  • Stephen Kleene Origins of Recursive Function Theory in Annals of the History of Computing, Vol. 3 No. 1, janvier 1981. Cet article raconte la période qui a vu à Princeton l'émergence du concept de fonction récursive.
  • Wilfried Sieg Step By Recursive Step: Church's Analysis Of Effective Calculability (1997), The Bulletin of Symbolic Logic, vol 3, n°2. Discute l'émergence du concept de récursivité dans la pensée de Church.

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Liens externes[modifier | modifier le code]