Calculabilité et complexité/Présentation de la leçon

La leçon présente

  • les extensions des machines de Turing, notamment aux machines de Turing non déterministes ;
  • la récursivité (au sens de Turing) et mu-récursivité (au sens de Church) ;
  • la Thèse de Church-Turing ;
  • la machine de Turing universelle et la non-calculabilité ;
  • des exemples de problèmes indécidables, classes de complexité : P, NP et EXP, NP-complétude.