La Maquina de Turing - PhD Alejandro Puga

La máquina de Turing fue definida por el matemático inglés Alan Turing en 1930 y se trata de un modelo de computo meramente abstracto el cual es capas de manipular símbolos sobre una tira de cinta infinita dividida en espacios que actúan como memoria con un cabezal capaz de leer y escribir símbolos en la cinta (uno a la vez) y moverla de celda en celda a derecha e izquierda que cuenta con un registro de estado, si una celda no contiene símbolo, decimos que contiene el símbolo blanco, y además posee una tabla finita de instrucciones o tabla de acción la cual rige la maquina de acuerdo con dicha tabla de reglas, con el fin de demostrar las limitaciones de los métodos algorítmicos mediante su ejecución, es decir, adaptada para simular la lógica de cualquier algoritmo de computador de manera teórica por lo que 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 que ayuda a entender los límites del cálculo mecánico lo que nos da la complejidad del algoritmo mediante el conteo del numero de movimientos de la maquina cuando la entrada tiene un tamaño fijo n , cualquier deficiencia en la maquina de Turing significa una deficiencia en el método algorítmico empleado. Esta maquina funciona deacuerdo a la tabla de acción es capaz de reconocer lenguajes formales, dichos lenguajes son de acuerdo a la jerarquía de Chomsky:

Gramáticas de tipo 0: (sin restricciones), incluye a todas las gramáticas formales. Estas gramáticas generan todos los lenguajes capaces de ser reconocidos por una maquina de turing.
Gramáticas de tipo 1: (gramáticas sensibles al contexto) Estas gramáticas tienen reglas de la forma $\alpha A\beta \rightarrow \alpha \gamma \beta$ con $A$ un no terminal y $\alpha$ , $\beta$ y $\gamma$ cadenas de terminales y no terminales. Las cadenas $\alpha$ y $\beta$ pueden ser vacías, pero $\gamma$ no puede serlo. La regla $S\rightarrow \epsilon$ está permitida si $S$ no aparece en la parte derecha de ninguna regla. Por lo que son exactamente todos aquellos lenguajes reconocidos por una maquina de turing determinista cuya cinta de memoria está acotada por un cierto número entero de veces sobre la longitud de entrada, también conocidas como automatas linealmente acotados.
Gramáticas de tipo 2: (gramáticas libres del contexto) Las reglas son de la forma $A\rightarrow \gamma$ con $A$ un no terminal y $\gamma$ una cadena de terminales y no terminales, los cuales son reconocidos por un autómata con pila.
Gramáticas de tipo 3: (gramáticas regulares) se restringen a aquellas reglas que tienen en la parte izquierda un no terminal, y en la parte derecha un solo terminal, posiblemente seguido de un no terminal. La regla $S\rightarrow \epsilon$ también está permitida si $S$ no aparece en la parte derecha de ninguna regla, aceptados por un autómata finito.

básicamente es un dispositivo que transforma un INPUT en un OUTPUT, ambos formados por un código binario de unos y ceros.

¿Cuál es la importancia de la Máquina de Turing?

La importancia de la máquina de Turing es por dos razones, Primeramente la máquina de Turing fue uno de los primeros (si no el primero) modelos teóricos para las computadoras, lo cual significaba que se trata de la definición de los pasos del proceso de computo, 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 ya que simula la lógica de cualquier algoritmo de computador, de ahí su enorme potencial y valor, otro aspecto importante es que nos determina si un problema matemático puede ser resuelto o no.

Gracias a esto surgió una gran pregunta que sigue repercutiendo en el presente ¿Puede una maquina pensar?, Turing se cuestionaba acerca de la inteligencia de las máquinas y su respuesta al momento fue el siguiente texto

