Enunciado Trabajo Colaborativo 3

1)Mediante un grafo explique la construcción modular de las Máquinas de
Turing y describa cada uno de sus elementos.

5)Cite un ejemplo real (aplicado a algún problema computacional válido,problema de cálculo, problema inmerso en un ejercicio de la vida diaria ó
problema que se pueda representar mediante un algoritmo) que lo lleve a
comprender o a asociar PRINCIPIO DE CHURCH-TURING:.(Describa su ejemplo
de forma concisa y aplicada)
Tenga cuidado con lo que copia de Internet. La explicación debe ser precisa,
clara y objetiva, de su autoría. Si cita algún documento de la web, severificarán las referencias y pié de página. Documento que no tenga estas
referencias, será material no evaluado.

7)Haciendo uso de un simulador, monte los tres ejercicios iniciales (2, 3 ,6) deeste trabajo en un simulador y recorra la máquina, verificando:
• su estado inicial,
• su estado final
• estado de parada
• estado de inicio
• cadenas aceptadas.
Tenga en cuenta que la construcciónde las máquinas (los diagramas de
Moore) solo son permitidos si son generados por un simulador.
En este ejercicio debe incluir los archivos generados por el simulador

8)Una manera más simple dedeterminar la indecibilidad es utilizando el
método de reducción, el cual está implícito en nuestra manera de pensar a
la hora de solucionar ciertos problemas: dado un problema P1, este se
reduce asolucionar P2. Es decir, si solucionamos P2, tenemos solucionado
P1.
Formule un problema típico que aplique a su vida cotidiana, personal,
académica o laboral que mediante el método de reducciónsolucione esta
“indecibilidad”.
La formulación implica:
• Descripción del problema
• Actores que intervienen
• Justificación porque es indecidible
• Una posible solución (de reducción)
• Unacomparativa con el autómata y la descripción de sus
componentes.

9)Diseñar una MT que acepte las palabras en {a, b} que terminen con a.
•
•
•
•
•
Plásmela en el simulador (debe entregar el...