Secundario

LRE y Leng.Recursivos. Computabilidad y Complejidad.

Lenguajes Recursivos y Recursivamente Enumerables

Lenguajes Recursivos y Recursivamente Enumerables
* Hemos visto que si L es un lenguaje decidible, existe una máquina M que siempre se detiene y que responde si una palabra cualquiera w pertenece a L.
* Los lenguajes decidibles también son conocidos como lenguajes recursivos
*Sin embargo, existe una calificación menos restrictiva.
* Un lenguaje L es recursivamente enumerable si existe una MT M, cuando es alimentada con alguna palabra w 2 L, se detiene diciendo S´I.
* El comportamiento no está definido cuando w 62 L.

El problema de la parada de una máquina de Turing es recursivamente enumerable.
En efecto, podemos construir una máquina M0 que recibe un par‹#(M),w› y simula la ejecución de M con w. Si M se detiene con w responde SI.
De la definición de lenguaje recursivamente enumerable, se obtiene claramente que todo lenguaje recursivo (decidible) es recursivamente enumerable, ya que un lenguaje recursivo es un caso particular de los lenguajes recursivamente enumerables.
Los lenguajes decidibles son cadenas de palabras calculables mediantefunciones recursivas por lo cual también se les llamas lenguajes recursivos.
Un lenguaje recursivamente enumerables es un lenguaje formal para el cual existe una máquina de Turing que acepta y se detiene con cualquier cadena del lenguaje. Pero que puede parar y rechazar, o bien iterar indefinidamente, con una cadena que no pertenece al lenguaje, en contraposición a los lenguajes recursivos en cuyo casose requiere que la máquina de Turing pare en todos los casos.

En aquellos problemas para los que exista algún valor en el conjunto de instancias para el que la aplicación no esté definida, NO se puede DECIDIR siempre: no se puede asegurar cual sería el comportamiento ante dichas instancias. Son problemas en los que la aplicación entre el conjunto de parámetros y el conjunto {cierto, falso} esuna función parcial. Por lo tanto, se establece la relación,

PROBLEMA DECIDIBLE = LENGUAJE RECURSIVO.

Así, estudiando si el lenguaje asociado a un determinado problema es o no es recursivo, se puede saber si el problema es o no es decidible y si se puede o no garantizar la existencia de un algoritmo de ejecución finita. Es decir, se asocia la existencia de un algoritmo a la existencia de unaMaquina de Turing que siempre pare, diciendo SI o NO. Y se usaran indistintamente ambos términos:
Existe un algoritmo → Existe una MT que siempre para.
Resulta una práctica habitual que los problemas se enuncien como problemas de decisión, de respuesta SI o NO y en los que, por lo tanto, resulta fácil transformar el enunciado en la cuestión de si un lenguaje (el asociado al enunciado) es o norecursivo y, por lo tanto, si existe o no un algoritmo que permita resolverlos. Centrarse en este tipo de problemas no supone restringir el campo de estudio, ya que normalmente cualquier problema se puede plantear como un problema de decisión y viceversa.
El objetivo de este tema seria, por lo tanto, establecer resultados que permitan afirmar si un problema es o no decidible. O, lo que es lo mismo,si el lenguaje asociado a dicho problema es o no recursivo.

Lenguaje recursivamente enumerable

En matemáticas, lógica e informática, un lenguaje recursivamente enumerable es un tipo de lenguaje formal que es también llamado parcialmente decidible o Turing-computable. Son conocidos como lenguajes tipo-0 en la Jerarquía de Chomsky.

Definición
Aunque existen varias definicionesequivalentes, ésta es una de las principales:
Un lenguaje recursivamente enumerable es un lenguaje formal para el cual existe una máquina de Turing que acepta y se detiene con cualquier cadena del lenguaje. Pero que puede parar y rechazar, o bien iterar indefinidamente, con una cadena que no pertenece al lenguaje, en contraposición a los lenguajes recursivos en cuyo caso se requiere que la máquina de...