Langage récursivement énumérable - Recursively enumerable language

En mathématiques , la logique et la science informatique , un langage formel est appelé récursivement dénombrable (également reconnaissable , partiellement décidable , semidecidable , Turing acceptable ou Turing reconnaissable ) si elle est un sous - ensemble récursivement énumérable dans l' ensemble de tous les mots possibles sur l' alphabet de le langage, c'est-à-dire s'il existe une machine de Turing qui énumérera toutes les chaînes valides du langage.

Les langages récursivement énumérables sont appelés langages de type 0 dans la hiérarchie Chomsky des langages formels. Tous les langages réguliers , sans contexte , sensibles au contexte et récursifs sont énumérables de manière récursive.

La classe de tous les langages énumérables récursivement est appelée RE .

Définitions

Il existe trois définitions équivalentes d'un langage énumérable récursivement:

1. Une langue récursivement énumérable est un sous-ensemble récursivement énumérable dans l' ensemble de tous les mots possibles sur l' alphabet de la langue .
2. Un langage récursivement énumérable est un langage formel pour lequel il existe une machine de Turing (ou une autre fonction calculable ) qui énumérera toutes les chaînes valides du langage. Notez que si le langage est infini , l'algorithme d'énumération fourni peut être choisi pour éviter les répétitions, puisque nous pouvons tester si la chaîne produite pour le nombre n est "déjà" produite pour un nombre qui est inférieur à n . Si elle est déjà produite, utilisez plutôt la sortie pour l'entrée n + 1 (récursivement), mais encore une fois, testez si elle est "nouvelle".
3. Un langage récursivement énumérable est un langage formel pour lequel il existe une machine de Turing (ou une autre fonction calculable) qui s'arrêtera et acceptera lorsqu'elle sera présentée avec n'importe quelle chaîne dans le langage en entrée, mais peut soit s'arrêter et rejeter soit boucler pour toujours lorsqu'elle sera présentée avec une chaîne pas dans la langue. Comparez cela aux langages récursifs , qui exigent que la machine de Turing s'arrête dans tous les cas.

Tous les langages réguliers , sans contexte , sensibles au contexte et récursifs sont énumérables de manière récursive.

Le théorème de Post montre que RE , avec son complément co-RE , correspond au premier niveau de la hiérarchie arithmétique .

Exemple

L'ensemble des machines de turing d'arrêt est récursivement énumérable mais non récursif. En effet, on peut faire fonctionner la machine de Turing et accepter si la machine s'arrête, donc il est récursivement énumérable. En revanche, le problème est indécidable.

Certains autres langages énumérables récursivement qui ne sont pas récursifs incluent:

• Problème de correspondance postale
• Mortalité (théorie de la calculabilité)
• Entscheidungsproblem

Propriétés de fermeture

Les langages récursivement énumérables (REL) sont fermés sous les opérations suivantes. Autrement dit, si L et P sont deux langages énumérables récursivement, alors les langages suivants sont également énumérables récursivement:

• l' étoile Kleene de L${\ displaystyle L ^ {*}}$
• la concaténation de L et P${\ displaystyle L \ circ P}$
• le syndicat ${\ displaystyle L \ cup P}$
• l' intersection . ${\ displaystyle L \ cap P}$

Les langues récursivement énumérables ne sont pas fermées sous différence d'ensemble ou complémentation. La différence d'ensemble - est récursivement énumérable si est récursive. Si est récursivement énumérable, alors le complément de est récursivement énumérable si et seulement si est également récursif. ${\ displaystyle L}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle L}$${\ displaystyle L}$${\ displaystyle L}$

Références

• Sipser, M. (1996), Introduction à la théorie de calcul , PWS Publishing Co .
• Kozen, DC (1997), Automates et calculabilité , Springer .

Liens externes

• Complexity Zoo : Classe RE
• Diapositives de cours