Máquinas De Turing

Máquinas de Turing

Compilado por:
Álvaro Arturo Ledo

FEBRERO 2012

INTRODUCCIÓN

Contrariamente de lo que pudiera parecer, la ciencia de la computación y las teorías sobre computabilidad no pertenecen a la disciplina que hoy conocemos como "Informática", sino a las matemáticas, que son, con mucho, anteriores a aquella.
A principio del siglo XX, el campo de la matemática teórica estabaen plena efervescencia, gracias sobre todo a los trabajos de Hilbert y Gödel.  En particular Hilbert había planteado ciertas cuestiones que derivaron en las teorías de la computación y la computabilidad, en concreto cual sería el significado de la computabilidad de un procedimiento.
Para dar una definición matemáticamente precisa de lo que es un algoritmo, Turing ideó un dispositivo imaginarioal que denominó Máquina de computación lógica LCM ("Logical Computing Machine"), pero que ha recibido en su honor el nombre de Máquina de Turing.  Aunque su propuesta es anterior a la aparición de los computadores digitales (1936 "On computable numbers, with an application to the Entscheidungproblem"), actualmente es el objeto central de estudio de los teóricos de la computación. 
Precisamente ladefinición moderna de lo que es "Computable" se basa en este concepto, y del mismo modo que cuando se habla de inteligencia artificial es inevitable referirse al Test de Turing, cuando se habla de algoritmos y computación es casi inevitable encontrar alguna referencia a la Máquina de Turing. Por si esto fuera poco, los conceptos subyacentes en la idea han jugado un papel importante en lasrecientes teorías filosóficas sobre la mente.
Lo que confiere al dispositivo su extraordinaria importancia es que es capaz de resolver cualquier problema matemático a condición de que haya sido reducido a un algoritmo.

MÁQUINA DE TURING

Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos.  En cada instante la máquina puede leer un solo dato de la secuencia(generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído.  Entre las acciones 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ónmatemá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.

Definición Formal
Una máquina de Turing con una sola cinta puede definirse como una 7-tupladonde:
*  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 un nú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 decómputo.

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. 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...