Institut de Recherche sur l'Enseignement des Mathématiques de Paris

« Émergence des modèles du concept de calculabilité »

Présente depuis toujours en mathématiques, la notion de fonction ou relation calculable par algorithme a trouvé sa formalisation entre les années 1920 et 1940. Dans son texte de 1936, non seulement Turing apporte la première solution convaincante mais il met en place ce qui va devenir la théorie de la calculabilité. Et il en démontre un des résultats majeurs et des plus étonnants (dixit Von Neumann) : l’existence d’une fonction calculable universelle. Le modèle de Turing a bien sûr été aussi décliné et poussé à son extrême dans plusieurs variantes, en particulier par l’école russe avec Markov et Kolmogorov. D’autres approches, a priori radicalement différentes, ont également été menées et ont été prouvées équivalentes à celle de Turing. Nous verrons l’influence considérable dans ces divers travaux de Hilbert et de son école. Et l’audace, une vingtaine d’années après les paradoxes qui avaient interpellé les mathématiciens, des approches issues des travaux de Schönfinkel : la logique combinatoire de Curry et le lambda calcul de Church et Kleene.