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

La notion intuitive de fonction calculable a reçu une formalisation mathématique universellement acceptée depuis les travaux de Turing, Church, Gödel, Kleene... des années 1930-1940. Mais cette formalisation est celle du versant dénotationnel de la calculabilité, c'est-à-dire celle des objets calculés par les algorithmes. Peut-on formaliser le versant opérationnel, c'est-à-dire la notion d'algorithme elle-même ? Cette question a été soulevée par Kolmogorov vers 1953, lequel a introduit à cette fin une extension de la machine de Turing dotée d'une grande flexibilité opérationnelle. Reprise par Gandy en 1980, la question a trouvé une formalisation mathématique avec les travaux de Yuri Gurevich depuis 1984.