Sites Inria

Evénement

Une question résiduelle après Turing : formaliser la notion d'algorithme

  Serge Grigorieff professeur  émérite à l’université Denis Diderot vous questionnera sur ce qu’est un algorithme et 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. Venez en débattre avec lui !

  • Date : 31/05/2012
  • Lieu : Ircica
  • Intervenant(s) : Serge Grigorieff
  • Organisateur(s) : Coloquium Polaris

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 ? 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 comparables.
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.

La conférence se tiendra de 14h à 15h30 dans l'amphithéâtre de l'Ircica à Villeneuve d'Ascq.

__

(*=) "traduire, c'est toujours trahir"

Localisation

Mots-clés : Serge Grigorieff Turing Colloqium Polaris Centre de recherche Inria Lille - Nord Europe

Haut de page

Suivez Inria