Máquina de Turing

Máquina de Turing

Que es:
Es un dispositivo de reconocimientos de lenguaje, es más general que cualquier autómata finito y cualquier autómata de pila, debido a que ellas pueden reconocer tanto loslenguajes regulares, como los lenguajes independientes de contexto y además muchos otros tipos de lenguajes.
La máquina de Turing (abreviado MT) tiene, un control finito, una cabeza lectora y unacinta donde puede haber caracteres, y donde eventualmente viene la palabra de entrada. La cinta es de longitud infinita hacia la derecha, hacia donde se extiende indefinidamente, llenándose los espacioscon el carácter blanco (que representaremos con “t”). La cinta no es infinita hacia la izquierda, por lo que hay un cuadro de la cinta que es el extremo izquierdo, la MT la cabeza lectora es de lecturay escritura, por lo que la cinta puede ser modificada en curso de ejecución. Además, en la MT la cabeza se mueve bidireccionalmente (izquierda y derecha), por lo que puede pasar repetidas veces sobreun mismo segmento de la cinta.
Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos.  En cada instante la máquina puede leer un solo dato de la secuencia(generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído.  Entre las acciones está la posibilidad de escribir nuevos datosen la secuencia; recorrer la secuencia en ambos sentidos y cambiar de "estado" dentro de un conjunto finito de estados posibles.
En realidad la máquina de Turing es más una abstracción matemática queun dispositivo físico o mecánico.  El hecho que se le denomine "máquina" se debe a que su funcionamiento puede ser descrito en términos de operaciones individuales muy sencillas que sugieren unaimplementación real muy simple, lo que ha motivado que existan muchas versiones prácticas del mismo.

Como funciona:
Una máquina de Turing es un dispositivo que transforma un INPUT en un OUTPUT después...