Esta semana, el lunes a las 8:45 aproximadamente pensamos como resolver el último entregable y nos pusimos a dibujar la máquina.
El miercoles terminamos el entregable y lo colgamos en el blog.
El jueves por la tarde correjimos la tarea 5 y 6 a los grupos 3 y 9 respectivamente.
jueves, 29 de mayo de 2008
miércoles, 28 de mayo de 2008
Última tarea
a) ¿Cómo se podría construir un generador de todos los códigos de Máquinas de Turing sintácticamente correctos?
Para la construcción de esta máquina se necesita un generador canónico para generar las posibles Máquinas de Turing con el alfabeto (0, 1). Y una máquina que nos diga si es una MT, que podemos usar el Autómata Finito que vimos en clase.
El generador va generando cadenas que se le pasan al Reconocedor de MT's si este las acepta se escriben en la cinta de salida separadas por #.
b)Una construcción similar a la del apartado anterior (o un razonamiento similar al que sustenta dicha construcción) permitió a Turing formular un importante resultado asociado al concepto de Computabilidad en el contexto del Entscheidungsproblem... ¿qué pensamiento estaría más cercano a su reacción inicial?
1) "'¡Hala, qué jartá de máquinas...! Malo será que no encuentre una que me apañe..."
2) "¡Anda!, salen infinitas máquinas, pero va a ser que no tengo bastantes..."
3) "Church se va a morir de envidia: dónde va a parar, mucho más bonita esta colección de máquinas que el peñazo del lambda-calculus...".
La respuesta correcta es la 2, pensando en que hay infinitas máquinas, pero se dio cuenta que no tendría suficientes llego a la conclusión que hay problemas que no se pueden resolver de manera automatizada, es decir que no son computables.
Para la construcción de esta máquina se necesita un generador canónico para generar las posibles Máquinas de Turing con el alfabeto (0, 1). Y una máquina que nos diga si es una MT, que podemos usar el Autómata Finito que vimos en clase.
El generador va generando cadenas que se le pasan al Reconocedor de MT's si este las acepta se escriben en la cinta de salida separadas por #.
b)Una construcción similar a la del apartado anterior (o un razonamiento similar al que sustenta dicha construcción) permitió a Turing formular un importante resultado asociado al concepto de Computabilidad en el contexto del Entscheidungsproblem... ¿qué pensamiento estaría más cercano a su reacción inicial?
1) "'¡Hala, qué jartá de máquinas...! Malo será que no encuentre una que me apañe..."
2) "¡Anda!, salen infinitas máquinas, pero va a ser que no tengo bastantes..."
3) "Church se va a morir de envidia: dónde va a parar, mucho más bonita esta colección de máquinas que el peñazo del lambda-calculus...".
La respuesta correcta es la 2, pensando en que hay infinitas máquinas, pero se dio cuenta que no tendría suficientes llego a la conclusión que hay problemas que no se pueden resolver de manera automatizada, es decir que no son computables.
martes, 13 de mayo de 2008
Demostración de que la operacion interseccion es de clausura para Lenguajes Recursivos
Demostración por construcción:
La intersección de LR' s es un LR.
Sea L1 un LR → Existe al menos una M 1 | L1( M1 ) y M1 siempre para.
Sea L1 un LR → Existe al menos una M 2 | L2( M2) y M2 siempre para.
Se considera L= L1 ∩ L2 = {x | x pertenece a L1 y x pertenece a L2 }
¿Existe al menos una M | L=L(M) y M siempre para ?
La MT M
-Para y acepta si x pertenece a L1 y si x pertenece a L2.
-Para y rechaza, si x no pertenece a L1 o si x no pertenece a L2.
-L1 ∩ L2 es un LR.
También podemos hacer una construcción en paralelo:
La intersección de LR' s es un LR.
Sea L1 un LR → Existe al menos una M 1 | L1( M1 ) y M1 siempre para.
Sea L1 un LR → Existe al menos una M 2 | L2( M2) y M2 siempre para.
Se considera L= L1 ∩ L2 = {x | x pertenece a L1 y x pertenece a L2 }
¿Existe al menos una M | L=L(M) y M siempre para ?
La MT M
-Para y acepta si x pertenece a L1 y si x pertenece a L2.
-Para y rechaza, si x no pertenece a L1 o si x no pertenece a L2.
-L1 ∩ L2 es un LR.
También podemos hacer una construcción en paralelo:
lunes, 12 de mayo de 2008
Demostración de que la operacion interseccion es de clausura para Lenguajes Recursivos
Demostracion por leyes de De Morgan:
Sea L1 un LR -> Existe al menos una M1 | L1=L(M1) y M1 siempre para.
Sea L2 un LR -> Existe al menos una M2 | L2=L(M2) y siempre para.
Sea L3 un LR -> Existe al menos una M3 | L3=L(M3)=(L1)' y siempre para.
Sea L4 un LR -> Existe al menos una M4 | L3=L(M4)=(L2)' y siempre para.
Sea L1 U L2 un LR -> (L1)' U (L2)' también lo es--> ((L1)' U (L2)')' es un LR --> L1 intersectado con L2 también lo es.
A continuación lo demostraremos mediante una contrucción de una MT que intersecte dos LR:
continuara....
Sea L1 un LR -> Existe al menos una M1 | L1=L(M1) y M1 siempre para.
Sea L2 un LR -> Existe al menos una M2 | L2=L(M2) y siempre para.
Sea L3 un LR -> Existe al menos una M3 | L3=L(M3)=(L1)' y siempre para.
Sea L4 un LR -> Existe al menos una M4 | L3=L(M4)=(L2)' y siempre para.
Sea L1 U L2 un LR -> (L1)' U (L2)' también lo es--> ((L1)' U (L2)')' es un LR --> L1 intersectado con L2 también lo es.
A continuación lo demostraremos mediante una contrucción de una MT que intersecte dos LR:
continuara....
domingo, 27 de abril de 2008
Maquina de Turing generadora
L={ anb2nan, con n mayor o igual a 0} .
En la cinta 2, se mostrarán las cadenas generadas del lenguaje.
Se empieza en q1.
En la cinta 2, se mostrarán las cadenas generadas del lenguaje.
Se empieza en q1.
| Multicinta | (0, B) | (1, B) | (B, B) |
| q1 | {q1, (0, R), (B, Z)} | {q2, (1, R), (B, Z)} | {q2, (0, R), (B, Z)} |
| q2 | {q2, (1, R), (B, Z)} | {q3, (1, L), (a, R)} | |
| q3 | {q3, (0, L), (b, R)} | {q3, (1, L), (a, R)} | {q4, (B, R), (B, Z)} |
| q4 | {q4, (0, R), (b, R)} | {q4, (1, R), (a, R)} | {q5, (B, L), (#, R)} |
| q5 | {q5, (0, L), (B, Z)} | {q5, (1, L), (B, Z)} | {q1, (0, R), (B, Z)} |
Máquina de Turing para saber si un bloque de ceros está ordenador crecientemente
Ejemplo de cadena que debe aceptar: B01000010000000B
Ejemplo de cadena que debe rechazar: B010000100B
Ejemplo de cadena que debe rechazar: B010000100B
| Principal | 0 | 1 | $ | B | X |
| q0 | (q1, B, R) | (q2, 0, L) | |||
| q1 | (q1, 0, R) | (q1, 1, R) | (q0, $, R) | ||
| q2 | (q2, 0, L) | (q2, 1, L) | (q2, $, L) | (q3, B, R) | |
| q3 | (q4, B, R) | (q5, B, R) | (q13, B, R) | ||
| q4 | (q4, 0, R) | (q4, 1, R) | (q4, $, R) | (q2, 0, L) | |
| q5 | (q6, X, R) | (q9, 1, R) | |||
| q6 | (q6, 0, R) | (q6, 1, R) | (q6, $, R) | (q7, B, L) | |
| q7 | (q8, B, L) | (q11, $, L) | |||
| q8 | (q8, 0, L) | (q8, 1, L) | (q8, $, L) | (q5, X, R) | |
| q9 | (q9, 0, R) | (q9, 1, R) | (q10, $, R) | ||
| q10 | (q11, B, L) | ||||
| q11 | (q11, 0, L) | (q11, 1, L) | (q11, $, L) | (q12, 0, L) | |
| q12 | (q3, B, R) | (q12, 0, L) | |||
| q13 | (q13, B, R) | (q14, B, L) | |||
| q14 |
| Multicabezal | (0, 0) | (1, 0) | (0, 1) | (1, 1) | (0, B) | (1, B) |
| q0 | {q0, (0, Z), (0, R)} | {q1, (0, Z), (1, R) | ||||
| q1 | {q1, (0, R), (0, R)} | {q2, (1, R), (0, R)} | {q1, (1, R), (1, R)} | {q3, (0, Z), (B, Z)} | {q3, (1, Z), (B, Z)} | |
| q2 | {q2, (0, Z), (0, R)} | {q1, (0, Z), (1, R)} | ||||
| q3 |
Maquina de Turing para contar el número de parámetros.
Cinta de entrada: B00010001010000100B
Cinta de salida:B00000B
A continuación ponemos la tabla de transición de la MT "normal". El cabezal inicialmente está posicionado sobre el primer cero. El estado final es el q8.
La tabla de transición siguiente, corresponde al modelo de Máquina de Turing multicinta para resolver el mismo problema que el anterior. En la cinta 2 guardamos la salida.
Cinta de salida:B00000B
A continuación ponemos la tabla de transición de la MT "normal". El cabezal inicialmente está posicionado sobre el primer cero. El estado final es el q8.
| Principal | 0 | 1 | $ | B |
| q0 | (q0, 0, R) | (q0, 1, R) | (q1, $, L) | |
| q1 | (q1, 0, L) | (q1, 1, L) | (q2, B, R) | |
| q2 | (q3, B, R) | |||
| q3 | (q3, B, R) | (q4, B, R) | (q7, B, R) | |
| q4 | (q4, 0, R) | (q4, 1, R) | (q5, $, R) | |
| q5 | (q5, 0, R) | (q6, 0, L) | ||
| q6 | (q6, 0, L) | (q6, 1, L) | (q6, $, L) | (q2, B, R) |
| q7 | (q7, 0, R) | (q8, 0, R) | ||
| q8 |
La tabla de transición siguiente, corresponde al modelo de Máquina de Turing multicinta para resolver el mismo problema que el anterior. En la cinta 2 guardamos la salida.
| Multicinta | (0, B) | (1, B) | (B, B) |
| q0 | {q1, (0, R), (0, R)} | ||
| q1 | {q1, (0, R), (B, Z)} | {q0, (1, R), (B, Z)} | {q2, (B, Z), (B, Z)} |
| q2 |
lunes, 14 de abril de 2008
Diario de la semana del 7-04-08 al 18-04-08
Esta semana quedamos el lunes, para empezar a enfocar como resolveríamos las dos Máquinas de Turing (la simple y la multicinta para sacar los divisores de un número), también tratamos un poco por encima la exposición que teníamos que hacer sobre que las MT “normales” tienen el mismo poder computacional que las MT no deterministas y al revés. Eso fue de 8:45 hasta cerca de las 10 que teníamos la clase de TALF.
Al enterarnos que teníamos que dar la exposición citada anteriormente el viernes próximo, creyendo primero que era el otro viernes. El martes a las 10 quedamos media hora para hablar como lo haríamos y para que buscáramos información por Internet.
El miércoles, a las 11 aproximadamente empezamos a realizar el powerpoint hasta las 13 horas. Y por la tarde continuamos haciendo el powerpoint y el guión que usaríamos donde poníamos los puntos a recalcar sobre las distintas diapositivas.
El jueves quedamos a las 10h nos repartimos las partes de la charla a suertes e hicimos un pequeño ensayo.
El viernes hicimos la exposición a la clase del tema anteriormente preparado.
Al enterarnos que teníamos que dar la exposición citada anteriormente el viernes próximo, creyendo primero que era el otro viernes. El martes a las 10 quedamos media hora para hablar como lo haríamos y para que buscáramos información por Internet.
El miércoles, a las 11 aproximadamente empezamos a realizar el powerpoint hasta las 13 horas. Y por la tarde continuamos haciendo el powerpoint y el guión que usaríamos donde poníamos los puntos a recalcar sobre las distintas diapositivas.
El jueves quedamos a las 10h nos repartimos las partes de la charla a suertes e hicimos un pequeño ensayo.
El viernes hicimos la exposición a la clase del tema anteriormente preparado.
Máquina de Turing Multicinta de Obtener los Divisores:
| Subrutina | (0, 0, B) | (0, B, B) | (B, 0, B) | (B, B, B) | (0, X, B) | (B, X, B) |
| qi | (qi, (0, R), (X, R), (B, Z)) | (qi2, (0, Z), (B, L), (B, Z)) | (qi3, (B, Z), (B, L), (B, Z)) | |||
| qi2 | (qi, (0, Z), (B, R), (B, Z)) | (qi3, (B, Z), (B, R), (B, Z)) | (qi2, (0, R), (0, L), (B, Z)) | |||
| qi3 | (qi7, (B, Z), (0, Z), (B, Z)) | (qi4, (B, Z), (X, Z), (B, Z)) | ||||
| qi4 | (qi5, (B, Z), (B, R), (B, Z)) | (qi4, (B, Z), (0, L), (0, R)) | ||||
| qi5 | (qi6, (B, L), (B, R), (B, Z)) | (qi11, (B, L), (B, Z), (B, Z)) | ||||
| qi6 | (qi6, (0, L), (O, Z), (B, Z)) | (qi, (B, R), (0, Z), (B, Z)) | ||||
| qi7 | (qi7, (B, Z), (0, R), (0, R)) | (qi8, (B, L), (B, L), (B, Z)) | ||||
| qi8 | (qi9, (0, Z), (B, L), (B, Z)) | |||||
| qi9 | (qi10, (0, L), (0, L), (B, Z)) | (qi11, (0, L), (B, Z), (B, Z)) | ||||
| qi10 | (qi10, (0, L), (0, L), (B, Z)) | (qi10, (0, L), (B, Z), (B, Z)) | (qi, (B, R), (B, R), (B, Z)) | |||
| qi11 | (qi11, (0, L), (B, Z), (B, Z)) | (qr, (B, R), (B, Z), (B, Z)) |
| Principal | (0, 0, B) | (0, B, B) | (B, B, B) |
| q0 | (q1, (0, R), (B, Z), (B, Z)) | (q2, (B, L), (B, L), (B, Z)) | |
| q1 | (q0, (0, R), (0, R), (B, Z)) | (q2, (B, L), (B, L), (B, Z)) | |
| q2 | (q3, (0, L), (0, L), (B, Z)) | ||
| q3 | (q3, (0, L), (0, L), (B, Z)) | (q3, (0, L), (B, Z), (B, Z)) | (qi, (B, R), (B, R), (B, Z)) |
| qr |
Máquina de Turing "Normal" de Obtener los Divisores:
| Subrutina | 0 | 1 | $ | B | X | Y |
| qi | (qi2, X, R) | (qi5, $, R) | ||||
| qi2 | (qi2, 0, R) | (qi3, $, R) | ||||
| qi3 | (qi4, Y, L) | (qi3, Y, R) | ||||
| qi4 | (qi4, 0, L) | (qi4, $, L) | (qi, X, R) | |||
| qi5 | (qi6, 0, L) | (qi7, $, L) | (qi5, Y, R) | |||
| qi6 | (qi6, $, L) | (qi, B, R) | (qi6, 0, L) | (qi6, Y, L) | ||
| qi7 | (qi7, $, L) | (qi8, B, R) | (qi7, 0, L) | (qi7, 0, L) | ||
| qi8 | (qi9, X, R) | (qi11, $, R) | ||||
| qi9 | (qi9, 0, R) | (qi9, 1, R) | (qi9, $, R) | (qi10, 0, L) | ||
| qi10 | (qi10, 0, L) | (qi10, 1, L) | (qi10, $, L) | (qi8, X, R) | ||
| qi11 | (qi11, 0, R) | (qi11, 1, R) | (qi11, $, R) | (qi12, 1, L) | ||
| qi12 | (qi12, 0, L) | (qi12, 1, L) | (qi12, $, L) | (qi13, B, R) | (qi12, 0, L) | |
| qi13 | (qi14, B, R) | |||||
| qi14 | (qi15, 0, L) | (qr, B, R) | ||||
| qi15 | (qi, B, R) |
| Principal | 0 | B | X | $ |
| q0 | (q1, $, R) | |||
| q1 | (q2, X, R) | |||
| q2 | (q2, 0, R) | (q3, $, L) | (q3, X, L) | |
| q3 | (q3, 0, L) | (q3, X, L) | (q4, $, L) | |
| q4 | (q4, 0, L) | (q5, 0, R) | ||
| q5 | (q5, 0, R) | (q6, $, R) | ||
| q6 | (q7, 0, L) | (q6, X, R) | (q8, $, L) | |
| q7 | (q1, X, R) | (q1, $, R) | ||
| q8 | (q8, 0, L) | (qi, B, L) | (q8, 0, L) | (q8, $, L) |
| qr | (qr, B, R) | (q9, B, R) | ||
| q9 |
lunes, 7 de abril de 2008
Máquina de Turing N(cuadrado)
Esto es un enlace al pdf de la Máquina de Turing que calcula el N(cuadrado): Para descargar pincha aquí
sábado, 5 de abril de 2008
Máquina de Turing de la División
| Subrutina | 0 | 1 | $ | B | Y |
| qi | (qi2, B, R) | (qr, B, R) | |||
| qi2 | (qi2, 0, R) | (qi2, 1, R) | (qi3, $, L) | (qi2, Y, R) | |
| qi3 | (qi4, Y, L) | (qi5, 1, R) | (qi3, Y, L) | ||
| qi4 | (qi4, 0, L) | (qi4, 1, L) | (qi, B, R) | ||
| qi5 | (qi5, 0, R) | (qi5, $, R) | (qi6, 0, L) | (qi5, Y, R) | |
| qi6 | (qi6, 0, L) | (qi6, 1, L) | (qi6, $, L) | (qi, B, R) | (qi6, 0, L) |
| Principal | 0 | 1 | $ | B | Y |
| q0 | (q1, 0, R) | ||||
| q1 | (q1, 0, R) | (q2, 1, R) | |||
| q2 | (q3, 0, R) | ||||
| q3 | (q3, 0, R) | (q4, B, L) | |||
| q4 | (q5, $, L) | ||||
| q5 | (q5, 0, L) | (q5, 1, L) | (qi, B, R) | ||
| qr | (qr, B, R) | (q6, 1, L) | (qr, 0, R) | ||
| q6 |
Máquina de Turing para la multiplicación
Máquina de Turing de la Multiplicación:
| Subrutina | 0 | 1 | $ | B | X |
| qi | (qi2, X, R) | (qi6, $, L) | |||
| qi2 | (qi2, 0, R) | (qi3, $, R) | |||
| qi3 | (qi3, 0, R) | (qi4, 0, L) | |||
| qi4 | (qi4, 0, L) | (qi5, $, L) | |||
| qi5 | (qi5, 0, L) | (qi, X, R) | |||
| qi6 | (qr, 1, L) | (qi6, 0, L) |
| Principal | 0 | 1 | $ | B |
| q0 | (q0, 0, R) | (q0, 1, R) | (q1, $, L) | |
| q1 | (q1, 0, L) | (q1, 1, L) | (q2, B, R) | |
| q2 | (q3, B, R) | (q4, B, R) | ||
| q3 | (q3, 0, R) | (qi, 1, R) | ||
| qr | (qr, 0, L) | (q2, B, R) | ||
| q4 | (q4, B, R) | (q5, B, R) | ||
| q5 |
Suscribirse a:
Comentarios (Atom)