Qu’est-ce qu’un algorithme ? Qu’est-ce qu’une fonction calculable ? Où en est-on aujourd’hui de ces deux questions posées par Turing dans son article fondateur de 1936 ? Pendant longtemps la première question a été  éclipsée par le succès de la réponse à la deuxième question.
Pourtant, si différents modèles de calculs permettent de calculer les mêmes choses, les façons dont ils les calculent, c’est à dire les familles d’algorithmes qui leur sont associées, ne sont pas comparable.
Bien sûr, on peut émuler les algorithmes d’un modèle par ceux d’un autre, mais – traduttore, traditore – il ne s’agit pas du tout des mêmes algorithmes. Styles de programmation et complexité algorithmique en montrent des différences rédhibitoires.
Existe-t-il un modèle de calcul permettant d’avoir tous les algorithmes ? Soyons plus modeste car la notion d’algorithme est très diverse: algorithmes séquentiels traditionnels, algorithmes parallèles, interactifs, analogiques, quantiques. . .
Est-il déjà possible d’avoir ceux en temps séquentiel et à pas de calcul bornés ? Yuri Gurevich a montré que c’est le cas grâce à la notion d’ASM (Abstract State Machine).
Nous ferons le point des travaux sur ces questions. Nous montrerons aussi comment les ASM permettent de modéliser non seulement les algorithmes mais aussi, de façon très simple, les classes d’algorithmes associés aux modèles de calcul. Comment le Lambda calcul donne aussi une solution.
Enfin, nous soulignerons l’impact dans ces travaux des idées de Turing. Tout particulièrement comment l’idée d’oracle est intrinsèque à celle d’algorithme, un fait a priori éloigné de l’intuition.

√ Bio : Serge Grigorieff est professeur émérite à l’université Denis Diderot – Paris 7. Sa carrière s’est partagée pour moitié entre les mathématiques et l’informatique.
Chercheur CNRS au laboratoire de Logique mathématiques à  l’université Paris 7 puis professeur de mathématiques à l’université Lyon 1, il est à l’origine, avec Michel Cosnard, alors à l’ENS de Lyon, du Magistère Informatique et modélisation créé à Lyon en 1986.
Depuis 1988, il a été professeur d’informatique à l’université Paris 7, membre du LITP puis du LIAFA. Logicien, ses travaux en informatique portent sur la théorie des automates, lacomplexité algorithmique de l’information, et la théorie des algorithmes.