Langage partiellement décidable

Récursivement énumérable

En théorie de la calculabilité, un ensemble récursivement énumérable ou semi-décidable est un ensemble qui est le domaine de définition, ou, de façon équivalente, l'image d'un fonction calculable (il faut ajouter l'ensemble vide à la dernière définition pour avoir tout à fait l'équivalence). La notion se généralise aux couples et n-uplets d'entiers et de façon plus générale aux objets qui peuvent se coder dans les entiers, mots d'un langage, formules logiques etc. Par exemple on montre que l'ensemble des programmes informatiques que l'on peut écrire dans un langage donné, ou que l'ensemble des théorèmes d'une théorie finiment axiomatisable est récursivement énumérable.

Les ensembles récursifs, on dit aussi décidables, sont tous récursivement énumérables mais la réciproque est fausse, comme le montre l'indécidabilité du problème de l'arrêt, ou celle du problème de la décision. On montre que les ensembles récursivement énumérables d'entiers sont exactement les projetés des ensembles récursifs de couples d'entiers.

En arithmétique on montre que les ensembles récursivement énumérables sont les ensembles définissables par divers types de formules n'utilisant essentiellement que des quantificateurs existentiels en tête, l'exemple le plus fin de ce genre de résultat étant la caractérisation de ces ensembles comme ensemble diophantiens, caractérisation qui conduit directement au théorème de Matiiassevitch.

La définition de Turing de l'énumérabilité

Intuitivement un ensemble est récursivement énumérable s'il existe un procédé mécanique (en gros qui peut être réalisé par un ordinateur) qui liste ses éléments. On dirait aussi qu'il existe un «programme» qui peut dire si un élément appartient à l'ensemble. Le même programme ne peut rien dire si l'élément n'appartient pas à l'ensemble.

Un peu plus précisément, un ensemble récursivement énumérable ou semi-décidable est un ensemble d'entiers tel qu'il existe une machine de Turing qui termine en acceptant sur l'entrée n si et seulement si n appartient à l'ensemble. De façon équivalente, il s'agit d'un ensemble tel qu'il existe une machine de Turing qui écrit successivement tous les éléments de l'ensemble (dans un ordre quelconque), d'où le terme (les fonctions récursives au sens de la logique mathématique sont les fonctions calculables par les machines de Turing).

Les ensembles récursivement énumérables ne sont pas forcément des ensembles récursifs : ainsi, l'ensemble des numéros des machines de Turing qui terminent sur l'entrée vide est clairement récursivement énumérable, mais n'est pas récursif, par un argument diagonal. Le théorème de Rice généralise ce résultat.

On se gardera de confondre les ensembles récursivement énumérables avec les ensembles dénombrables.

Équivalence des deux définitions de Turing

• S'il existe une machine qui affiche tous les éléments d'un ensemble, il est facile de savoir si un mot appartient ou non à l'ensemble. Attendre qu'il s'affiche. S'il s'affiche, il appartient à l'ensemble. S'il n'appartient pas à l'ensemble, il ne s'affichera pas.
• Réciproquement, s'il existe une machine M1 qui se termine quand le mot entré appartient à l'ensemble, il est possible d'obtenir une machine M2 qui affiche tous les éléments de l'ensemble. On ordonne tout d'abord tous les mots : appelons-les A,B,C.... Voici l'algorithme de M2.
  • Lancer M1 pendant un pas sur A.
  • Lancer M1 pendant deux pas sur A, puis deux pas sur B.
  • Lancer M1 pendant trois pas sur A, puis trois pas sur B, puis trois pas sur C.
  • Continuer...

Si M1 arrive à un état final, noter l'entrée comme faisant partie de l'ensemble. On obtient ainsi M2 qui écrit tous les éléments de l'ensemble, et eux seulement.

Exemples

D'une manière générale, tout algorithme A₁ admettant un paramètre entier n définit un ensemble récursivement énumérable, à savoir l'ensemble des entiers pour lequel l'algorithme se termine.

