Chapitre 4 - Partie 1 : Repère historique - Church, Turing et les fondements du calcul

Dans les années 1930, avant même l'existence des ordinateurs, des mathématiciens cherchent à définir précisément ce qu'est « calculer ». La récursivité est au cœur de ces travaux.

---

Chronologie

Date	Événement	Personnalité
1883	Tours de Hanoï : puzzle devenu l'exemple classique d'un problème résolu récursivement.	Édouard Lucas
1930s	Lambda-calcul : modèle de calcul fondé sur les fonctions, base de la programmation fonctionnelle.	Alonzo Church
1931	Théorèmes d'incomplétude : limites de ce que l'on peut démontrer par des moyens formels.	Kurt Gödel
1936	Machine de Turing et preuve de l'indécidabilité du problème de l'arrêt.	Alan Turing
1936	Thèse de Church-Turing : les différents modèles de calcul sont équivalents en puissance.	Church et Turing
1958-1960	LISP, premier langage où la récursivité est au centre de la programmation.	John McCarthy

---

À retenir

• Church (lambda-calcul) et Turing (machine) arrivent, par des chemins différents, à la même notion de calculabilité.
• La récursivité est à la fois un outil de programmation et un concept théorique fondamental.