Generador de Máquinas de Turing

En un principio teníamos la idea de que una sola máquina debía generar el código según la sintaxis de la codificación de las máquinas de Turing pero nuestra idea resultó no ser la correcta, ya que la forma de incrementar las distintas soluciones en la cinta de salida no permitiría abacarcar todos los códigos necesarios, es decir, si incrementabamos los códigos por los bloques de 0's no generabamos máquinas de varios códigos y por lo tanto solo teníamos una transición. Por lo contrario si incrementabamos los códigos de las máquinas nunca llegabamos a ejecutar distintas transiciones y esto nos hacia pensar en el generador de pares.

Dandole vueltas al tema pensamos que era importante el orden en el que debían salir las máquinas, así que decidimos imponer el orden canónico.

Solución (a):

La máquina resultante del primer apartado de la tarea estaría formado por un generador canónico (GC) cuya salida sería la entrada a un reconocedor sintactico (M1). Esta última comprobaría si la cadena entrante pertenece a su lenguaje, la sintaxis correcta de la codificación de las Máquinas de Turing. Si pertenece, acepta y la escribe en la cinta de salida sino la rechaza y espera a la siguiente cadena del generador.

Construción de Máquina:



Solución (b):

Elegimos la dos ya que aunque tengamos infinitas máquinas para infinitos problemas seguirán habiendo problemas no computables y que no pueden ser solucionados con una Máquina de Turing.

Demostración de que la intersección de dos LRs es un LR

Sean L1 y L2, L.R. => M1,M2 | L1 = L(M1), L2 = L(M2) y M1 y M2 siempre paran:

• Si x pertenece a L1, M1 acepta la cadena x y si x no pertenece a L1, M1 rechaza la cadena x.
• Si x pertenece a L2, M2 acepta la cadena x y si x no pertenece a L2, M2 rechaza la cadena x.

Sea L = L1∩L2, la maquina se presenta en la siguiente figura:
Breve explicacion de la figura. Si x pertenece a L1, M1 la mandara a M2 y si a su vez pertece a M2 devolvera si. Sino no. Si x no pertenece a L1, M1 la rechaza directamente sin pasar por M2, ya que la interseccion debe de contener "algo en comun" de L1 y L2.

Para reforzar la demostracion, segun el teorema 7.5 "El complemento de un lenguaje es recursivo y su union tambien" de este modo utilizando las leyes de Morgan se demostraria que la interseccion cumpliria la misma idea.

MT Multicinta Generador de lenguaje

L={an b2n an, con n mayor o igual a 0}

Entrada:

• Cinta1: ...BBB...
• Cinta2: ...BBB...

Salida:

• Cinta1: ...0000...
• Cinta2: ...λ$abba$aabbbbaa$...

Proceso:

El proceso de la maquina es sencillo, consiste en generar 0's en la primera cinta y su correspondiente lenguaje en la segunda cinta. Este proceso sera ciclico y sin fin, ya que estamos tratando con un generador.
Para ello utilizamos multicinta porque nos facilita de manera considerable el trabajo.


Click para agrandar

Trabajo semanal

Hola puenteros,

Pese a el desanimo que genera para trabajar una semana con puente, decidimos que el nuevo trabajo semanal debería realizarse antes de este, y así lo hicimos. El martes por la tarde, alrededor de las 6 y hasta las 7, los máquinas del Turing se reunían para solucionar, una vez más, un trabajo que no resultó ser muy laborioso y mucho menos complicado. El poder utilizar maquinas "modificadas" para el ejercicio simplifica mucho nuestra labor y esfuerzo.

Una vez terminada la faena, Vicente se encargará de dar los últimos retoques estéticos, muy importantes para nuestro blog y que en breve serán colgados para vuestro disfrute.

No seais impacientes y saber que los maquinas del Turing nunca descansan. Ser felices y portaos bien en el puente.

Atentamente,
Los Máquinas del Turing (LMT)