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.
1 comentario:
Buena foto, y buen dibujo, esta bien. Pero os falta un poquito de explicacion no?
Solo deciros que os toca corregirnos la tarea 5, igual que os estoy corrigiendo yo esta tarea y gracias a esto tendreis una nota mas, no me jodais y corregirnos dentro del plazo si puede ser.
Aleee, q vaya bien.
Publicar un comentario