L'indécidabilité du problème de l'arrêt

1. Le Problème de l'Arrêt : Une question simple, une réponse impossible

Au cœur du problème de l'arrêt se trouve une question d'apparence simple, mais aux implications immenses pour un informaticien :

Est-il possible de créer un programme universel qui, pour n'importe quel autre programme P et n'importe quelle entrée I, puisse déterminer si P finira par s'arrêter ou s'il tournera en boucle à l'infini ?

Un tel programme serait un outil de débogage ultime. Il pourrait détecter toutes les boucles infinies, prouver des conjectures mathématiques (comme celle de Goldbach, en vérifiant si un programme qui cherche un contre-exemple s'arrête un jour), et bien plus encore. Malheureusement, nous allons prouver qu'un tel outil universel ne peut pas exister.

Formalisation du Problème

Pour raisonner formellement, nous traduisons ce problème en termes de langages et de machines de Turing.

Le problème de l'arrêt est formalisé par le langage $A_{TM}$ (parfois noté $H$ ou HALT) :

Ici, $⟨M,w⟩$ est une chaîne de caractères qui encode la machine $M$ et son entrée $w$. "Décider" le problème de l'arrêt revient à construire une machine de Turing qui décide le langage $A_{TM}$.

$A_{TM}$ est Récursivement Énumérable (Reconnaissable)

Avant de prouver que $A_{TM}$ n'est pas décidable, montrons qu'il est au moins reconnaissable. On peut construire une machine de Turing universelle, appelons-la $U$, qui reconnaît $A_{TM}$ comme suit :

1. Sur une entrée $⟨M,w⟩$, $U$ simule l'exécution de $M$ sur $w$.
2. Si, au cours de la simulation, $M$ atteint un état d'acceptation, $U$ s'arrête et accepte.
3. Si, au cours de la simulation, $M$ atteint un état de rejet, $U$ s'arrête et rejette.
4. Si $M$ boucle à l'infini sur $w$, alors $U$ boucle également à l'infini.

Le comportement de $U$ correspond exactement à la définition d'un reconnaisseur pour $A_{TM}$. La question cruciale est donc : peut-on améliorer $U$ pour qu'elle s'arrête toujours, même lorsque $M$ boucle ? La réponse est non.

2. La Preuve de l'Indécidabilité

Nous allons démontrer que $A_{TM}$ est indécidable en utilisant un raisonnement par l'absurde. La technique employée, la diagonalisation, a été popularisée par Georg Cantor pour montrer qu'il existe différentes "tailles" d'infinis, et a été adaptée par Turing d'une manière magistrale.

L'Intuition : Le Paradoxe du Menteur

Pour saisir l'essence de la preuve, commençons par une vidéo qui en explique la logique de manière très intuitive, en la reliant au célèbre paradoxe du menteur ("Je mens").

La Construction Formelle

Maintenant, formalisons ce que vous venez de voir.

Étape 1 : L'hypothèse (par l'absurde)

Supposons que $A_{TM}$ est décidable.
Cela implique qu'il existe une machine de Turing $H$ (le "Halting Decider") qui décide $A_{TM}$. Par définition d'un décideur, $H$ s'arrête toujours et se comporte comme suit :

Étape 2 : La machine contradictoire

À partir de $H$, nous construisons une nouvelle machine de Turing, appelons-la $D$ (pour "Diagonale" ou "Démoniaque").

• Entrée de $D$ : $D$ prend en entrée l'encodage d'une seule machine, $⟨M⟩$.
• Fonctionnement de $D$ :
  1. $D$ exécute $H$ sur l'entrée $⟨M,⟨M⟩⟩$. C'est-à-dire que $D$ demande à $H$ : "La machine $M$ s'arrête-t-elle et accepte-t-elle si on lui donne son propre code comme entrée ?".
  2. $D$ inverse la réponse de $H$ :
     • Si $H$ accepte, $D$ entre dans une boucle infinie (ou rejette ; le point crucial est qu'elle n'accepte pas).
     • Si $H$ rejette, $D$ s'arrête et accepte.

