Una máquina de Turing es un dispositivo que transforma un INPUT en un OUTPUT después de algunos pasos. Tanto el INPUT como el OUPUT constan de números en código binario (ceros y unos). En su versión original la máquina de Turing consiste en una cinta infinitamente larga con unos y ceros que pasa a través de una caja. La caja es tan fina que solo el trozo de cinta que ocupa un bit (0 ó 1) está en su interior. La máquina tiene una serie de estados internos finitos que también se pueden numerar en binario.
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.
• Una máquina que decide un lenguaje recursivamente enumerable se ve de la
siguiente manera:
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 mediante funciones 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 caso se requiere que la máquina de Turing pare en todos los casos.
_ Sea M un autómata de Turing. Problema de decisión: ¿w ⟨L(M)?
Posibles respuestas (sobre dicha entrada w):
M se para en un estado final w ⟨ L(M)⟩
M se para en un estado no final w ⟨L(M)⟩
M no se para w ⟨L(M)⟩
L es un lenguaje RECURSIVO si existe un autómata de Turing M que se
para ante cualquier entrada y tal que:
_ si w ⟨ L _ M⟩ se para en un estado final
_ si w ⟨ L _ M⟩ se para en un estado no final
L es un lenguaje RECURSIVAMENTE ENUMERABLE si existe un autómata
de Turing M tal que:
_ si w ⟨L _ M⟩ se para en un estado final
_ si w diferente⟨L _ M⟩ se para en un estado no final o M no se para.
Pues, aquí ya salió mi concepto amigo "recursivamente enumerable" :) Otros cuatro puntos por esta entrada en la sesión tres.
ResponderEliminar