Maquina De Turing

Que es la maquina 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 estamisma.
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 deentrada. 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 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 deaceptación, representando así la salida.
Funcionamiento
La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenidoanterior 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.
Visualización de una máquina de Turing, en laque se ve el cabezal y la cinta que se lee.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) (nuevoestado, 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 yel 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. Inicialmente todas las celdas...