Calculabilité et complexité

Après avoir rappelé la notion de machine de Turing et diverses variantes, dont les machines de Turing non-déterministes, on expose d'autres paradigmes de calcul : les grammaires générales et les fonctions mu-calculables. On montre que toutes les variantes de machines de Turing sont équivalentes -- toute fonction calculable avec une variante, l'est avec tout autre variante et tout langage décidé dans une variante est décidable avec toute autre variante -- et équivalentes aux grammaires et aux fonctions mu-calculables. Toutes les preuves données sont constructives : on donne des "algorithmes" transformant une machine dans un formalisme en une machine équivalente dans un autre formalisme.

On montre ensuite des fonctions qui sont non-calculables au sens de Turing, ou des problèmes qui sont non décidables.

On se pose ensuite la question de la calculabilité en pratique en abordant les notions de classe de complexité P, NP et EXP. On définit la NP-complétude, on pose le problème "P=NP ?" et on démontre le théorème de Cook et la NP-complétude de divers problèmes classiques.