Calculabilité et complexité

Automates, machines de Turing, problèmes décidables, récursivement énumérables et indécidables, classes de complexité, NP-complétude.