última semana antes de examenes

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.

Ú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.

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:

Demostración de que la operacion interseccion es de clausura para Lenguajes Recursivos

Demostracion por leyes de De Morgan:

Sea L₁ un LR -> Existe al menos una M₁ | L₁=L(M₁) y M₁ siempre para.

Sea L₂ un LR -> Existe al menos una M₂ | L₂=L(M₂) y siempre para.

Sea L₃ un LR -> Existe al menos una M₃ | L₃=L(M₃)=(L₁)' y siempre para.

Sea L₄ un LR -> Existe al menos una M₄ | L₃=L(M₄)=(L₂)' y siempre para.

Sea L₁ U L₂ un LR -> (L₁)' U (L₂)' también lo es--> ((L₁)' U (L₂)')' es un LR --> L₁ intersectado con L₂ también lo es.

A continuación lo demostraremos mediante una contrucción de una MT que intersecte dos LR:

continuara....