Un ensemble L de mots écrits sur un alphabet A est dit récursivement énumérable (on dit aussi semi-décidable) s'il est egal à l'ensemble des mots acceptés par une machine de Turing.
Les premières propriétés des langages récursivement énumérables sont les suivantes
Un énumérateur est une machine de Turing qui est utilisée d'une manière particulière. Cette machine est lancée avec une entrée initiale vide et seules les sorties sont prises en compte. On suppose pour cela que la machine possède une bande, appelée bande de sortie sur laquelle la tête de lecture ne revient jamais en arrière. Ceci garantit que la machine écrit sur cette bande sans jamais effacer. On suppose aussi que les symboles écrits sur cette bande sont soit des symboles d'entrée (de l'alphabet d'entrée Σ qui est alors utilisé comme un alphabet de sortie) soit le symbole blanc #. Le symbole blanc est utilisé comme séparateur. Ce qui est écrit sur la bande se décompose w0#w1#w2#w3 … où w0, w1, w2, … sont des mots sur l'alphabet d'entrée Σ. On dit que les mots w0, w1, w2, … sont énumérés par la machine de Turing. Il faut remarquer que les mots w0, w1, w2, … ne sont pas nécessairement différents deux à deux. La machine peut très bien énumérer plusieurs fois le même mot.
Un langage est dit énuméré par une machine de Turing (vue comme un énumérateur) s'il est égal à l'ensemble des mots qui sont énumérés sur la bande de sortie de la machine. Ceci signifie que tous les mots qui sont écrits sur la bande de sortie appartiennent au langage considéré et que réciproquement chaque mot du langage est au moins écrit une fois sur la bande de sortie.
On a alors le résultat suivant qui dit que la notion de langage énuméré par une machine de Turing est identique à la notion de langage accepté par une machine de Turing. Ce résultat justifie la terminologie.
Théorème Un langage est récursivement énumérable si et seulement si il est énuméré par une machine de Turing.
Pour montrer ce théorème, il faut montrer que pour toute machine de Turing M, il existe un énumérateur S qui énumère exactement les mots acceptés par M et que réciproquement pour tout énumérateur S, il existe une machine de Turing M qui accepte exactement les mots énumérés par S.
Construire une machine qui accepte exactement les mots énumérés par un énumérateur S est relativement facile. Il suffit de faire une machine M qui simule l'énumérateur S sur des bandes autres que la première bande où se trouve la donnée initiale et de comparer cette donnée avec les mots énumérés sur la bande de sortie. A chaque fois que l'énumérateur termine un mot en écrivant un symbole #, celui-ci est comparé avec la donnée initiale. S'il y a égalité, la machine accepte. Sinon, elle continue à simuler l'énumérateur jusqu'à l'écriture du symbole # suivant.
Machine M avec w en entrée
Faire jusqu'à acceptation
Simuler S jusqu'à l'écriture d'un # sur la bande de sortie.
Comparer w avec le mot entre les deux derniers # de la bande de sortie.
Si égalité, alors accepter (et terminer)
Il faut remarquer que si une entrée n'est pas énumérée par S, la machine M ne s'arrête jamais. C'est dû au fait que tant qu'un mot n'est pas écrit sur la bande de sortie, il est impossible de savoir s'il sera énuméré ou pas par S.
La réciproque est un peu plus délicate. L'énumérateur S ne peut pas simplement simuler la machine sur chacun des mots afin d'écrire ceux qui sont acceptés. La machine peut ne jamais terminer sur un mot donné. Du coup, les mots suivants acceptés ne seraient jamais écrit par S. L'idée est que S va successivement écrire les mots qui sont acceptés par un calcul de longueur un, deux, trois et ainsi de suite. De plus, pour chaque longueur de calcul, l'énumérateur n'essaye pas tous les mots car il ne terminerait pas sinon. Il se contente d'essayer un nombre fini de mots, par exemple ceux qui sont de longueur inférieure à la longueur de calcul considérée. L'énumérateur utilise donc un compteur k qui est incrémenté à chaque itération. Pour chaque mot de longueur inférieure à la valeur de k, S simule la machine M sur au plus k étapes de calcul. Le mot est écrit sur la bande de sortie s'il est accepté en au plus k étapes.
Énumérateur S sans entrée
Pour k = 1, 2, 3, …
Pour chaque mot w tel que |w| ≤ k
Simuler M sur au plus k étapes de calcul.
Si M accepte en au plus k étapes, écrire w.
Il est clair que tous les mots écrits par S sont acceptés par M. Réciproquement, si un mot w est accepté par la machine M, il existe un calcul ayant un nombre m d'étapes de calcul. Pour k supérieur au maximum de |w| et de m, l'énumérateur écrit w sur la bande de sortie.
Pour montrer que l'union et l'intersection de deux langages récursivement énumérables sont aussi récursivement énumérables, on construit des machines de Turing qui acceptent l'union et l'intersection à partir des deux machines acceptant les deux langages. Comme toute machine de Turing est équivalente à une machine avec une seule bande, on peut supposer que les langages L1 et L2 sont acceptés par les machines de Turing à une seule bande M1 = (Q1, Σ1, Γ1, E1, q1,0, F1, #) et M2 = (Q2, Σ2, Γ2, E2, q2,0, F2, #). On construit alors deux machines de Turing à deux bandes M∪ et M∩ qui acceptent l'union L1 ∪ L2 et l'intersection L1 ∩ L2. L'idée générale des machines M∪ et M∩ est de simuler simultanément les machines M1 et M2. Elles effectuent alternativement une transition de la machine M1 puis une transition de la machine M2. Les transitions de M1 sont simulées sur la première bande et les transitions de M2 sont simulées sur la seconde bande.
La machine M∪ commence par recopier la donnée initiale de la première bande sur la seconde bande. Ensuite elle simule les deux machines alternativement. Son état de contrôle est alors un triplet (q1, q2, n) dont les deux premières composantes donnent les états de contrôle respectifs de M1 et M2 et la troisième composante qui est égale à 1 ou à 2 donne quelle est la prochaine machine qui effectue une transition. Son ensemble d'états est donc Q1 × Q2 × {1, 2}. L'alphabet de bande de M∪ est donc Γ1 × Γ2. Les transitions sont données par
E = { (p1, p2, 1),
(a1, a2) →
(q1, p2, 2),
(b1, a2), (x,S) |
p1, a1 →
q1, b1,x &isin E1 }
∪
{ (p1, p2, 2),
(a1, a2) →
(p1, q2, 1),
(a1, b2), (S,x) |
p2, a2 →
q2, b2,x &isin E2 }.
Lorsque la troisième composante de l'état de M∪ est égal à 1, elle effectue une transition qui modifie l'état p1 en q1 et elle écrit sur la première bande. Lorsque cette troisième composante de l'état de M∪ est égal à 2, elle effectue une transition qui modifie l'état p2 en q2 et elle écrit sur la seconde bande. Cette troisième composante passe de 1 à 2 et de 2 à 1 à chaque transition. Ceci garantit que la machine M∪ simule alternativement une transition de M1 puis une transition de M2.
La machine accepte sont entrée dès qu'une des deux machines M1 ou M2 accepte. Son ensemble d'états finaux est donc F1 × Q2 × {1, 2} ∪ Q1 × F2 × {1, 2}.
La machine M∩ est très semblable à la machine M∪. Elle commence aussi par recopier la donnée initiale de la première bande sur la seconde bande. Ensuite elle simule aussi les deux machines alternativement. Par contre, elle accepte lorsque les deux machines M1 et M2 acceptent. Lorsqu'une des deux machines M1 ou M2 accepte, la machine M∩ continue de simuler les transitions de l'autre machine. Si cette autre machine accepte aussi à son tour, alors la machine M∩ accepte finalement.
Nous allons donner explicitement un langage qui n'est pas récursivement énumérable. Ce langage est obtenu par argument diagonal.
On commence par numéroter tous les mots sur l'alphabet d'entrée pour en faire une suite w0, w1, w2, … qui contient tous ces mots. Pour cela, on les énumère par longueur croissante puis pour chaque longueur par ordre lexicographique. Si par exemple l'alphabet Σ est égal {a, b}, les premières valeurs de la suite sont w0 = ε (le mot vide), w1 = a, w2 = b, w2 = aa, w3 = ab, w4 = ba, w5 = bb, w6 = aaa, w7 = aab, … et ainsi de suite.
On fait de même avec les machines de Turing. On suppose avoir fixé un alphabet sur lequel sont codées toutes les machines de Turing. On énumére alors les machines par longueur croissante de leur codage. Pour chaque longueur de codage, les machines de Turing sont énumérées dans l'ordre lexicographique de leur codage. On obtient alors une suite M0, M1, M2, … qui contient toutes les machines de Turing.
On considère alors le langage L suivant.
L = { wi | i ≥ 0 et Mi n'accepte pas wi }
Le résultat suivant confirme que le langage L convient.
Proposition. Le langage L n'est pas récursivement énumérable.
Pour montrer que L n'est pas récursivement énumérable, on effectue un raisonnement par l'absurde. Supposons que L soit récursivement énumérable. Il est alors égal à l'ensemble des mots acceptés par une machine M. Puisque la suite M0, M1, M2, … contient toutes les machines de Turing, la machine M est égal à la machine Mk pour un certain entier k. On considère alors le mot wk ayant même numéro que la machine M et on distingue deux cas.
Dans les deux cas, on aboutit à une contradiction qui montre que l'hypothèse de départ est fausse. Le langage L n'est pas récursivement énumérable.
Un ensemble L de mots écrits sur un alphabet A est dit récursif ou décidable s'il est l'ensemble des mots acceptés par une machine de Turing (déterministe) qui n'a pas de calcul infini.
Les deux mots récursif ou décidable sont synonimes mais on parlera plutôt de langage récursif et problème décidable.
Le fait que la machine n'a pas de calcul infini signifie que quelque soit l'entrée, la machine s'arrête toujours après un nombre fini de transitions. Lorsque la machine est non déterministe, ceci signifie que pour une entrée initiale donnée, tous les calculs s'arrêtent après un nombre fini d'étapes.
Dans la définition précédente, le mot déterministe est mis entre parenthèses car on peut toujours supposer que la machine qui accepte le langage L est déterministe. On a vu qu'une machine non déterministe est toujours équivalente à une machine déterministe. De plus, si la machine non déterministe s'arrête toujours, il y a une machine déterministe équivalente qui s'arrête toujours également. Soit M une machine non déterministe qui s'arrête toujours. pour une entrée donnée, la longueur des calculs dans M est bornée. La machine déterministe qui essaye tous les calculs de M peut détecter qu'aucun calcul d'une longueur donnée n'est valide et peut alors s'arrêter.
Par contre, l'hypothèse que la machine s'arrête toujours est essentielle.
Les premières propriétés des langages récursifs sont les suivantes
Le fait qu'un langage récursif est récursivement énumérable découle directement des définitions. L'union et l'intersection de deux langages récursifs se traitent de la même manière que pour les langages récursivement énumérables. Il suffit de remarquer que si les machines M1 et M2 n'ont pas de calcul infini, alors les deux machines M∪ et M∩ contruites pour l'union et l'intersection n'ont pas de calcul infini également.
Nous commençons par montrer que le complémentaire d'un langage récursif est aussi récursif. Soit L un langage récursif accepté par une machine M sans calcul infini. Comme toute machine est équivalente à une machine qui est déterministe, on peut supposer que la machine M est déterministe. Considérons alors la machine M' obtenu en échangeant dans M les états finaux et les états non finaux. Si M est la machine (Q, Σ, Γ, E, q0, F, #), alors M' est la machine (Q, Σ, Γ, E, q0, Q\F, #). Puisque M et M' sont déterministes, il y a pour toute entrée w, un unique calcul partant de la configuration q0w. Le mot est w est alors accepté par M ou par M' si ce calcul est acceptant. Par définition des états finaux de M', ce calcul est acceptant dans M' si et seulement si il n'est pas acceptant dans M. La machine M' accepte donc le complémentaire de L.
Nous montrons maintenant que si un langage L et son complémentaire sont tous les deux récursivement énumérables, alors L et son complémentaire sont tous les deux récursifs. Ce résultat explique pourquoi les langages récursivement énumérables sont aussi appelés semi-récursifs. Supposons que L et son complémentaire sont respectivement acceptés par les machines M et M'. Pour construire une machine P sans calcul infini qui accepte L, on considère la machine P qui, pour une entrée w, simule simultanément les machines M et M' sur la même entrée w (comme on l'a déjà fait pour l'union ou l'intersection de deux langages). Dès qu'une des deux machines M ou M' accepte l'entrée, la machine P s'arrête. Si c'est la machine M qui a accepté (w est donc dans L), P accepte et si c'est la machine M' qui a accepté (w est donc le complémentaire de L), alors P rejette. Il est clair que M accepte le langage L. De plus, tout mot w appartient à L ou à son complémentaire. Pour tout entrée w, une des deux machines M ou M' doit accepter. La machine P est donc sans calcul infini.
Nous donnons maintenant un exemple de langage récursivement énumérable mais non récursif. Pour une machine de Turing M et pour un mot w, ⟨M, w⟩ dénote le codage de M et de w. On considère alors le langage L suivant.
L = { ⟨M, w⟩ | M accepte w }
Le langage L code le problème de savoir si une machine M accepte une donnée w. Ce problème est appelé problème d'acceptation. Le résultat suivant monte que ce problème est indécidable (non récursif).
Proposition. Le langage L est récursivement énumérable mais il n'est pas récursif.
Il faut remarquer que le complémentaire de L n'est pas récursivement énumérable. Sinon, L serait récursif en vertu de la propriété 4 ci-dessus. Ceci fournit un autre exemple de langage qui n'est pas récursivement énumérable.
Pour montrer que L n'est pas récursif, on effectue à nouveau un raisonnement par l'absurde. On suppose que L est récursif et on montre que cela conduit à une contradiction. Ceci signifie que le langage L est accepté par une machine de Turing A qui s'arrête toujours. On construit alors une autre machine de Turing P qui prend comme entrée le codage ⟨M⟩ d'une machine de Turing quelconque.
Machine P avec en entrée ⟨M⟩
Calculer si A accepte l'entrée ⟨M, ⟨M⟩⟩.
Accepter si A n'accepte pas (négation).
Pour montrer que la machine P ne peut pas exister, on considère ce qui se passe lors que P reçoit ⟨P⟩ comme entrée. Si P accepte ⟨P⟩, alors, A accepte l'entrée ⟨P, ⟨P⟩⟩ et justement P n'accepte pas ⟨P⟩. Si au contraire, P n'accepte pas l'entrée ⟨P⟩ alors, A n'accepte pas l'entrée ⟨P, ⟨P⟩⟩ et justement P accepte ⟨P⟩. Dans les deux cas, on aboutit à une contradiction. L'hypothèse de départ est donc fausse et la machine A n'existe pas.
Pour montrer que L est récursivement énumérable, il faut faire une machine qui accepte une entrée ⟨M, w⟩ si M accepte w. L'idée est de faire une machine qui soit capable de simuler n'importe qu'elle machine qui lui est donnée en entrée. Une telle machine est dite universelle puisqu'elle est capable de simuler n'importe qu'elle machine.
Construire une machine universelle n'est pas très difficile. Pour rendre la chose plus compréhensible, on utilise une machine à plusieurs bandes. Une première bande est utilisée pour stoker le codage ⟨M⟩ de la machine qui est passée en donnée ainsi que le codage de la donnée initiale. Une deuxième bande est utilisée pour stoker l'état courant de la machine M. Une troisième bande est utilisée pour stoker le contenu de la bande de M pendant la simulation. Sur cette bande, un symbole spécial permet de marquer la position de la tête de lecture de M.
La simulation proprement dite se fait étape de calcul par étape de calcul. La machine universelle recherche dans les transitions de M une transition qui peut être effectuée. Ensuite, la transition choisie est effectuée puis la simulation se poursuit ainsi.