Máquina de Turing

Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de una CPU dentro de un computador.

Originalmente fue definida por el matemático inglés Alan Turing como una «máquina automática» en 1936 en la revista Proceedings of the London Mathematical Society^{[nota 1]}​. La máquina de Turing no está diseñada como una tecnología de computación práctica, sino como un dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico^[3]​^[4]​

Turing dio una definición sucinta del experimento en su ensayo de 1948, «Máquinas inteligentes». Refiriéndose a su publicación de 1936, Turing escribió que la máquina de Turing, aquí llamada una máquina de computación lógica, consistía en:

Una máquina de Turing que es capaz de simular cualquier otra máquina de Turing es llamada una máquina universal de Turing (UTM, o simplemente una máquina universal). Una definición más matemáticamente orientada, con una similar naturaleza "universal", fue presentada por Alonzo Church, cuyo trabajo sobre el cálculo lambda se entrelaza con el de Turing en una teoría formal de la computación conocida como la tesis de Church-Turing. La tesis señala que las máquinas de Turing capturan, de hecho, la noción informal de un método eficaz en la lógica y las matemáticas y proporcionan una definición precisa de un algoritmo o 'procedimiento mecánico'.

La importancia de la máquina de Turing en la historia de la computación es doble: primero, la máquina de Turing fue uno de los primeros (si no el primero) modelos teóricos para las computadoras, viendo la luz en 1936. Segundo, estudiando sus propiedades abstractas, la máquina de Turing ha servido de base para mucho desarrollo teórico en las ciencias de la computación y en la teoría de la complejidad. Una razón para esto es que las máquinas de Turing son simples, y por tanto amenas al análisis. Dicho esto, cabe aclarar que las máquinas de Turing no son un modelo práctico para la computación en máquinas reales, las cuales precisan modelos más rápidos como los basados en RAM.

Alan Turing introdujo el concepto de máquina de Turing en el trabajo On computable numbers, with an application to the Entscheidungsproblem, publicado por la Sociedad Matemática de Londres en 1936, en el que 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 ideó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver.^[6]​

Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.^[7]​)

Mediante este modelo teórico y el análisis de la complejidad de los 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 pueden encontrarse en tiempo polinómico por máquinas de Turing deterministas y no deterministas, respectivamente.

Precisamente, la tesis de Church-Turing formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX caracteriza la noción informal de computabilidad con la computación mediante una máquina de Turing.^[8]​

La idea subyacente es el concepto de que una máquina de Turing puede verse como un autómata 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 máquina de Turing modela matemáticamente a una máquina que opera mecánicamente sobre una cinta. En esta cinta hay símbolos que la máquina puede leer y escribir, uno a la vez, usando un cabezal lector/escritor de cinta. La operación está completamente determinada por un conjunto finito de instrucciones elementales como "en el estado 42, si el símbolo visto es 0, escribe un 1; Si el símbolo visto es 1, cambia al estado 17; en el estado 17, si el símbolo visto es 0, escribe un 1 y cambia al estado 6; etc". En el artículo original ("Sobre números computables con una aplicación al Entscheidungsproblem"), Turing no imagina un mecanismo, sino una persona a la que él llama la "computadora", quien ejecuta servilmente estas reglas mecánicas deterministas (o como Turing pone, "de una manera desganada").

Más precisamente, una máquina de Turing consta de:

Note que cada parte de la máquina — su estado y colecciones de símbolos — y sus acciones — imprimir, borrar, movimiento de la cinta — es finito, discreto y distinguible; es la cantidad potencialmente ilimitada de cinta lo que le da una cantidad ilimitada de espacio de almacenamiento.

Una máquina de Turing^[10]​es un modelo computacional que realiza una lectura/escritura de manera automática sobre 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, ${displaystyle Delta }$ 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 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 de aceptación, representando así la salida.

Una máquina de Turing con una sola cinta puede definirse como una 7-tupla

donde:^[11]​

Existe 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 ${displaystyle S!}$ como símbolo de "no movimiento" en un paso de cómputo.

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:

El cómputo se determina a partir de una tabla de estados de la forma:

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

Las máquinas de Turing pueden representarse mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:

Es una secuencia de la forma ${displaystyle alpha _{1}qalpha _{2}!}$ donde ${displaystyle alpha _{1},alpha _{2}in Gamma ^{*}}$ y ${displaystyle qin Q}$ que escribe el estado de una máquina de Turing. La cinta contiene la cadena ${displaystyle alpha _{1}alpha _{2}!}$ seguida de infinitos blancos. El cabezal señala el primer símbolo de ${displaystyle alpha _{2}!}$.

