gggggg

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 uncará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.
En realidad la máquina de Turing es más una abstracción matemática que undispositivo 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.
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 de lectura/escritura. 
La cinta contiene una serie de celdas, y en cada una de ellas puede escribirse un símbolo de unconjunto finito;  este conjunto de símbolos se denomina el alfabeto de la máquina.
En principio todas las celdas que no se hayan escrito contienen un carácter especial nulo o vacío (representadapor 0 o #).
 La cinta puede contener tantas celdas a derecha e izquierda del cabezal como sean 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 deestados posibles es finito, y no se exige ningún estado especial con el que sea iniciada la máquina.
Existe una tabla de acción, que contiene las instrucciones de lo que hará el autómata.  Estas...