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.

Travaux 

Il est connu principalement pour le développement du lambda-calcul, son application à la notion defonction 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é

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 

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 

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 etAlan Turing1.

Ses travaux influencèrent les langages de programmation fonctionnelle.

Bibliographie 

• Notices d’autorité : Système universitaire de documentation • Bibliothèque nationale de France • Fichier d’autorité international virtuel •Bibliothèque du Congrès • Gemeinsame Normdatei • WorldCat
• 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)

Sources et références 

• 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.
• un entretien avec Church sur sa période à Princeton (en anglais)

↑ http://www.math.ucla.edu/~asl/bsl/0104/0104-005.ps [archive]