Máquina de Turing

De Wikipedia, la enciclopedia libre

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

Diagrama artístico de una máquina de Turing.

Tabla de contenidos

1 Descripción
2 Definición
3 Ejemplo
4 Máquinas de Turing deterministas y no deterministas
5 Máquina Universal de Turing
6 Máquina de Turing Cuántica
7 Véase también
8 Enlaces externos

[editar] Descripción

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 para la derecha;
avanzar el cabezal lector/escritor para la izquierda.

El cómputo es determinado a partir de una tabla de estados de la forma:

(estado, valor) $\rightarrow$ (\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 ser escrito en la cinta.

Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.

Mediante este modelo teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo polinómico son encontradas según el determinismo y no determinismo respectivamente de la máquina de Turing.

De hecho, se puede probar matemáticamente que para cualquier programa de computadora es posible crear una máquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing, formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX.

La idea subyacente en el concepto de que una máquina de Turing es una persona ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible. La memoria 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, “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 Turing puede 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.

[editar] Definición

Una máquina de Turing con una sola cinta puede ser definida como una 6-tupla $M=(Q, \Gamma, s, b, F, \delta)\,$ , donde

$Q \,$ es un conjunto finito de estados.
$\Gamma \,$ es un conjunto finito de símbolos de cinta, el alfabeto de cinta.
$s \in Q$ es el estado inicial.
$b \in \Gamma$ es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
$F \subseteq Q$ es el conjunto de estados finales de aceptación.
$\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}\,$ es una función parcial denominada función de transición, donde L es un movimiento a la izquierda y R 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 $S\,$ como símbolo de "no movimiento" en un paso de cómputo o el símbolo $Σ$ para indicar el alfabeto de entrada.

[editar] Ejemplo

Definimos una máquina de Turing sobre el alfabeto {'0', '1'}, donde 0 representa el símbolo blanco. La máquina comenzará su proceso situada sobre un símbolo "1" de una serie. La máquina de Turing copiará el número de símbolos "1" que encuentre hasta el primer blanco detrás de dicho símbolo blanco. Es decir, situada sobre el 1 situado en el extremo izquierdo, doblará el número de símbolos 1, con un 0 en medio. Así, si tenemos la entrada "111" devolverá "1110111", con "1111" devolverá "111101111", y sucesivamente.

El conjunto de estados es {s1, s2, s3, s4, s5} y el estado inicial es s1. La tabla que describe la función de transición es la siguiente:

 Estado Símbolo Símbolo   Mov.  Estado           Estado Símbolo Símbolo   Mov.  Estado
        leído   escrito         sig.                    leído   escrito         sig.
 - - - - - - - - - - - - - - - - - - - -           - - - - - - - - - - - - - - - - - - - -
  s1      1   ->    0      R      s2               s4      1   ->   1       L     s4
  s2      1   ->    1      R      s2               s4      0   ->   0       L     s5
  s2      0   ->    0      R      s3               s5      1   ->   1       L     s5
  s3      0   ->    1      L      s4               s5      0   ->   1       R     s1
  s3      1   ->    1      R      s3

El funcionamiento de una computación de esta máquina se puede mostrar con el siguiente ejemplo (en negrita se resalta la posición de la cabeza lectora/escritora):

 Paso Estado  Cinta      Paso Estado   Cinta
 - - - - - - - - - - -   - - - - - - - - - - - -
    1  s1     11           9  s2       1001
    2  s2     01          10  s3       1001
    3  s2     010         11  s3       10010
    4  s3     0100        12  s4       10011
    5  s4     0101        13  s4       10011
    6  s5     0101        14  s5       10011
    7  s5     0101        15  s1       11011
    8  s1     1101          -- Parada --

La máquina realiza su proceso por medio de un bucle, en el estado inicial s1, reemplaza el primer 1 con un 0, y pasa al estado s2, con el que avanza hasta la derecha, saltando los símbolos 1 hasta un 0 (que debe existir), cuando lo encuentra pasa a ser s3, con este estado avanza saltando los 1 hasta encontrar otro 0 (la primera vez no habría ningún 1). Una vez en el extremo derecho, añade un 1. Después comienza el proceso de retorno; con s4 vuelve a la izquierda saltando los 1, cuando encuentra un 0 (en el medio de la secuencia), pasa a s5 que continúa a la izquierda saltando los 1 hasta el 0 que se escribió al principio. Se reemplaza de nuevo este 0 por 1, y pasa al símbolo siguiente, si es un 1, se pasa a otra iteración del bucle, pasando al estado s1 de nuevo. Si es un símbolo 0, será el símbolo central, con lo que la máquina se detiene al haber finalizado su cómputo.

[editar] Máquinas de Turing deterministas y no deterministas