No quiero dar una definición de pensar, y si tuviera que hacerlo probablemente no podría decir
nada más que es un tipo de zumbido que entró en mi cabeza. Pero realmente no veo la
necesidad de acordar una definición. Lo importante es trazar una línea que divida las
propiedades de un cerebro, o de un hombre, que queremos discutir y aquellas que no. Me
gustaría sugerir un tipo de prueba que uno podría aplicarle a una máquina. Podría decirse que
es una prueba para ver si una máquina piensa, pero es mejor evitar esa cuestión, y decir que
las máquinas que aprueben son, digamos, máquinas de “Grado A”. La idea de esta prueba es
que una máquina tiene que intentar y pretender que es un hombre, respondiendo las
preguntas que le son dadas, y aprobará solo si la pretensión es razonablemente convincente.
Una considerable proporción de un jurado, que no deben ser expertos en máquinas, deben
ser convencidos por la pretensión. No se le permite al jurado ver la máquina –eso haría la
prueba muy fácil. Así que la máquina esta apartada en una habitación lejana y el jurado puede
hacerle preguntas, las cuales se le transmiten a la máquina y ella manda una respuesta
mecanografiada. Las preguntas pueden tratar cualquier tema. Y las preguntas no necesitan
realmente ser preguntas. Por ejemplo “Yo afirmo que tu eres una máquina”. De la misma
forma, a la máquina se le permite todo tipo de trucos para aparentar ser humano, como
esperar un poco antes de dar una respuesta, o cometer errores de ortografía, pero no puede
hacer manchas en el papel. Sería mejor suponer que cada jurado tiene que juzgar varias
veces, y algunas de esas veces realmente están tratando con un hombre y no con una
máquina. Esto evitaría que dijeran “debe ser una máquina” cada vez sin la consideración
apropiada.
Alan Turing

Esto dio origen al juego de la imitación el cual consistía en una conversación entre un hombre (A), una mujer (B) y el interrogador (C) cuyo sexo es irrelevante. El interrogador permanece en una habitación separada de A y de B. El objetivo del interrogador es determinar cuál de los otros dos jugadores es la mujer, mientras que el objetivo del hombre y la mujer es convencer al interrogador de que él/ella es la mujer. dicho juego no resulto relevante sino hasta 2014 que una máquina fue capaz de convencer a todos los jueces de que era un humano.

Un antecedente que se tiene de importancia de la maquina de Turing es que fue la que resolvió el problema de descifrar los mensajes nazis creados por la máquina enigma en la segunda guerra mundial.

Funcionamiento de la máquina de Turing

La máquina de Turing al tener un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, este borra el contenido anterior y escribe un nuevo valor por lo tanto las operaciones de movimiento o transición que se pueden realizar en esta máquina se limitan a cambiar de estado (o quedarse en el estado actual), escribir un símbolo (reemplazando el símbolo que existía o dejando el mismo) y mover la cabeza a la izquierda o derecha.

El cómputo se determina 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, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a escribir en la cinta.

Dicha cinta dividida en espacios llamados celdas actúa como memoria de lo que el cabezal va escribiendo, por lo que es donde se escriben y leen los símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado blanco como se hablo al inicio; dado un símbolo inicial en cierto estado se le la posición donde esta escrito el símbolo y se es remplazado por otro ya sea el mismo o diferente para pasar a la siguiente celda ya sea a la izquierda o a la derecha, siguiendo la lectura de acuerdo a la jerarquización de Chomsky para los lenguajes.

Clasificación de las maquinas de Turing

Máquina de Turing con movimiento de espera

La función de transición está definida por

$\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\},$

la cual puede ser modificada como

$\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R,S\}.$

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

Máquina de Turing con cinta infinita a ambos lados

La cinta es infinita tanto por la derecha como por la izquierda, lo cual permite realizar transiciones iniciales como

$\delta (q_{0},x)=(q_{1},y,L)\!$ .

Máquina de Turing con cinta multipista

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. solo posee un cabezal al igual que una MT sencilla.

Máquina de Turing multicinta

Una MT con más de una cinta consiste de un control finito con k cabezales y k cintas. Cada cinta es infinita en ambos sentidos. 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.

El lenguaje aceptado es recursivamente enumerable

Máquina de Turing multidimensional

Una MT multidimensional es aquella cuya cinta puede verse 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.

A la bidimensional MT se agregan dos nuevos movimientos del cabezal {U,D} arriba y abajo. De esta forma la definición de los movimientos que realiza el cabezal será {L,R,U,D}.

Máquina de Turing universal

Esta clasificación representa una gran importancia ya que nos provee lo que es el Turing completo, es decir, un sistema que tiene un poder computacional equivalente a la máquina de Turing universal ( el sistema y la máquina universal de Turing pueden emularse entre sí). En 1947, Turing indicó que

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

es un concepto destinado a unificar todas las funciones matemáticas computables por lo que le es posible imitar cualquier otra Máquina de Turing, ofreciéndonos el mismo output que lo haría esa misma Máquina. Esto significa algo muy importante y es que es una máquina programable. 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.

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

