AutreNotion · Glossaire
Récursivement énumérable (langage)
Un langage est dit récursivement énumérable s'il existe une machine de Turing qui, pour toute entrée appartenant au langage, s'arrête et accepte, mais qui peut ne pas s'arrêter pour les entrées n'appartenant pas au langage. La classe des langages récursivement énumérables contient strictement la classe des langages récursifs (décidables). Le problème de l'arrêt, qui demande si une machine de Turing s'arrête sur une entrée donnée, est récursivement énumérable mais pas récursif.
Sommaire
Ce que vous allez apprendre
- Distinguer reconnaissance et décision par le comportement sur les entrées extérieures au langage.
- Suivre pas à pas un reconnaisseur du problème de l'arrêt.
- Comprendre pourquoi une durée d'attente finie ne prouve jamais la non-terminaison.
En clair
Imaginez un programme qui teste des mots un par un. Lorsqu'un mot appartient au langage recherché, le programme finit toujours par répondre « oui ». Pour un mot extérieur au langage, il peut répondre « non », mais il peut aussi calculer sans fin.
Un langage récursivement énumérable possède précisément ce type de reconnaissance à sens unique. L'attente a donc une signification asymétrique : une acceptation prouve l'appartenance, tandis qu'une absence de réponse ne permet pas de conclure.
Définition
Un langage est un ensemble de mots formés sur un alphabet fini. Un langage récursivement énumérable, aussi appelé reconnaissable ou semi-décidable, est un langage pour lequel il existe une machine de Turing reconnaissante. Pour chaque mot appartenant au langage, cette machine termine son calcul dans un état d'acceptation.
Pour un mot qui n'appartient pas au langage, aucune terminaison n'est exigée : la machine peut le rejeter en temps fini ou poursuivre son calcul indéfiniment. Cette condition distingue la reconnaissance d'une décision. Un langage est récursif, ou décidable, lorsqu'une machine termine sur toute entrée et répond correctement dans les deux cas. Tout langage décidable est récursivement énumérable, mais la réciproque est fausse.
Le mot « énumérable » renvoie à une caractérisation équivalente : une machine peut produire successivement tous les mots du langage, éventuellement avec répétitions, sans avoir à annoncer qu'elle a terminé. Le problème de l'arrêt fournit le cas classique d'une appartenance reconnaissable mais indécidable.
Un exemple, pas à pas
Considérons le langage ARRÊT, formé des descriptions de couples composés d'une machine de Turing et d'une entrée sur laquelle cette machine finit par s'arrêter.
Données.
Une description valide d'une machine M.
Un mot d'entrée w.
La question : M s'arrête-t-elle lorsqu'elle reçoit w ?
Une description valide d'une machine M.
Un mot d'entrée w.
La question : M s'arrête-t-elle lorsqu'elle reçoit w ?
1. Une machine reconnaissante lit la description du couple formé par M et w.
2. Elle simule ensuite, étape après étape, l'exécution de M sur w.
3. Si la simulation s'arrête, la machine reconnaissante accepte : le couple appartient à ARRÊT. Si la simulation continue indéfiniment, elle continue elle aussi et ne produit aucun verdict.
Le contrôle est direct : toute exécution finie finit par être observée après un nombre fini d'étapes. En revanche, après n'importe quel temps d'attente, une exécution encore active pourrait toujours s'arrêter plus tard. ARRÊT est donc récursivement énumérable, sans être décidable.
En pratique
En vérification de programmes, une recherche peut confirmer qu'une exécution atteint un état précis en exhibant une trace finie. Si aucune trace n'apparaît, il faut éviter de transformer l'attente en preuve d'impossibilité.
Pour reconnaître un langage, on choisit un semi-décideur lorsque seule l'appartenance doit être certifiée. Si une réponse garantie pour toute entrée est nécessaire, il faut rechercher un décideur et démontrer sa terminaison dans les deux cas.
Pour énumérer des solutions possibles, on peut entrelacer les calculs lancés sur toutes les entrées au lieu d'attendre la fin du premier. Ce partage des étapes empêche un calcul infini de bloquer l'examen des suivants.
À ne pas confondre
Langage récursivement énumérable et langage décidable. Un décideur s'arrête sur chaque entrée ; un reconnaisseur peut boucler hors du langage. Le problème de l'arrêt tranche : il est reconnaissable, mais aucun décideur ne le résout pour tous les couples machine-entrée.
Reconnaître et énumérer. Reconnaître consiste à tester une entrée donnée ; énumérer consiste à produire les membres du langage. Pour les machines de Turing, ces deux formulations caractérisent la même classe, mais les procédures et leurs sorties ne se présentent pas de la même façon.
Ensemble dénombrable et langage récursivement énumérable. Un langage sur un alphabet fini est au plus dénombrable, mais cela ne fournit pas nécessairement une procédure effective pour l'énumérer. L'existence d'une machine est le critère décisif.
Limites et pièges
Attendre n'est pas rejeter. Si le reconnaisseur n'a pas encore accepté, l'entrée peut être extérieure au langage ou simplement nécessiter davantage d'étapes. Il faut réserver « non » à un rejet effectivement obtenu.
Une borne pratique ne devient pas une décision. Interrompre une simulation après un million d'étapes donne un résultat « inconnu », pas la preuve que la machine ne s'arrêtera jamais. Un délai fixé par l'utilisateur ne remplace pas une garantie de terminaison.
Le complément change la situation. Si un langage et son complément sont tous deux récursivement énumérables, on peut faire avancer leurs deux reconnaisseurs en alternance. L'un des deux finit par accepter, ce qui fournit alors un décideur pour le langage.
Un énumérateur ne doit pas rester prisonnier d'un calcul. Tester les entrées l'une après l'autre échoue si un test boucle. Il faut entrelacer les simulations afin que chacune reçoive progressivement des étapes de calcul.
Pour aller plus loin
machine de Turing — Pour préciser le modèle de calcul qui reconnaît ou décide un langage.
Semi-décidable (problème) — Pour relier la propriété d'un problème à celle du langage qui encode ses réponses positives.
problème de l'arrêt — Pour étudier l'exemple canonique d'un problème reconnaissable qu'aucun algorithme ne décide dans tous les cas.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres