Maquina de turing

LA MÁQUINA DE TURING

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 datos en lasecuencia;  recorrer la secuencia en ambos sentidos y cambiar de "estado" dentro de un conjunto finito de estados posibles.
Existen diversas "variedades" de una máquina de Turing, pero la más simple puede ser descrita diciendo que es cualquier dispositivo que cumple las siguientes condiciones:
• Tiene una cinta sobre la que puede desplazarse a izquierda y derecha un cabezal delectura/escritura.  La cinta contiene una serie de celdas, y en cada una de ellas puede escribirse un símbolo de un conjunto finito;  este conjunto de símbolos se denomina el alfabeto de la máquina.  En principio todas las celdas que no se hayan escrito antes contienen un carácter especial nulo o vacío (que se representa por 0 o #).  La cinta puede contener tantas celdas a derecha e izquierda del cabezal comosean necesarias para el funcionamiento de la máquina.
• El cabezal puede moverse a derecha (R) a izquierda (L) de su posición actual, así como leer el contenido de una celda o escribir en ella cualquier carácter de su alfabeto.
• Existe un registro de estado que almacena el estado de la máquina.  El número de estados posibles es finito, y no se exige ningún estado especial con el quesea iniciada la máquina.
• Existe una tabla de acción, que contiene las instrucciones de lo que hará el autómata.  Estas instrucciones representan en cierta forma el "programa" de la máquina.  Las ejecución de cada instrucción de la tabla de acción incluye cuatro pasos:
o Leer un carácter en la posición actual.
o Escribir un nuevo símbolo en esta posición (puede ser elmismo que había).  El símbolo a escribir es alguno del alfabeto de la máquina, y depende del carácter leído y del estado actual.
o Desplazar el cabezal una celda a derecha o izquierda (R/L);  en algunos modelos el desplazamiento puede ser nulo (detener H).
o Decidir cual será el nuevo estado en función del carácter que se acaba de leer y del estado actual.  Si la tabla de acciónno contiene ninguna correspondencia con el estado actual y el símbolo leído, entonces la máquina detiene su funcionamiento.

En los modelos didácticos computarizados la tabla suele definirse mediante una matriz de cinco columnas que contiene:

Estado/Carácter-leído/Carácter-a-escribir/Movimiento/Nuevo-estado

|+---+---++---+---+---+ |
|| S | R || W | M | N ||
|+---+---++---+---+---+ |
|| 0 | 0 || 0 | R | 0 | |
|| 0 | 1 || 1 | R | 1 | |
|| 1 | 0 || 1 | R | 2 | |
|| 1 | 1 || 1 | R | 1 | |
|| 2 | 0 || 0 | H | 2 | |
|| 2 | 1 || 0 | H | 2 | |
|+---+---++---+---+---+|
| |
|S = Estado actual |
|R = Carácter leído |
|W = Carácter escrito |
|M = Dirección del movimiento |
|N = Nuevo estado |

En el recuadro se incluye una muestra de una de estas tablas.  Representa el comportamiento deuna máquina de turing que es capaz de sumar 1 a cualquier número unario.  El alfabeto solo tiene dos símbolos:  Vacío (0) y valor (1).  La máquina puede adoptar tres estados diferentes numerados del 0 al 2 (es costumbre señalar el estado inicial con 0).  El movimiento H ("Halt") significa no desplazar el cabezal.  En este caso la máquina se detiene (o entra en un bucle sin fin).
|[pic]...