On ignore le plus souvent si un tel ensemble est récursif, c’est-à-dire s'il est possible de concevoir un algorithme A₂ terminant et répondant Oui pour les entiers de l'ensemble, et répondant Non pour les entiers n'appartenant pas à l'ensemble.

La définition de Smullyan de l'énumérabilité

Les ensembles (récursivement) énumérables peuvent être définis d’une autre façon, issue des travaux de Post et Smullyan, qui repose sur la notion de règle de production.

L’ensemble des vérités atomiques de l’arithmétique formelle

L’exemple de l’ensemble VAF0 des vérités atomiques de l’arithmétique formelle va nous servir ici pour donner un contenu concret aux définitions qui vont suivre.

VAF0 est défini avec un objet de base, 0, un opérateur unaire s, la fonction de succession, deux opérateurs binaires, + et . , l’addition et la multiplication, et deux prédicats binaires fondamentaux, = et <. On pourrait faire un choix plus restreint, 0, +, . , et =, par exemple. Mais les règles de production et les axiomes de l’arithmétique formelle sont plus faciles à énoncer avec ce choix-là.

L’unique formule initiale de VAF0 est 0=0. Ses règles de production sont les suivantes.

R1 Si x=y alors sx=sy

R2 Si x=y alors x<sy

R3 Si x<y alors x<sy

R4 Si x=y alors x+0=y

R5 Si x+y=z alors y+x=z

R6 Si x+y=z alors x+sy=sz

R7 Si x=x alors x.0=0 R8 Si x.y=z alors y.x=z

R9 Si x.y=z alors x.sy=z+x

R10 Si x=y alors y=x

R11 Si x=y et y=z alors x=z

R12 Si x=y et y<z alors x<z

R13 Si x=y et z<y alors z<x

Les éléments de VAF0 sont obtenus à partir de 0=0 en appliquant un nombre fini de fois les règles de production R1 à R13.

La définition de l’énumérabilité par des règles de production

Commençons par donner la définition des ensembles génériques, celle des ensembles énumérables en résultera immédiatement. VAF0 est un ensemble générique. Les ensembles génériques sont énumérables.

Un ensemble générique Eg est défini à partir de cinq ensembles finis, l’ensemble des objets de base, l’ensemble des opérateurs fondamentaux, l’ensemble des prédicats fondamentaux, l’ensemble des formules initiales et l’ensemble des règles de production.

Les éléments de Eg sont des formules atomiques, composées avec des noms d’objet et des prédicats fondamentaux. Les objets sont obtenus à partir des objets de base en leur appliquant les opérateurs fondamentaux. Les formules initiales sont des formules atomiques.

Pour expliciter les règles de production, il faut introduire des noms de variable, distincts de tous les noms, d’objets, d’opérateurs et de prédicats, déjà introduits. Les variables de R1 à R13 sont x, y et z. Les termes sont obtenus à partir des objets et des variables en leur appliquant les opérateurs fondamentaux. 0, x+s0 et x.(sy+s0) sont des termes. Une clause atomique est une formule atomique construite avec des prédicats fondamentaux et des termes, x+y=z par exemple.

Une règle de production est définie par un nombre n fini de clauses atomiques. Les n-1 premières clauses sont les conditions de production, ou prémisses, la dernière clause est le résultat, ou conclusion. Toutes les règles de R1 à R10 ne contiennent qu’une seule prémisse. R11, R12, et R13 en contiennent deux. On impose en général que toutes les variables mentionnées dans la conclusion aient d’abord été mentionnées dans les prémisses. On interprète une règle de production en disant que si les conditions de production sont satisfaites alors le résultat est produit.

L’ensemble générique Eg est l’ensemble toutes les formules obtenues à partir des formules initiales en appliquant un nombre fini, éventuellement très grand, de fois les règles de production.

Un système formel E est énumérable s’il existe un ensemble générique Eg et un prédicat unaire P fondamental de Eg tels que x est dans E équivaut à Px est dans Eg.

