Semi-décidable (problème)

Imaginez un programme chargé de surveiller un autre programme. Dès que le programme observé s'arrête, le surveillant peut répondre « oui, il s'arrête ». En revanche, tant que le calcul continue, il ignore s'il finira dans une seconde ou jamais.

Un problème semi-décidable présente cette asymétrie : les cas positifs finissent par être reconnus, mais un cas négatif peut laisser l'algorithme tourner indéfiniment. L'absence de réponse n'est donc pas une réponse « non ».

Un problème de décision demande une réponse « oui » ou « non » pour chaque instance. Il est semi-décidable lorsqu'un algorithme reconnaît toutes ses instances positives : sur chacune d'elles, il s'arrête en répondant « oui », et il ne répond jamais « oui » sur une instance négative. Sur une instance négative, ce même algorithme peut s'arrêter et répondre « non », mais il est aussi autorisé à calculer sans fin. Le terme récursivement énumérable désigne la même propriété, souvent formulée pour l'ensemble des instances positives.

Un problème décidable possède une exigence plus forte : un algorithme s'arrête sur chaque instance et fournit la bonne réponse. Il est donc toujours semi-décidable. La réciproque échoue, comme le montre le problème de l'arrêt, qui est semi-décidable sans être décidable.

Notons P le problème et P barre son complément, qui échange instances positives et négatives. Le critère fondamental est : $P\text{ est d}\acute{\text{e}}\text{cidable }⟺P\text{ et }\bar{P}\text{ sont semi-d}\acute{\text{e}}\text{cidables}P\backslash text\{\; est\; décidable\; \}\; \backslash Longleftrightarrow\; P\backslash text\{\; et\; \}\; \backslash overline\{P\}\backslash text\{\; sont\; semi-décidables\}$. En effet, deux procédures de reconnaissance lancées en parallèle finissent par reconnaître l'une des deux réponses.

On considère un reconnaisseur R du problème de l'arrêt. Les données sont les suivantes : le programme A compte de 1 à 5 puis s'arrête ; le programme B répète indéfiniment la même instruction ; R simule le programme reçu et répond « oui » dès que celui-ci s'arrête. Les deux trajectoires d'exécution rendent visible ce que R peut certifier.

1. R lance la simulation de A.
2. Après la cinquième étape annoncée, A s'arrête.
3. R détecte cet arrêt, s'arrête à son tour et répond « oui ».
4. R lance séparément la simulation de B.
5. B poursuit sa boucle ; R continue donc à simuler sans jamais produire de réponse « non ».

Le contrôle est immédiat : le cas positif A est reconnu en un temps fini. Pour B, attendre davantage ne transforme jamais le silence de R en certificat négatif. R reconnaît donc l'arrêt, mais ne décide pas tous les cas.

Pour établir qu'un problème est semi-décidable, on construit un reconnaisseur et on prouve qu'il finit par accepter chaque cas positif. Si la procédure doit aussi rejeter chaque cas négatif, il faut rechercher un algorithme de décision, plus exigeant.

Dans le problème de l'arrêt, simuler le programme testé suffit à confirmer un arrêt lorsqu'il survient. Si la simulation continue, elle ne permet pas de choisir entre un arrêt très tardif et une exécution infinie.

Pour savoir si un problème semi-décidable est en réalité décidable, on examine aussi son complément. Lorsque les cas positifs et négatifs disposent chacun d'un reconnaisseur, leur exécution en parallèle garantit qu'une réponse finira par arriver.

Problème décidable. Son algorithme doit s'arrêter sur toutes les instances, positives comme négatives. Un reconnaisseur qui répond « oui » sur A mais tourne sans fin sur B illustre seulement la semi-décidabilité. Pour l'établir, il faut prouver qu'il accepte toute instance positive et n'accepte aucune instance négative.

Problème indécidable. Ce terme signifie qu'aucun algorithme ne décide tous les cas. Il n'exclut pas la semi-décidabilité : le problème de l'arrêt est précisément indécidable et semi-décidable.

Réponse négative. Une procédure qui s'arrête en disant « non » fournit un résultat. Une procédure encore en cours n'en fournit aucun : même après une longue attente, son silence ne tranche pas le cas.

Un cas positif peut être très lent. La définition garantit seulement que le reconnaisseur finira par s'arrêter sur ce cas ; elle ne fixe aucun délai. Un temps d'attente choisi à l'avance ne constitue donc pas un test général.

Une boucle n'est pas un verdict. Sur une instance négative, le reconnaisseur peut calculer indéfiniment. Il serait erroné d'interrompre arbitrairement le calcul et d'interpréter cette interruption comme la réponse mathématique « non ».

Le complément est décisif. Si un problème et son complément sont tous deux semi-décidables, le problème est décidable. Par conséquent, pour un problème semi-décidable mais non décidable, le complément ne peut pas être semi-décidable.

Le problème de l'arrêt fournit le cas central : sa fiche détaille pourquoi l'arrêt peut être reconnu sans être décidé dans tous les cas.

La machine de Turing donne le modèle abstrait dans lequel on formalise les procédures, leurs arrêts et leurs boucles.

La fiche algorithme précise ce qu'est une procédure effective avant d'étudier les limites imposées par la semi-décidabilité.