Séance Séminaire

Séminaire de culture générale Mathématique

P=NP par les Machines de Turing

L’objet central de cet exposé est la notion de Machine de Turing, imaginée par Alan Turing en 1936. J’en présenterai la définition, et je montrerai en quoi cette notion est plus expressive que d’autres types de modèles de calculs et de langages, et en quoi on peut considérer que les machines de Turing modélisent (ou formalisent) la notion de procédure effective, c’est-à-dire d’algorithme. Ceci permettra d’aborder la question : tout problème peut-il être résolu algorithmiquement ? Et d’introduire la notion d’indécidabilité, ou de non-calculabilité. Nous nous tournerons ensuite vers les questions de complexité que permettent d’étudier les machines de Turing, et je présenterai les classes P et NP permettant de comprendre la fameuse conjecture P = NP, considérée comme l’une des plus importante de l’informatique théorique. Cet exposé ne demandera aucune connaissance préalable avancée en mathématiques ou en informatique, si ce n’est de bonnes bases de logique. Il s’appuiera essentiellement sur l’ouvrage pédagogique pour la licence « Introduction à la calculabilité » de Pierre Wolper (Dunod).