Alonzo Church - Définition

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

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 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à 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. 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 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.

Parmi ses étudiants à Princeton, il eut des logiciens devenus célèbres, à savoir 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 et Alan Turing. See (lien).

Ses travaux influencèrent les langages de programmation fonctionnelle.

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 à 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)