La entrada de una máquina de Turing viene determinada por el estado actual y el símbolo leído, un par [estado, símbolo], siendo el cambio de estado, la escritura de un nuevo símbolo y el movimiento las acciones a tomar en función de una entrada. En el caso de que para cada par estado y símbolo posible exista a lo sumo una posibilidad de ejecución, se dirá que es una máquina de Turing determinista, mientras que en el caso de que exista al menos un par [estado, símbolo] con más de una posible combinación de actuaciones se dirá que se trata de una máquina de Turing no determinista.

La función de transición $δ$ en el caso no determinista, queda definida como sigue:

$\delta: Q \times \Gamma \rightarrow \mathcal{P} ( Q \times \Gamma \times \{L,R\})$

La capacidad de cómputo de ambas versiones es equivalente; se puede demostrar que dada una máquina de Turing no determinista existe otra máquina de Turing determinista equivalente, en el sentido de que reconoce el mismo lenguaje, y viceversa. No obstante, la velocidad de ejecución de ambos formalismos no es la misma, pues si una máquina no determinista M reconoce una cierta palabra de tamaño n en un tiempo $O (t (n))$ , la máquina determinista equivalente reconocerá la palabra en un tiempo $O (2 t (n))$ . Es decir, el no determinismo permitirá reducir la complejidad de la solución de los problemas, permitiendo resolver, por ejemplo, problemas de complejidad exponencial en un tiempo polinómico.

Véase también: Complejidad computacional

[editar] Máquina Universal de Turing

Una máquina de Turing computa una determinada función parcial de carácter definido, y unívoca, definida sobre las secuencias de posibles cadenas de símbolos de su alfabeto. En este sentido se puede considerar como equivalente a un programa de ordenador, o lo que es lo mismo, a un algoritmo. Sin embargo es posible realizar una codificación de la tabla que representa a una máquina de Turing, a su vez, como una secuencia de símbolos en un determinado alfabeto; por ello, podemos construir una máquina de Turing que acepte como entrada la tabla que representa a otra máquina de Turing, y, de esta manera, simule su comportamiento.

En 1947, Turing indicó:

Se puede demostrar que es posible construir una máquina especial de este tipo que pueda realizar el trabajo de todas las demás. Esta máquina especial puede ser denominada máquina universal.

Esta fue, posiblemente, la idea germinal del concepto de Sistema Operativo, un programa que puede, a su vez, ejecutar en el sentido de controlar otros programas, demostrando su existencia, y abriendo camino para su construcción real.

Con esta codificación de tablas como cadenas, se abre la posiblidad de que unas máquinas de Turing se comporten como otras máquinas de Turing. Sin embargo, muchas de sus posibilidades son indecidibles, pues no admiten una solución algorítmica. Por ejemplo, un problema interesante es determinar si una máquina de Turing cualquiera se parará en un tiempo finito sobre una determinada entrada; problema conocido como Problema de la parada, y que Turing demostró que era indecidible. En general, se puede demostrar que cualquier cuestión no trivial sobre el comportamiento o la salida de una máquina de Turing es un problema indecidible.

[editar] Máquina de Turing Cuántica

En 1985, Deutsch presentó el diseño de la primera Máquina Cuántica basada en una máquina de Turing. Para poder hacer esto, Deutsch enunció la tesis de Church de manera diferente dando lugar al denominado "Principio de Church-Turing-Deutsch".

A partir de este momento, diseña la primera máquina cuántica de Turing, cuya estructura es muy similar a la de una máquina de Turing clásica. Podemos definir una máquina cuántica, como una máquina formada por una serie de estados finitos, con los tres componentes clásicos:

Una unidad de memoria finita
Un procesador finito
Un cursor

La siguiente ilustración muestra el esquema de una máquina cuántica:

Los QuBits (tal como se muestran en la ilustración anterior) nos permiten representar que, en esta máquina, el procesador está formado por un número finito de estados.

El juego de instrucciones de esta máquina está formado por los cambios que se realizan sobre los QuBits de control (hay que tener en cuenta, que a veces esto puede depender del QuBit que se esté procesando en un momento dado sobre la cinta). Además, esta máquina sólo puede realizar una instrucción por unidad de tiempo.

La unidad de memoria es similar a la cinta de memoria de una máquina de Turing tradicional. La única diferencia entre ambas radica en el hecho de que, por cada elemento de la cinta de la máquina cuántica, tenemos un QuBit. Por tanto, podemos decir que el alfabeto de esta nueva máquina está formado por el espacio de valores del QuBit.

Finalmente, podemos definir el cursor como el elemento que nos permite comunicar la unidad de memoria y el procesador. Para almacenar su posición dentro de la cinta utilizamos una variable entera. Es necesario resaltar, que el cursor sólo puede procesar un elemento de la cinta por unidad de tiempo.