Una cinta de memoria infinita en donde cada elemento es un qubit.
Un procesador finito.
Un cabezal.

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 su única diferencia es que cada elemento de la cinta de la máquina cuántica es un qubit y el alfabeto de esta nueva máquina está formado por el espacio de valores del qubit.

Ejemplos

Ejemplo 1

Se utiliza el diagrama presentado para ordenar la lista {3,1,2}. Entonces la entrada debe ser ∆|3|1|2|∆,
donde el cabezal esta en el primer delta. Y en el estado inicial, el cabezal pasa de leer el
primer símbolo blanco a leer el número 3. Mientras se lean los elementos 1, 2 o 3 el cabezal se mueve
a la derecha; cuando se llega al símbolo blanco se regresa a la izquierda y lee el pivote que en este
caso es el número 2. Ahora, con el pivote fijo, regresa al primer número de la lista y se ejecuta $T_2$ .
Dentro de la máquina $T_2$ las opciones son: leer un número menor que el pivote y moverse a la
derecha, ver el pivote y moverse a la izquierda; o leer un número m mayor que el pivote, reescribir el
símbolo blanco y moverse a la derecha. En este caso, el cabezal lee el número m = 3 y lo cambia por
el símbolo blanco para después avanzar a la derecha. La lista al momento es ∆|∆|1|2|∆ (cabezal en el 1).
Ahora, el cabezal debe buscar el pivote moviéndose a la derecha por lo que cada vez que se lee un
elemento de la lista de elementos diferentes que el pivote se sigue avanzando a la derecha. Aquí, el
cabezal pasa por el número 1, luego el número 2 y se regresa a la izquierda. El cabezal está leyendo
el número $x$ = 1, que es menor que el pivote, lo cambia por m = 3 y se mueve a la izquierda. Se tiene
∆|∆|3|2|∆ (cabezal en el segundo delta).
Mientras se lea un número se mueve a la izquierda buscando el símbolo blanco. Cuando se encuentra
el símbolo blanco se reemplaza por $x$ = 1 y se mueve a la derecha, de modo que ∆|1|3|2|∆.
Se regresa al estado inicial de $T_n$ . En este momento se lee un número mayor que el pivote, m = 3, por
lo que se reescribe el símbolo blanco moviéndose a la derecha. En seguida se observa el pivote y se
mueve a la izquierda, ∆|1|∆|2|∆ (cabezal en el delta central). Como el cabezal está en el símbolo blanco, se mueve a la derecha y se cambia el pivote por el número 3: ∆|1|∆|3|∆. Después de recorrer a la izquierda hasta encontrar el símbolo blanco y luego un lugar a la derecha, se inicia $T_3$ dentro de $T_2$ . Como el cabezal está leyendo el número 3 en el primer estado de $T_3$ , se mueve a la izquierda sin modificar el símbolo actual. Se tiene ∆|1|∆|3|∆ (cabezal en delta central) y esto indica a la máquina que el cabezal queda estacionario y se alcanza el estado $ℎ_a$ para $T_3$ .
Así, continua la ejecución de $T_2$ en el estado que se encuentra justo debajo del recuadro de $T_m$ . El símbolo blanco indica que el cabezal se mueve hacia la izquierda para leer el número 1; este número, que es menor que el pivote, se fija y se llama $p$ . Se recorre a la izquierda hasta encontrar el símbolo blanco; el primer elemento de la sublista a ordenar se encuentra haciendo un movimiento a la derecha. Entonces se inicia $T_1$ y con la cinta ∆|1|∆|3|∆. Nuevamente, se alcanza el estado $ℎ_a$ de $T_1$ después de dos movimientos. Ahora, el estado actual es el que se encuentra a la derecha del recuadro de $T_p$ y se tiene ∆|1|∆|3|∆ (cabezal en primer delta). Solo resta encontrar el símbolo blanco mediante movimientos a la derecha. De este modo ∆|1|∆|3|∆ (cabezal en delta central) se cambia por ∆|1|2|3|∆ y se detiene $T_2$ dejando una lista ordenada.

Ejemplo 2

Definimos una máquina de Turing sobre el alfabeto {1,0}, 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 ${s_1, s_2, s_3, s_4, s_5}$ y el estado inicial es ${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):

La máquina realiza su proceso por medio de un bucle, en el estado inicial ${s_1}$ reemplaza el primer 1 con un 0, y pasa al estado ${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 ${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 ${s_4}$ vuelve a la izquierda saltando los 1, cuando encuentra un 0 (en el medio de la secuencia), pasa a ${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.