problème de la décision

Prenez un programme et une donnée précise. La question « ce programme finira-t-il par s'arrêter avec cette donnée ? » n'admet que deux réponses : oui ou non. Une question construite ainsi est un problème de décision.

Le défi n'est pas seulement de répondre dans un exemple. Il faut savoir si une même procédure peut donner la bonne réponse, puis s'arrêter, pour toutes les entrées autorisées. Si elle existe, le problème est décidable. Sinon, il est indécidable.

Un problème de décision associe à chaque entrée autorisée une réponse parmi deux valeurs, généralement « oui » et « non ». Une instance est une entrée particulière du problème. Par exemple, pour le problème de l'arrêt, l'instance réunit un programme donné et une entrée donnée ; la question est de savoir si cette exécution finit.

En théorie de la calculabilité, le problème est décidable lorsqu'il existe un algorithme, ou une machine de Turing, qui s'arrête sur toute entrée autorisée et fournit toujours la réponse correcte. Si aucun tel algorithme n'existe, il est indécidable. Le problème de l'arrêt et le problème de correspondance de Post appartiennent à cette seconde catégorie. Dans ce dernier, on demande si des dominos portant deux mots peuvent être répétés et ordonnés de sorte que les concaténations du haut et du bas coïncident.

En théorie de la complexité, l'étude porte sur les problèmes déjà décidables. Elle compare les ressources de calcul, notamment le temps et la mémoire, nécessaires aux algorithmes qui les résolvent. La forme binaire de la réponse ne préjuge donc ni de l'existence d'un algorithme général ni de son coût.

Considérons un programme qui reçoit un entier naturel nommé n. Tant que n est strictement positif, il lui retranche 1 ; lorsqu'il atteint 0, le programme s'arrête. L'instance choisie donne la valeur initiale 3. La question de décision est : « ce programme s'arrête-t-il pour l'entrée 3 ? »

1. Le programme lit 3.
2. Trois passages dans la boucle produisent successivement 2, puis 1, puis 0.
3. La condition « strictement positif » devient fausse.
4. Le programme atteint son arrêt.

La réponse pour cette instance est donc oui. Le contrôle consiste à recompter les trois retraits : $3\to 2\to 1\to 03\; \backslash to\; 2\; \backslash to\; 1\; \backslash to\; 0$. Plus généralement, toute entrée naturelle n atteint 0 après exactement n passages. Cette preuve vaut pour ce programme précis ; elle ne fournit pas une procédure capable de trancher l'arrêt de n'importe quel programme.

Pour étudier une propriété informatique, on la formule d'abord comme une question à deux réponses. Sur une entrée fixée, le geste consiste à identifier précisément ce qui ferait répondre « oui » et ce qui ferait répondre « non ».

En calculabilité, on cherche ensuite une procédure qui réponde correctement et s'arrête pour toutes les entrées. Si cette garantie universelle est impossible, on classe le problème comme indécidable au lieu de chercher à mesurer la rapidité d'un solveur général inexistant.

Lorsque le problème est décidable, l'analyse peut porter sur son coût. On compare alors les algorithmes selon le temps ou la mémoire qu'ils demandent, plutôt que selon la seule forme « oui/non » de leur résultat.

Un problème de décision demande un verdict binaire. Un problème de recherche demande au contraire de produire un objet qui satisfait les conditions. « Existe-t-il une séquence de dominos dont les deux lectures coïncident ? » est une décision ; « donnez une telle séquence » demande un objet.

Il ne faut pas non plus confondre décidabilité et complexité. La première demande si un algorithme correct termine sur toute entrée. La seconde compare le temps ou la mémoire nécessaires lorsque le problème est décidable. Une réponse toujours obtenue peut rester très coûteuse.

Connaître une instance ne tranche pas le problème général. On peut prouver que le programme de l'exemple s'arrête pour l'entrée 3 sans disposer d'un algorithme qui décide l'arrêt pour tout programme et toute entrée. Il faut toujours vérifier la portée du verdict.

Indécidable ne signifie pas que chaque cas reste sans réponse. Le blocage porte sur l'existence d'une procédure unique, correcte et terminante pour toutes les entrées. Pour une instance particulière, un arrêt observé suffit à répondre oui ; il ne résout pas le problème universel.

Deux réponses ne signifient pas deux calculs faciles. La sortie ne contient qu'un verdict, mais les ressources nécessaires pour l'obtenir peuvent varier fortement. Après avoir établi la décidabilité, il reste donc à étudier séparément le temps et la mémoire.

Le problème de l'arrêt donne le cas emblématique d'une question binaire pour laquelle aucun décideur général n'existe.

La machine de Turing fournit le modèle abstrait employé pour formuler avec précision l'existence d'une procédure de décision.

La fiche algorithme précise ce qu'est une suite d'opérations finies et éclaire le rôle de la terminaison dans la décidabilité.