Ce que les ordinateurs ne peuvent pas faire.

• Construire un automate pour un langage régulier et prouver qu’un langage ne l’est pas (lemme de l’étoile).
• Simuler une machine de Turing et expliquer pourquoi elle capture « tout ce qui est calculable ».
• Rédiger la preuve d’indécidabilité de l’arrêt et une réduction polynomiale.
• Situer un problème (facile, NP-complet, indécidable) et adapter sa stratégie (exact, approché, heuristique).

Références : Introduction to the Theory of Computation (Sipser), programme MPI (« automates », « décidabilité et complexité »), Computational Complexity (Arora & Barak, gratuit), cours de Scott Aaronson « Quantum Computing Since Democritus ».

Les langages reconnus par automates finis sont exactement ceux décrits par les expressions régulières (Kleene) : votre re.match(r"^(0|1)*$") est compilé en automate. Un AFD lit chaque caractère une fois, en O(1) par caractère, avec une mémoire fixe : idéal pour un microcontrôleur (analyse d’une trame, module L22, ou d’un protocole : la machine à états de la séance 28 est un automate). Limite : pas de comptage non borné ; un langage avec des parenthèses équilibrées n’est pas régulier — il faut une pile.

Turing (1936) cherchait à définir « procédure mécanique ». Sa machine est minimale (un ruban, une tête, une table finie) mais peut simuler n’importe quel ordinateur — et réciproquement. Le lambda-calcul de Church, les fonctions récursives de Gödel-Kleene, Python, C, un jeu de la vie de Conway, un automate cellulaire à une dimension (règle 110) : tous équivalents. La thèse de Church-Turing affirme que tout ce qui est « effectivement calculable » l’est par une machine de Turing : ce n’est pas un théorème (on ne peut pas prouver quelque chose sur une notion informelle) mais une hypothèse jamais démentie. La machine universelle — une MT qui lit la description d’une autre MT et la simule — est l’ancêtre conceptuel de l’ordinateur à programme enregistré, et c’est aussi ce que fait MachineDeTuring.executer.

L’argument est celui de Cantor (les réels ne sont pas dénombrables) et de Gödel (une proposition qui dit « je ne suis pas prouvable ») : construire un objet qui se réfère à lui-même pour le mettre en contradiction. Autres indécidables : le 10e problème de Hilbert (existence de solutions entières d’un polynôme, Matiyasevich 1970), le problème de correspondance de Post, le pavage du plan par un jeu de tuiles, l’égalité de deux expressions régulières avec intersection et complément… et, en physique, le « gap spectral » d’un matériau (Cubitt et al., 2015). Réduction : pour montrer qu’un problème X est indécidable, on montre qu’un décideur de X permettrait de décider l’arrêt.

• P : les problèmes de décision résolubles en O(n^k) sur une machine de Turing déterministe. Tri, plus court chemin, primalité (AKS, 2002), programmation linéaire.
• NP : ceux dont une solution (« certificat ») se vérifie en temps polynomial. SAT, sous-somme, voyageur de commerce (version décision), coloration, sudoku n×n.
• NP-difficile : au moins aussi dur que tout problème de NP (tout NP s’y réduit en temps polynomial). NP-complet : NP-difficile et dans NP.
• P ⊆ NP évidemment. P = NP ? est ouvert depuis 1971 ; c’est l’un des sept problèmes du millénaire. Presque tout le monde pense P ≠ NP, sans preuve. Si P = NP avec un algorithme pratique : plus de cryptographie à clé publique, et la découverte de preuves mathématiques devient mécanique.

SAT → 3-SAT → {CLIQUE, COUVERTURE PAR SOMMETS, ENSEMBLE INDÉPENDANT} → … ; 3-SAT → 3-COLORATION ; 3-SAT → SOUS-SOMME → SAC À DOS → PARTITION ; CIRCUIT HAMILTONIEN → VOYAGEUR DE COMMERCE. Karp (1972) en a donné 21 ; on en connaît des milliers, dans tous les domaines (planification de robots, repliement de protéines, sudoku, Tetris, Super Mario). Reconnaître qu’un problème est NP-complet est utile : on arrête de chercher l’algorithme exact polynomial et on passe à la bonne stratégie : instances petites (backtracking, SAT solver, module L17), cas particuliers polynomiaux (2-SAT, module L05), approximation garantie (2-approximation de la couverture par sommets), heuristiques (2-opt, module L04), ou paramétrage (FPT).

BQP (calculable efficacement par ordinateur quantique) contient P et l’on pense qu’il ne contient pas NP : les ordinateurs quantiques ne résoudront probablement pas SAT ou le voyageur de commerce en temps polynomial. Ils battent le classique sur des problèmes de structure : factorisation et logarithme discret (Shor, 1994 : exponentiel → polynomial, d’où la cryptographie post-quantique), recherche non structurée (Grover : √N au lieu de N), simulation de systèmes quantiques (chimie, matériaux — l’application la plus prometteuse). Les machines actuelles (100-1000 qubits bruités) n’ont pas encore d’avantage pratique prouvé ; la correction d’erreurs quantique est le verrou. Autres classes : PSPACE (mémoire polynomiale : jeux à deux joueurs généralisés, échecs n×n), EXPTIME, et la hiérarchie polynomiale. On sait P ≠ EXPTIME, mais pas P ≠ PSPACE.

