Naissance de "Alonzo Church", logicien américain

Alonzo Church (14 juin 1903 Washington, D.C., - 11 août 1995 Hudson) 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 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.