Maquina De Turing

Máquina de Turing
Una máquina de Turing (MT) es un modelo computacional que realiza una lectura/
escritura de manera automática sobre una entrada llamada cinta, generando una
salida en esta misma.
Este modelo está formado por un alfabeto de entrada y uno de salida, un símbolo
especial llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos
y un conjunto de transiciones entredichos estados. Su funcionamiento se
basa en una función de transición, que recibe un estado inicial y una cadena
de caracteres (la cinta, la cual puede ser infinita) pertenecientes al alfabeto de
entrada. La máquina va leyendo una celda de la cinta en cada paso, borrando el
símbolo en el que se encuentra posicionado su cabezal y escribiendo un nuevo
símbolo perteneciente al alfabeto desalida, para luego desplazar el cabezal a la
izquierda o a la derecha (solo una celda a la vez). Esto se repite según se indique
en la función de transición, para finalmente detenerse en un estado final o de
aceptación, representando así la salida.

Definición formal
Una máquina de Turing con una sola cinta puede definirse como una 7-tupla

donde:2
es un conjunto finito de estados.
es unconjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de
máquina o de entrada.
es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta (

).

es el estado inicial.
es un símbolo denominado blanco, y es el único símbolo que se puede repetir un
número infinito de veces.
es el conjunto de estados finales de aceptación.

es una función parcialdenominada función de
transición, donde es un movimiento a la izquierda y
es el movimiento a la derecha.
Existen en la literatura un abundante número de definiciones alternativas, pero todas ellas
tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo como
símbolo de "no movimiento" en un paso de cómputo.

Funcionamiento
La máquina de Turing consta de un cabezallector/escritor y una cinta infinita en la que
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:
Avanzar el cabezal lector/escritor hacia la derecha.

Avanzar el cabezal lector/escritor hacia la izquierda.
El cómputo es determinado a partir de una tabla de estados de la 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 la
cinta, 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 se divide en espacios de trabajo denominados
celdas, donde se pueden escribir y leer símbolos. Inicialmentetodas 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 el sí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".
La máquina de Turingpuede considerarse como un autómata capaz de reconocer lenguajes
formales. En ese sentido, es capaz de reconocer los lenguajes recursivamente
enumerables, de acuerdo a la jerarquía de Chomsky. Su potencia es, por tanto, superior
a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros
modelos con la misma potencia computacional.

Representación comodiagrama de estados
Las maquinas de Turing pueden representarse mediante grafos particulares, también
llamados diagramas de estados finitos, de la siguiente manera:

Los estados se representan como vértices, etiquetados con su nombre en el interior.
Una transición desde un estado a otro, se representa mediante
una arista dirigida que une a estos vértices, y esta rotulada por símbolo que lee el...