Por ejemplo, para la máquina de Turing

con las transiciones

La descripción instantánea para la cinta 1011 es:

Definimos una máquina de Turing sobre el alfabeto ${displaystyle {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, posiciona el cabezal 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 ${displaystyle {s_{1},s_{2},s_{3},s_{4},s_{5}}!}$ y el estado inicial es ${displaystyle s_{1}!}$. La tabla que describe la función de transición es la siguiente:

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

La máquina realiza su proceso por medio de un bucle, en el estado inicial ${displaystyle s_{1}!}$, reemplaza el primer 1 con un 0, y pasa al estado ${displaystyle s_{2}!}$, con el que avanza hacia la derecha, saltando los símbolos 1 hasta un 0 (que debe existir), cuando lo encuentra pasa al estado ${displaystyle s_{3}!}$, con este estado avanza saltando los 1 hasta encontrar otro 0 (la primera vez no habrá ningún 1). Una vez en el extremo derecho, añade un 1. Después comienza el proceso de retorno; con ${displaystyle s_{4}!}$ vuelve a la izquierda saltando los 1, cuando encuentra un 0 (en el medio de la secuencia), pasa a ${displaystyle s_{5}!}$ 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 el cómputo.

Una razón para aceptar la máquina de Turing como un modelo general de cómputo es que el modelo que hemos definido anteriormente es equivalente a muchas versiones modificadas que en principio pareciera incrementar el poder computacional.

La función de transición de la MT sencilla está definida por

la cual puede ser modificada como

Donde ${displaystyle S!}$ significa «permanecer» o «esperar», es decir no mover el cabezal de lectura/escritura. Por lo tanto, ${displaystyle delta (q,sigma )=(p,sigma ',S)!}$ significa que se pasa del estado q al p, se escribe ${displaystyle sigma '}$ en la celda actual y la cabeza se queda sobre la celda actual.

Esta modificación se denota al igual que una MT sencilla, lo que la hace diferente es que la cinta es infinita tanto por la derecha como por la izquierda, lo cual permite realizar transiciones iniciales como ${displaystyle delta (q_{0},x)=(q_{1},y,L)!}$.

Es aquella que mediante la cual cada celda de la cinta de una máquina sencilla se divide en subceldas. Cada celda es así capaz de contener varios símbolos de la cinta. Por ejemplo, la cinta de la figura tiene cada celda subdividida en tres subceldas.

Se dice que esta cinta tiene múltiples pistas puesto que cada celda de esta máquina de Turing contiene múltiples caracteres, el contenido de las celdas de la cinta puede ser representado mediante n-tuplas ordenadas. Los movimientos que realice esta máquina dependerán de su estado actual y de la n-tupla que represente el contenido de la celda actual. Cabe mencionar que posee un solo cabezal al igual que una MT sencilla.

Una MT con más de una cinta consiste de un control finito con k cabezales lectores/escritores y k cintas. Cada cinta es infinita en ambos sentidos. La MT define su movimiento dependiendo del símbolo que está leyendo cada uno de sus cabezales, da reglas de sustitución para cada uno de los símbolos y dirección de movimiento para cada uno de los cabezales. Inicialmente la MT empieza con la entrada en la primera cinta y el resto de las cintas en blanco.

Una MT multidimensional es aquella cuya cinta puede verse como extendiéndose infinitamente en más de una dirección, el ejemplo más básico sería el de una máquina bidimensional cuya cinta se extendería infinitamente hacia arriba, abajo, derecha e izquierda.

En la modificación bidimensional de MT que se muestra en la figura también se agregan dos nuevos movimientos del cabezal {U,D} (es decir arriba y abajo). De esta forma la definición de los movimientos que realiza el cabezal será {L,R,U,D}.

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 del cabezal, las acciones a tomar en función de una entrada. En el caso de que para cada par (estado, 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 ${displaystyle delta }$ en el caso no determinista, queda definida como sigue:

¿Cómo sabe una máquina no determinista qué acción tomar de las varias posibles? Hay dos formas de verlo: una es decir que la máquina es "el mejor adivino posible", esto es, que siempre elige la transición que finalmente la llevará a un estado final de aceptación. La otra es imaginarse que la máquina se "clona", bifurcándose en varias copias, cada una de las cuales sigue una de las posibles transiciones. Mientras que una máquina determinista sigue un único "camino computacional", una máquina no determinista tiene un "árbol computacional". Si cualquiera de las ramas del árbol finaliza en un estado de aceptación, se dice que la máquina acepta la entrada.

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 ${displaystyle O(t(n))!}$, la máquina determinista equivalente reconocerá la palabra en un tiempo ${displaystyle 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.

El problema de la parada o problema de la detención (halting problem en inglés) para máquinas de Turing consiste en: dada una MT M y una palabra w, determinar si M terminará en un número finito de pasos cuando se ejecuta usando w como entrada.

Alan Turing, en su famoso artículo «On computable numbers, with an application to the Entscheidungsproblem» (1936), demostró que el problema de la parada de la máquina de Turing es indecidible, en el sentido de que ninguna máquina de Turing lo puede resolver.

Toda máquina de Turing puede codificarse como una secuencia binaria finita, es decir una secuencia finita de ceros y unos. Para simplificar la codificación, suponemos que toda MT tiene un único estado inicial denotado por ${displaystyle q_{1}!}$, y un único estado final denotado ${displaystyle q_{2}!}$. Tendremos que para una MT M de la forma

Todos estos símbolos se codifican como secuencias de unos:

Los estados de una MT ${displaystyle q_{1},q_{2},q_{3},ldots ,q_{n}!}$ se codifican también con secuencias de unos:

Las directrices de desplazamiento ${displaystyle R!}$, ${displaystyle L!}$ y ${displaystyle S!}$ se codifican con 1, 11, 111, respectivamente. Una transición ${displaystyle delta (q,a)=(p,c,R)!}$ se codifica usando ceros como separadores entre los estados, los símbolos del alfabeto de cinta y la directriz de desplazamiento ${displaystyle R!}$. Así, la transición ${displaystyle delta (q_{3},s_{2})=(q_{5},s_{3},R)!}$ se codifica como

En general, la codificación de una transición cualquiera ${displaystyle delta (q_{i},s_{k})=(q_{j},s_{l},R)!}$ es

donde ${displaystyle tin {1,2,3}!}$, según la dirección sea ${displaystyle mathrm {derecha} (R), mathrm {izquierda} (L), mathrm {esperar} (S)}$.

Una MT se codifica escribiendo consecutivamente las secuencias de las modificaciones de todas sus transiciones. Más precisamente, la codificación de una MT M es de la forma ${displaystyle C_{1}C_{2}ldots C_{i}!}$, donde ${displaystyle C_{i}!}$ es la codificación de la ${displaystyle i}$-ésima transición de M. Puesto que el orden en que se representen las transiciones de una MT no es relevante, una misma MT tiene varias codificaciones diferentes. Esto no representa ninguna desventaja práctica o conceptual ya que no se pretende que las codificaciones sean únicas.

Una máquina de Turing computa una determinada función parcial de carácter definido e 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 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ó:

Con esta codificación de tablas como cadenas, se abre la posibilidad 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.

El concepto de Máquina de Turing universal está relacionado con el de un sistema operativo básico, pues puede ejecutar cualquier instrucción computable sobre él.^[12]​

En 1985, Deutsch presentó el diseño de la primera Máquina cuántica basada en una máquina de Turing. Con este fin enunció una nueva variante la tesis de Church-Turing dando lugar al denominado "principio de Church-Turing-Deutsch".

La estructura de una máquina de Turing cuántica es muy similar a la de una máquina de Turing clásica. Está compuesta por los tres elementos clásicos:

El procesador contiene el conjunto de instrucciones que se aplica sobre el elemento de la cinta señalado por el cabezal. El resultado dependerá del qubit de la cinta y del estado del procesador. El procesador ejecuta una instrucción por unidad de tiempo.

La cinta de memoria es similar a la de una máquina de Turing tradicional. La única diferencia es que cada elemento de la cinta de la máquina cuántica es un qubit. El alfabeto de esta nueva máquina está formado por el espacio de valores del qubit. La posición del cabezal se representa con una variable entera.

Dos modelos matemáticos equivalentes a los de las máquinas de Turing son las máquinas de Post, creadas en forma paralela por Emil Leon Post,^[13]​ y el cálculo lambda, introducido por Alonzo Church y Stephen Kleene en los años 1930, y también usado por Church para demostrar en 1936 el Entscheidungsproblem.

---