Máquinas de turing

Máquinas de Turing

Concepto y representación de Máquinas de Turing
Una Máquina de Turing es un modelo matemático simple de una computadora que realiza una lectura/escritura de manera automática sombre 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 entre dichos 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 yescribiendo un nuevo símbolo perteneciente al alfabeto de salida, 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.

Representación como diagrama de estados
Las maquinas de Turing pueden representarsemediante 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 cabezal/símbolo que escribirá el cabezal, movimiento delcabezal.
* El estado inicial se caracteriza por tener una arista que llega a él y que no proviene de ningún otro vértice.
* El o los estados finales se representan mediante vértices que están encerrados a su vez por otra circunferencia.

Modelo de la Máquina de Turing
Un modelo formal para un procedimiento efectivo deberá poseer ciertas propiedades. Primero, cada procedimiento deberápoder describir de manera finita. Segundo, el procedimiento deberá consistir en pasos discretos, cada uno de los cuales puede llevarse a cabo de manera mecánica. Este modelo fue introducido por Alan Turing en 1936.
El modelo básico tiene un control finito, una cinta de entrada que está dividida en celdas y una cabeza de cinta que barre una celda de la cinta a la vez. La cinta tiene una celda que estámás a la izquierda, pero se extiende de manera infinita hacia la derecha. Cada celda de la cinta puede contener exactamente un símbolo de un número infinito de símbolos de cinta. Inicialmente las n celdas que están más a la izquierda, para alguna n ≥ 0 finita, sujetan la entrada, que es una cadena de símbolos escogidos de un subconjunto de los símbolos de la cinta, llamados símbolos de entrada.Cada una del número infinito de celdas restantes sujeta el espacio en blanco, que es un tipo especial de símbolo que no es de entrada.

En un movimiento, dependiendo del símbolo barrido por la cabeza de la cinta y del estado del control finito, la máquina de Turing:
1. Cambia de estado
2. Imprime un símbolo en la celda de la cinta que está siendo barrida, sustituyendo lo que se encontrabaahí escrito
3. Mueve su cabeza una celda hacia la izquierda o la derecha.
Nótese que la diferencia entre una máquina de Turing y un autómata de dos direcciones estriba en la capacidad de la primera para cambiar símbolos en su cinta.
De manera formal, una máquina de Turing (TM) se representa por una 7-tupla:
M= (Q, Ʃ, , , q0, Β, F)
donde,
Q es el conjunto finito de estados
 es elconjunto finito de símbolos de cinta admisibles
Ʃ , subconjunto de  que no incluye a B, es el conjunto de los símbolos de entrada
 es la función de movimientos siguiente, una transformación de Q x  a Q x  x {L, R} ( puede, sin embargo, permanecer indefinida para algunos argumentos)
q0 en Q es el estado inicial
F Q Q es el conjunto de estados finales de aceptación.

Máquinas de Turing...