# 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:
* Un llenguatge enumerable recursivament és un subconjunt enumerable recursivament del conjunt de totes les possibles paraules de l'alfabet del llenguatge.
* 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.
* 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

## Referències

* ↑ «Complexity Zoo:R - Complexity Zoo» (en anglès). Arxivat de l'original el 2017-07-21. [Consulta: 28 novembre 2018].
* ↑ Michael., Sipser,. Introduction to the theory of computation. 2a edició. Boston: Thomson Course Technology, 2006. ISBN 0534950973.
* ↑ 1951-, Kozen, Dexter,. Automata and computability. Nova York: Springer, 1997. ISBN 0387949070.
Teoria d'autòmats: llenguatge formals i gramàtica formals :
Jerarquia de ChomskyGramàtiquesLlenguatgesMàquines abstractes
Tipus-0
Tipus-1
Tipus-2
Tipus-3
Sense restriccions
(sense nom)
Sensitiva al context
Concatenació de rang
Indexada
Sistema lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
No recursives
Enumerable recursivament
Decidible
Sensible al context
Concatenació de rang$^*$
Indexat$^*$
Llenguatge lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
Lliure d'estrella
Finit
Màquina de Turing
Decider
Linealment acotat
Màquina de Turing PTIME
Pila anidada
Autòmat per subprocessos
Autòmat amb pila d'arbre restringit
Pila incrustada
Autòmat amb pila no-determinista
Autòmat amb pila determinista
Visibly pushdown
Finit
Sense comptadors(amb monoides finits aperiòdics)
Finit acíclic :
Cada categoria de llenguatges, excepte aquells marcats per $^*$, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia. :