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)

MT Multicabezal. Orden creciente de bloques de 0's

Entrada:

• Ejemplo 1: B00100100010000B
• Ejemplo 2: B00100010B

Salida:

• Ejemplo 1: B00100100010000B (ACEPTA)
• Ejemplo 2: ....(RECHAZA)

Proceso:

La MT contiene 2 cabezales, situados en el primer 0 los dos. El primero se mantiene en el 0 y el segundo busca el 1 que indica el comienzo del segundo bloque de 0s. Cuando lo encuentra se situa encima del 0 adyacente y movemos los dos cabezales hacia la derecha comprobando que el bloque de la izquierda sea menor o igual que el bloque de la derecha. Si es asi, seguimos comporbando los siguientes bloques sino la rechazamos.
Pd: Acepta cadenas formadas por un solo bloque de ceros (B000B)

Click para agrandar

MT Multicinta. Contador bloques de 0's

Entrada:

• Cinta 1: B000010001010B
• Cinta 2: BBBBBB..

Salida:

• Cinta 1: B000010001010B
• Cinta 2: B0000B

Proceso:

El cabezal empieza situado en el primer 0 (cinta 1) y recorre la cadena inicial en busca de 1s. Ccada uno que encuentre precedido de 0 añade un 0 en la cinta 2. Facil...¿no?

Click para agrandar

Trabajo Semanal

Amigos del Turing,

Esta semana, las máquinas a realizar nos han parecido un poco mas sencillas que las anteriores, ¿será la practica? ¿seremos máquinas?. Para la realización de estos dos ejercicios hemos empleado el transcurso de la mañana soleada del jueves 24 de Abril. Ya preveemos los problemas que nos puede traer una determinada máquina con mas facilidad e igualmente con su resolución.

La resolución de los problemas propuestos fueron concluidas en 3 horas. Seguiremos informando...

Un saludo,
Los Máquinas del Turing.