Maquina de turing

UNIDAD IV: Maquina de Turing

La máquina de Turing es un modelo computacional introducido por Alan Turing en el trabajo “On computable numbers, with an application to the Entscheidungsproblem”, publicado por la Sociedad Matemática de Londres, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que puedaaplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. Turing construyó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver. La máquina de Turing es un modelo matemático abstracto que formaliza el concepto de algoritmo.

Definición formal de una Maquina de Turing

Una máquina de Turing conuna sola cinta puede ser definida como una 7-tupla , donde:
• es un conjunto finito de estados.
• es un conjunto 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 unnúmero infinito de veces.
• es el conjunto de estados finales de aceptación.
• es una función parcial denominada 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 o el símbolo para indicar el alfabeto de entrada.
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 contenido anterior y escribe un nuevo valor (fig.1). Las operaciones que se pueden realizar en esta máquina se limitan a:
• avanzar el cabezal lector/escritor hacia laderecha.
• avanzar el cabezal lector/escritor hacia la izquierda.
Fig.1. Visualización de una Maquina de Turing, en la que se ve el cabezal y la cinta que se lee

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, dandola dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta.
La memoria será la cinta la cual se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado “blanco”. Las instrucciones que determinan el funcionamiento de la máquina tienen la forma, “siestamos 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 Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido es capaz de reconocer los lenguajes recursivamente enumerables, deacuerdo 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 como diagrama de estados:Las maquinas de Turing se pueden representar 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 cabezal/símbolo que escribirá el cabezal, movimiento del cabezal.
• El estado inicial se caracteriza por tener una arista que llega a él, proveniente de ningún otro...