Llenguatge enumerable recursivament

En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge enumerable recursivament (o també parcialment decidible o Turing-computable) si és un subconjunt enumerable recursivament del conjunt de totes les paraules amb l'alfabet del llenguatge. Equivalentment, un llenguatge és enumerable recursivament si existeix una màquina de Turing que accepta i s'atura amb qualsevol cadena del llenguatge.

Aquest tipus de llenguatges s'etiqueten com de tipus 0 en la jerarquia de Chomsky dels llenguatges formals. Tots els llenguatges regulars, lliures de context i recursius son llenguatges enumerables recursivament.

La classe de tots els llenguatges enumerables recursivament s'anomena RE.

Definicions

Hi ha tres definicions equivalents d'un llenguatge enumerable recursivament:

1. Un llenguatge enumerable recursivament és un subconjunt enumerable recursivament del conjunt de totes les possibles paraules de l'alfabet del llenguatge.
2. Un llenguatge enumerable recursivament és un llenguatge formal pel que existeix una màquina de Turing (o alguna altra funció computable) que enumerarà totes les cadenes vàlides del llenguatge.
3. Un llenguatge enumerable recursivament és un llenguatge formal pel que existeix una màquina de Turing (o alguna altra funció computable) que s'aturarà i acceptarà quan se li presenti qualsevol cadena del llenguatge com a entrada, però que o bé s'aturarà i rebutjarà o no s'aturarà mai quan la cadena no sigui del llenguatge. Això diferència aquest tipus de llenguatge dels llenguatges recursius, on la màquina ha d'aturar-se en tots els casos.

Tots els llenguatges regulars, lliures de context i recursius son llenguatges enumerables recursivament.

El teorema de Post demostra que la classe RE juntament amb la seva complementaria co-RE es corresponent al primer nivell de la jerarquia aritmètica.

Propietats de clausura

Els llenguatges enumerables recursivament són tancats segons les següents operacions. Si L i P són dos llenguatges enumerables recursivament, llavors els següents llenguatges també ho són:

• la clausura de Kleene $L^{*}$
• la concatenació $L\circ P$
• la unió $L\cup P$
• la intersecció $L\cap P$

Els llenguatges enumerables recursivament no estan tancats respecte a la diferència de conjunts o complementari. El conjunt diferència L - P pot ser o pot no ser enumerable recursivament. Si L és enumerable recursivament, llavors el complement d'L és enumerable recursivament si i només si L és també recursiu.

Vegeu també

• Complexitat computacional