Maquina de turing y mealy



Ingeniería en Sistemas Computacionales

Materia: Lenguaje de Interfaces

Practica: # 1

Tema: Maquina de Turing
Máquina de Mealy



MAQUINA DE TURING
La máquina de Turing modelamatemáticamente a una máquina que opera mecánicamente sobre una cinta. En esta cinta hay símbolos que la máquina puede leer y escribir, uno a la vez, usando un cabezal lector/escritor de cinta.
Laoperación está completamente determinada por un conjunto finito de instrucciones elementales como "en el estado 42, si el símbolo visto es 0, escribe un 1; Si el símbolo visto es 1, cambia al
Turing noimagina un mecanismo, sino una persona a la que él llama la "computadora", quien ejecuta servilmente estas reglas mecánicas deterministas, de una manera desganada.
FUNCIONAMIENTO
La máquina deTuring consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar enesta máquina se limitan a:
Mover el cabezal lector/escritor hacia la derecha.


Mover el cabezal lector/escritor hacia la izquierda.
El cómputo se determina a partir de una tabla de estados de laforma:
(estado, valor)  (nuevo estado, nuevo valor, dirección)
Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover elcabezal, el nuevo estado de la máquina y el valor a escribir en la cinta.
La memoria es la cinta de la máquina que se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leersímbolos. Inicialmente todas las celdas contienen un símbolo especial denominado "blanco". Las instrucciones que determinan el funcionamiento de la máquina tienen la forma, "si estamos en elestado xleyendo la posición y, donde hay escrito el símbolo z, entonces este símbolo debe ser reemplazado por este otro símbolo, y pasar a leer la celda siguiente, bien a la izquierda o bien a la derecha"....