La réduction au problème de l'arrêt est l'outil de référence pour démontrer qu'un problème est indécidable : autrement dit, qu'aucun algorithme ne peut le résoudre correctement dans tous les cas. Une nuance mérite d'être posée d'emblée, car elle prête souvent à confusion. La méthode ne dit pas si un algorithme donné est calculable — tout algorithme écrit l'est par construction. Elle établit qu'une propriété portant sur les algorithmes n'est pas décidable.
Le point de départ : le problème de l'arrêt
L'énoncé est simple. Étant donné un programme H et une entrée I, H s'arrête-t-il lorsqu'on l'exécute sur I ? La réponse est qu'aucune procédure halts(H, I) ne peut renvoyer vrai exactement quand H termine et faux quand H boucle indéfiniment. Ce résultat, dû à Turing, est le socle de toute la théorie de la calculabilité.
Le schéma de preuve en cinq temps
1. Supposer que P est décidable
On raisonne par l'absurde. On imagine donc qu'il existe un algorithme solveP(x) capable de trancher correctement n'importe quelle instance du problème P qu'on lui soumet.
2. Construire la réduction
On montre alors comment se servir de solveP pour décider l'arrêt. Concrètement, on écrit un algorithme halts(H, I) qui appelle solveP comme sous-programme :
halts(H, I):
1. transformer (H, I) en une instance « x » du problème P
2. r = solveP(x)
3. interpréter r et renvoyer vrai ou faux
L'étape 1 est le cœur du travail. Il faut fabriquer x de telle sorte que la réponse de P sur cette instance encode exactement le comportement d'arrêt de H sur I. La manière d'y parvenir dépend entièrement de la nature de P.
3. Justifier la correction
On explique pourquoi solveP(x) renseigne sans ambiguïté sur l'arrêt de H sur I. Cette correspondance doit être vraie dans les deux sens, et pas seulement sur quelques exemples favorables.
4. Aboutir à la contradiction
Si la réduction est correcte, alors halts décide l'arrêt. Or on sait que c'est impossible. La contradiction est là.
5. Conclure
L'hypothèse de départ est donc fausse : P est indécidable.
Les difficultés réelles de l'exercice
• La transformation fait tout. Écrire le squelette de la preuve est mécanique ; inventer la bonne construction ne l'est pas. C'est là que se joue l'intelligence de la démonstration.
• La preuve est indirecte. On ne montre jamais que P est indécidable frontalement, seulement qu'il ne peut pas l'être sans rendre l'arrêt décidable.
• La quantification doit être universelle. La réduction doit fonctionner pour tout couple (H, I), et non pour un cas particulier. C'est ce qui donne à la conclusion sa portée générale.
Un exemple déroulé : le problème du vide
Énoncé. Étant donné une machine de Turing M, le langage qu'elle accepte est-il vide ? Autrement dit, existe-t-il au moins un mot que M accepte ?
Hypothèse. Supposons qu'un algorithme isEmpty(M) réponde correctement à cette question.
Réduction. Construisons à partir de H et I une machine MHI dont le comportement est le suivant : quel que soit le mot w qu'on lui présente, elle commence par simuler H sur I ; si cette simulation s'achève, elle accepte w ; sinon elle boucle sans fin.
halts(H, I):
1. M_HI = construireMachine(H, I) // telle que décrite ci-dessus
2. r = isEmpty(M_HI)
3. si r == vrai : renvoyer faux // H ne s'arrête pas sur I
sinon : renvoyer vrai // H s'arrête sur I
Pourquoi cela marche. Si H s'arrête sur I, la simulation interne se termine toujours et MHI accepte absolument tous les mots : son langage vaut Σ*, donc il n'est pas vide, isEmpty renvoie faux et halts renvoie vrai. Si H ne s'arrête pas, MHI boucle sur chaque entrée : son langage est vide, isEmpty renvoie vrai et halts renvoie faux.
Conclusion. Nous disposerions d'un décideur pour l'arrêt, ce qui est exclu. Le problème du vide est donc indécidable.
Trois remarques pour finir
La réduction établit que P est au moins aussi difficile que le problème de l'arrêt ; l'indécidabilité de ce dernier se transmet mécaniquement. La même technique, appliquée aux réductions polynomiales, sert à démontrer la NP-complétude en théorie de la complexité. Enfin, construireMachine(H, I) est une construction de l'esprit : personne ne fabrique matériellement cette machine de Turing. Ce qui compte, c'est qu'on puisse la décrire de façon algorithmique.
En résumé, la réduction au problème de l'arrêt ne contourne pas la limite : elle la révèle. En montrant qu'un solveur pour P fournirait un solveur pour une question dont l'impossibilité est démontrée, on situe P du bon côté de la frontière du calculable.