Tarea 6: Generador de códigos válidos de MT universales

¡¡Última tarea!! :-)

a)
Según el enunciado del problema se pide una máquina generadora de cadenas que serán códigos sintácticamente válidos de MT (las cadenas generadas las podría comparar con comparar con la tarea de compilar un programa, sintácticamente puede estar correcto y compilar sin errores, otra historia es que no de errores de ejecución).

Para realizar este último generador de cadenas (del curso :-P ), vamos a utilizar una MT multicinta con 2 cintas.

La posicion inical del los cabezales en las cintas serán:
Cinta1: ...B0B... (primera cadena que aceptaría el generador sería 111010101010111)
Cinta2: ...BBB...

La cinta 1 tendrá una cadena que la máquina de Turing deberá comprobar si es sintácticamente correcta, en cuyo caso se escribirá en la cinta 2. Independientemente de si es o no válida la cadena se sustituirá la cadena de la cinta 1 por la siguiente que la sucede.

Tras mucho pensar y como no se nos ocurría otra manera de tratar la cadena, la usamos como si fuera un número binario al que se le incrementa en 1 el valor. Se rechazarían muchas cadenas pero sacamos todas las válidas en orden canónico (total... hay infinitas cadenas, de las cuales infinitas cadenas se rechazarían y otras infinitas serían válidas... antes de agotarse las infinitas combinaciones posibles de cadenas nuestro sol se convierte en supernova ).

Funcionamiento:
- Desde f(q₀,1,B) hasta f(q₁₉,1,B) la MT recorre la cadena de la cinta 1. Si la recorre sin error se escribirá en la cinta 2 un delimitador "#" para separar cada una de las cadenas válidas y a su vez el cabezal de la cinta 1 se desplazará hacia la izquierda.
- Desde f(q₂₀,1,B) hasta f(q₂₀,B,B) se seguirá desplazando en la cinta 1 hacia la izquierda hasta llegar al inicio de la cadena.
- Desde f(q₂₁,0,B) hasta f(q₂₁,B,B) copia simbolo a simbolo de izquierda a derecha la cadena de la cinta 1 en la cinta 2.
- Desde f(q₂₂,0,B) hasta f(q₂₃,1,B) trata de colocar en la cinta 1 la siguiente cadena en orden canónico, tratando la cadena de la cinta 1 como un número binario se le suma 1, dejando preparada la siguiente cadena para la siguiente iteracción del generador.
- Finalmente en el estado q₂₄ el cabezal de la cinta 1 se desplaza hacia la izquierda hasta el inicio de la nueva cadena y salta al estado q₀ para comenzar de nuevo el proceso de validación de cadena.


A continuación, las transiciones del MT del "a)" de la tarea:
f(q₀,1,B) = (q₁,{1,R},{B,Z})
f(q₁,1,B) = (q₂,{1,R},{B,Z})
f(q₂,1,B) = (q₃,{1,R},{B,Z})
f(q₃,0,B) = (q₄,{0,R},{B,Z})
f(q₄,0,B) = (q₄,{0,R},{B,Z})
f(q₄,1,B) = (q₅,{1,R},{B,Z})
f(q₅,0,B) = (q₆,{0,R},{B,Z})
f(q₆,0,B) = (q₇,{0,R},{B,Z})
f(q₇,0,B) = (q₈,{0,R},{B,Z})
f(q₈,1,B) = (q₉,{1,R},{B,Z})
f(q₇,1,B) = (q₉,{1,R},{B,Z})
f(q₆,1,B) = (q₉,{1,R},{B,Z})
f(q₉,0,B) = (q₁₀,{0,R},{B,Z})
f(q₁₀,0,B) = (q₁₀,{0,R},{B,Z})
f(q₁₀,1,B) = (q₁₁,{1,R},{B,Z})
f(q₁₁,0,B) = (q₁₂,{0,R},{B,Z})
f(q₁₂,0,B) = (q₁₃,{0,R},{B,Z})
f(q₁₃,0,B) = (q₁₄,{0,R},{B,Z})
f(q₁₃,1,B) = (q₁₅,{1,R},{B,Z})
f(q₁₄,1,B) = (q₁₅,{1,R},{B,Z})
f(q₁₂,1,B) = (q₁₅,{1,R},{B,Z})
f(q₁₅,0,B) = (q₁₆,{0,R},{B,Z})
f(q₁₆,0,B) = (q₁₇,{0,R},{B,Z})
f(q₁₇,1,B) = (q₁₈,{1,R},{B,Z})
f(q₁₆,1,B) = (q₁₈,{1,R},{B,Z})
f(q₁₈,1,B) = (q₁₉,{1,R},{B,Z})
f(q₁₉,0,B) = (q₄,{0,R},{B,Z})
f(q₁₉,1,B) = (q₂₀,{1,L},{#,R})
f(q₂₀,1,B) = (q₂₀,{1,L},{B,Z})
f(q₂₀,0,B) = (q₂₀,{0,L},{B,Z})
f(q₂₀,B,B) = (q₂₁,{B,R},{B,Z})
f(q₂₁,0,B) = (q₂₁,{0,R},{0,R})
f(q₂₁,1,B) = (q₂₁,{1,R},{1,R})
f(q₂₁,B,B) = (q₂₂,{B,L},{B,Z})
f(q₂₂,0,B) = (q₂₄,{1,L},{B,Z})
f(q₂₂,1,B) = (q₂₃,{0,L},{B,Z})
f(q₂₃,0,B) = (q₂₄,{1,L},{B,Z})
f(q₂₃,1,B) = (q₂₃,{0,L},{B,Z})
f(q₂₄,0,B) = (q₂₄,{0,L},{B,Z})
f(q₂₄,1,B) = (q₂₄,{1,L},{B,Z})
f(q₂₄,B,B) = (q₀,{B,R},{B,Z})


b)
El pensamiento que creemos que se acerca más es la opción 2 ("¡Anda! salen infinitas máquinas pero va a ser que no tengo bastantes...") porque a pesar de haber infinitas máquinas puede darse el caso que el resultado no se encuentre entre todas esas máquinas (por ejemplo: cuando un programa no puede detenerse porque cae en un bucle infinito, hay infinitos resultados pero ninguno de ellos es el válido para continuar).

Tarea 5: Demostración de intersección de dos LRE.

Por las propiedades de clausura de los LRE, podemos demostrar que la intersección de dos LRE da como resultado otro lenguaje LRE.
Para el lenguaje interesección de dos Lenguajes sólo aceptará cadenas que pertenezcan a ambos lenguajes.

Para demostrarlo utilizaremos 2 MT, ambas máquinas (M1 y M2) reconocen lenguajes recursivamentes enumerables.

Procedimiento:
Tomamos una cadena x tal que si la M2 acepta la cadena, habilitará la M1. Si esta última acepta la cadena, tendremos la intersección entre L1 y L2.

Si x € L1 AND x € L2 => x € L1 intersección L2 = L