INTRODUCCION

considerar las máquinas abstractas que permiten solucionar ciertos tipos de algoritmos, los algoritmos en los que no puede recordarse más que una cantidad fija de información y otros en los que la información desarrollada durante la ejecución del algoritmo puede recuperarse solo en concordancia con la regla “lifo” últimos en entrar primeros en salir, en esta unidad se describe una maquina abstracta, llamada Máquina de Turing , que es aceptada de manera amplia como modelo general de computación, aunque las operaciones básicas de esta máquina son comparables en su sencillez a las de las máquinas estudiadas en las unidades anteriores, las nuevas maquinas pueden realizar una amplia variedad de operaciones de cómputo.

Además de aceptar lenguajes les es posible computar funciones y de conformidad con la tesis de Church-Turing, ejecutar casi cualquier procedimiento algorítmico concebible.

OBJETIVO GENERAL

Reconocer la importancia y el poder computacional de las Máquinas de Turing en el contexto de la solución de problemas computacionales de reconocimiento de Lenguajes.

OBJETIVOS ESPECÍFICOS:

Estudiar las Máquinas de Turing y sus propiedades básicas

Máquina que acepta el lenguaje de palabras sobre {0, 1} que comienzan y acaban con el mismo símbolo.

Diséñela en un Diagrama de Moore

Recorra la máquina con al menos una cadena válida.

Identifique una cadena que no sea válida y justifíquela porque.

Ejecute el RunTest a la cadena aceptada (muéstrela en la captura de imagen para el trabajo)

Identifique en que momento la máquina se detiene