class AFD2:
    def __init__(self, table, initial, finaux): self.t, self.q0, self.F = table, initial, set(finaux)
    def accepte(self, mot):
        q = self.q0
        for c in mot:
            if (q, c) not in self.t: return False
            q = self.t[(q, c)]
        return q in self.F
def produit(A1, A2, op):
    etats1 = {q for q, _ in A1.t} | set(A1.t.values()); etats2 = {q for q, _ in A2.t} | set(A2.t.values())
    lettres = {c for _, c in A1.t} | {c for _, c in A2.t}; table = {}
    for p in etats1:
        for q in etats2:
            for c in lettres:
                if (p, c) in A1.t and (q, c) in A2.t: table[((p, q), c)] = (A1.t[(p, c)], A2.t[(q, c)])
    ok = (lambda p, q: p in A1.F and q in A2.F) if op == "et" else (lambda p, q: p in A1.F or q in A2.F)
    return AFD2(table, (A1.q0, A2.q0), {(p, q) for p in etats1 for q in etats2 if ok(p, q)})

NOT = {("s", "0"): ("s", "1", "D"), ("s", "1"): ("s", "0", "D"), ("s", "_"): ("f", "_", "S")}
etat_initial_not, finaux_not = "s", ["f"]
# DOUBLE : lire un 1 → le marquer X, aller à droite jusqu'au blanc, écrire 1, revenir au premier 1 non marqué ; à la fin, remplacer les X par 1
DOUBLE = {("s", "1"): ("d", "X", "D"), ("s", "Y"): ("s", "Y", "D"), ("s", "_"): ("r", "_", "G"),
          ("d", "1"): ("d", "1", "D"), ("d", "Y"): ("d", "Y", "D"), ("d", "_"): ("g", "Y", "G"),
          ("g", "1"): ("g", "1", "G"), ("g", "Y"): ("g", "Y", "G"), ("g", "X"): ("s", "X", "D"),
          ("r", "Y"): ("r", "1", "G"), ("r", "X"): ("r", "1", "G"), ("r", "_"): ("f", "_", "S")}
etat_initial_double, finaux_double = "s", ["f"]

Chaque 1 déclenche un aller-retour sur un ruban de longueur ≈ 2n : O(n) par 1, O(n²) au total. Une machine de Turing paie en temps ce que la RAM donne gratuitement (accès direct) — mais seulement polynomialement : c’est pourquoi P est le même pour tous les modèles raisonnables (thèse de Church-Turing étendue).

def partition_vers_sous_somme(L):
    s = sum(L); return (L, s // 2) if s % 2 == 0 else (L, -1)          # somme impaire : impossible → cible inatteignable
def partition_brute(L):
    s = sum(L); return s % 2 == 0 and any(sum(S) == s // 2 for r in range(len(L) + 1) for S in itertools.combinations(L, r))
def sous_somme_brute(L, c): return any(sum(S) == c for r in range(len(L) + 1) for S in itertools.combinations(L, r))
def sous_somme_pd(L, c):                      # tableau de booléens de taille c + 1 : O(n·c)
    if c < 0: return False
    atteignable = [False] * (c + 1); atteignable[0] = True
    for x in L:
        for s in range(c, x - 1, -1):
            if atteignable[s - x]: atteignable[s] = True
    return atteignable[c]

conclusions = {"(12, 20)": "pd", "(12, 20000)": "brute", "(16, 20)": "pd", "(16, 20000)": "brute"}

Avec de petits nombres, le tableau de la PD compte quelques centaines de cases et gagne largement ; avec des nombres de l’ordre de 10⁴, il dépasse 10⁵ cases à parcourir n fois et la force brute (4 096 ou 65 536 sous-ensembles) redevient plus rapide. La PD est en O(n·c) où c est la valeur de la cible ; en bits, c = 2^|c| : exponentielle en la taille de l’entrée. Un problème résoluble en temps polynomial en la valeur des nombres est faiblement NP-complet ; les fortement NP-complets (3-SAT, TSP) n’ont pas même cela.

Partition initiale {acceptants, non acceptants} ; raffiner : deux états restent dans le même bloc ssi, pour chaque lettre, leurs successeurs sont dans le même bloc ; itérer jusqu’au point fixe. Le nombre de blocs est le nombre d’états de l’AFD minimal (unique à renommage près, théorème de Myhill-Nerode).

Une MT à 2 états et 2 symboles a (2 états × 2 symboles) transitions, chacune choisie parmi (état suivant ∈ {A, B, HALT}) × (symbole ∈ {0,1}) × (direction ∈ {G, D}) : 12⁴ = 20 736 machines. Simulez chacune avec un plafond de 100 pas ; celles qui s’arrêtent donnent leur nombre de pas ; le maximum est 6. Pour n = 5, le plafond ne suffit plus : il faut prouver que certaines machines ne s’arrêtent jamais — et pour n assez grand c’est indécidable (une MT peut encoder la conjecture de Goldbach : BB(27) décide Goldbach).

Pour une MT qui s’arrête en p(n) pas, le calcul est un tableau p(n) × p(n) (temps × ruban). Variables booléennes pour chaque case × symbole × temps et chaque état × temps. Clauses : (a) exactement un symbole par case et par temps ; (b) ligne 0 = entrée ; (c) chaque fenêtre 2×3 de cases consécutives évolue selon la table (les cases loin de la tête ne changent pas) ; (d) l’état acceptant apparaît. Taille O(p(n)²) : polynomiale. Toute instance de tout problème de NP se traduit ainsi en SAT — c’est ce que signifie « SAT est NP-complet ».