Maquinas de Turing

Hola compañeros, les hablare sobre las maquinas de turing Una máquina de Turing:

es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.

Es un autómata que se mueve sobre una secuencia lineal de datos.  En cada instante esta máquina puede leer un solo dato de la secuencia (generalmente un carácter) y realizar ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído.  Está la posibilidad de escribir nuevos datos en 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 que un 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 una implementación real muy simple, lo que ha motivado que existan muchas versiones prácticas del mismo.

-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 que sea 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.  La ejecución de cada instrucción de la tabla de acción incluye cuatro pasos: 

-Leer un carácter en la posición actual.

-Escribir un nuevo símbolo en esta posición (puede ser el mismo que había).  El símbolo a escribir es   alguno del alfabeto de la máquina.

-Desplazar el cabezal una celda a derecha o izquierda.

-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ón no contiene ninguna correspondencia con el estado actual y el símbolo leído, entonces la máquina detiene su funcionamiento.