ingenieria en sistemas

1- Definición: Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de susimplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de lasfunciones de un CPU dentro de un computador.
Funcionamiento: La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en laque el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:
Moverel 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 dela forma:
(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 lacinta, dando la dirección para mover el cabezal, 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 sedivide en espacios de trabajo denominados celdas, donde se pueden escribir y leer sí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 el estado x leyendo la posición y, donde hay escrito elsí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".