Un ensemble générique est un ensemble de formules atomiques tandis qu’un ensemble énumérable est un ensemble d’objets. Cette différence n’est pas fondamentale. Les ensembles génériques sont énumérables et leurs formules peuvent être considérées comme des objets. Plus précisément, chaque prédicat fondamental d’un ensemble générique Eg peut être considéré comme un opérateur au point de vue d’un autre ensemble générique.

Pour montrer que Eg est énumérable, définissons l’ensemble générique Eg’ avec les mêmes objets de base et les mêmes opérateurs fondamentaux que Eg. Chaque prédicat fondamental de Eg est considéré comme un opérateur fondamental de Eg’. Eg’ , quant à lui a un seul prédicat unaire, P. Chaque formule atomique f de Eg est un objet pour Eg’ . Les formules initiales de Eg’ sont les formules Pf où f est une formule initiale de Eg. Les règles de production de Eg’ sont obtenues à partir de celles de Eg en remplaçant leurs formules f par Pf. Eg est énumérable parce qu’il est défini par Eg’ et le prédicat unaire P.

La définition présente de l’énumérabilité est un peu différente de celle de Smullyan (Theory of formal systems) parce qu’ici les expressions formelles sont des formules bien formées, au sens de la grammaire des opérateurs, alors que dans la théorie de Smullyan, les expressions formelles sont toutes les suites finies de symboles. Cette différence est mineure.

L’équivalence de cette définition avec celle de Turing

Pour prouver que l’énumérabilité au sens de Smullyan est équivalente à l’énumérabilité au sens de Turing, il faut prouver (i) et (ii).

(i) Un ensemble Smullyan-énumérable est Turing-énumérable.

(ii) Un ensemble Turing-énumérable est Smullyan-énumérable.

(i) est assez évident pour tous ceux qui savent programmer un ordinateur. On peut définir un ordre sur l’ensemble de toutes les productions, celles-ci étant définies comme des suites finies de règles de production. Le problème de savoir si une formule est obtenue par une production à partir des formules initiales est décidable parce qu’une production ne produit qu’un nombre fini de formules. On programme alors l’ordinateur pour qu’il examine toutes les productions une par une. Si la formule étudiée est obtenue par une de ces productions, alors l’ordinateur s’arrête, sinon il examine la production suivante. Un ordinateur ainsi programmé s’arrête si et seulement si la formule étudiée fait partie de l’ensemble Smullyan-énumérable étudié. Un ensemble Smullyan-énumérable est donc toujours Turing-énumérable.

(ii) On considère les vérités de la forme x est l’état numéro i d’une machine dont le programme est y et dont l’état initial est z. L’état numéro zéro est défini par l’état initial de la mémoire et la position initiale de la machine. L’état numéro i+1 est obtenu après l’exécution d’une instruction sur l’état numéro i. À partir d’une définition rigoureuse du concept de machine de Turing universelle, on peut définir un ensemble Smullyan-énumérable qui contient toutes les vérités de la forme ci-dessus, ainsi que toutes celles qui précisent que la machine s’est arrêtée, pour un programme PrU d’une machine universelle. Cela prouve (ii).

Les définitions de Turing et de Smullyan permettent toutes les deux de définir des ensembles énumérables s. Mais celle de Smullyan est avantageuse au point de vue de l’axiomatique, parce que les règles de production peuvent être immédiatement traduites en axiomes. Les axiomes ainsi définis sont automatiquement vrais si le modèle est un ensemble générique défini avec ces règles de production. La définition de Smullyan simplifie souvent la tâche quand on veut trouver un modèle, un ensemble de vérités atomiques, pour des axiomes.

Références

• (fr) O. Carton, Langages formels, calculabilité et complexité. Vuibert 2008, (ISBN 978-2-7117-2077-4)
• (fr) J.-M. Autebert, Calculabilité et décidabilité. Dunod 1992, (ISBN 978-2225826320)
• (fr) P. Wolper. Introduction à la calculabilité. 3-ième édition, Dunod 2006, (ISBN 978-2100499816)

Voir aussi

• Ensemble récursif
• Dixième problème de Hilbert

Ce document provient de « R%C3%A9cursivement %C3%A9num%C3%A9rable ».