Puisque nous avons supposé que $H$ est un décideur (s'arrête toujours), notre machine $D$ est aussi une machine de Turing parfaitement valide.

Le schéma suivant résume la construction de $D$ (appelée CM, Contradictory Machine) à partir de $H$ (appelée HM, Halting Machine).

Étape 3 : La Contradiction

Puisque $D$ est une machine de Turing, elle possède son propre encodage, $⟨D⟩$. Que se passe-t-il si nous donnons $⟨D⟩$ comme entrée à la machine $D$ elle-même ?

Analysons le comportement de $D(⟨D⟩)$ :

• Cas 1 : Supposons que $D$ accepte son entrée $⟨D⟩$.

  • En regardant la définition de $D$, pour qu'elle accepte, il faut que l'appel interne à $H(⟨D,⟨D⟩⟩)$ ait renvoyé "rejette".
  • Mais si $H$ rejette $⟨D,⟨D⟩⟩$, cela signifie (par définition de $H$) que $D$ n'accepte pas son entrée $⟨D⟩$.
  • Contradiction : Nous avons supposé que $D$ accepte $⟨D⟩$ et nous en avons déduit que $D$ n'accepte pas $⟨D⟩$.

• Cas 2 : Supposons que $D$ n'accepte pas son entrée $⟨D⟩$ (elle boucle ou rejette).

  • En regardant la définition de $D$, pour qu'elle n'accepte pas, il faut que l'appel interne à $H(⟨D,⟨D⟩⟩)$ ait renvoyé "accepte".
  • Mais si $H$ accepte $⟨D,⟨D⟩⟩$, cela signifie (par définition de $H$) que $D$ accepte son entrée $⟨D⟩$.
  • Contradiction : Nous avons supposé que $D$ n'accepte pas $⟨D⟩$ et nous en avons déduit que $D$ accepte $⟨D⟩$.

Dans les deux cas, nous aboutissons à une absurdité logique. L'existence même de la machine $D$ est paradoxale. Comme la construction de $D$ à partir de $H$ est logiquement correcte, la seule faille dans notre raisonnement est l'hypothèse initiale.

Conclusion de la preuve : L'hypothèse selon laquelle un décideur $H$ pour $A_{TM}$ existe est fausse. Par conséquent, le langage $A_{TM}$ est indécidable.

Visualisation par la Diagonale

Le nom "diagonalisation" vient d'une manière plus visuelle de présenter cette preuve. Imaginez un tableau infini où les lignes sont toutes les machines de Turing $(M_1,M_2,\dots )$ et les colonnes sont tous les encodages de ces machines $(⟨M_1⟩,⟨M_2⟩,\dots )$. La case (i, j) du tableau contient le résultat de $H(⟨M_i,⟨M_j⟩⟩)$.

Notre machine $D$ est construite en regardant la diagonale de ce tableau (les cases (i, i)) et en inversant chaque résultat. Le paradoxe vient du fait que $D$ doit elle-même se trouver quelque part dans la liste des machines (disons, à la ligne $k$), mais par construction, son comportement sur l'entrée $⟨M_k⟩$ (c'est-à-dire $⟨D⟩$) doit être différent de celui de la ligne $k$ sur la diagonale.

La vidéo suivante explique cette construction en détail.

Consolidation : La Preuve Formelle

Pour finir, il est indispensable de maîtriser la version entièrement formelle de cette preuve, en utilisant la notation standard ${\varphi }_i$ pour désigner la fonction calculée par la i-ème machine de Turing. C'est le niveau de rigueur attendu à l'Agrégation.

Conclusion : La Première Limite Fondamentale

Aujourd'hui, nous avons non seulement défini le problème de l'arrêt, mais nous avons surtout démontré formellement qu'il est impossible de le résoudre algorithmiquement.

Points clés à retenir :

• Le problème de l'arrêt est formalisé par le langage $A_{TM}=\{⟨M,w⟩\mid M\text{ accepte }w\}$.
• $A_{TM}$ est reconnaissable (on peut simuler $M$ sur $w$) mais indécidable.
• La preuve de l'indécidabilité repose sur un raisonnement par l'absurde appelé diagonalisation : on suppose l'existence d'un décideur de l'arrêt ($H$), on l'utilise pour construire une machine contradictoire ($D$) qui fait le contraire de ce que le décideur prédit sur elle-même, menant à un paradoxe.
• Nous avons donc prouvé que la classe des langages décidables est un sous-ensemble strict de la classe des langages reconnaissables.

Le fait que le problème de l'arrêt soit indécidable est bien plus qu'une curiosité théorique. C'est la première brique qui nous permet de construire tout un édifice de problèmes "impossibles". Dans la prochaine leçon, nous introduirons la notion de réduction, une technique puissante qui permet de prouver l'indécidabilité d'autres problèmes en montrant qu'ils sont "au moins aussi difficiles" que le problème de l'arrêt.