Si seguimos embalados por este camino, llegaremos rápidamente a un autómata que pueda reconocer cualquier entrada. Así lo pensaron cuando comenzaron a diseñar estas primeras máquinas.
Al día de hoy, aunque se ha avanzado muchísimo, aún estamos lejos de autómatas que nos permitan resolver todo tipo de entradas.
Ejemplo 4. Máquina de Turing con cinta semi-infinita
La cinta de una MT de este modelo es finita a izquierda e infinita a derecha. Veamos que para toda MT M1 con cinta infinita existe una MT M2 equivalente con cinta semi infinita (el sentido inverso se prueba trivialmente).
Idea general.
Supongamos que M1 y M2 son MT del modelo inicial, con un conjunto de estados finales. Sean M1 = (Q1, Ʃ1, Γ1, δ1, q1, F1) y M2 = (Q2, Ʃ2, Γ2, δ2, q2, F2). Primeramente se debe introducir la noción de track (pista). En el caso más general, se puede asumir que
toda celda de una MT está dividida en T tracks, con T ≥ 1 (hasta el momento sólo se ha trabajado con celdas de un track). De este modo, el contenido de una celda puede representarse como una T-tupla (x1, …, xT), y las 5-tuplas de la función de transición δ
tienen la forma (qi, (x1, …, xT), q’i, (x’1, …, x’T), d), con d ∈ {L, R, S}. La MT M2 tiene 2 tracks. En el track superior simula los movimientos de M1 a la derecha de la celda inicial, incluyéndola, y en el track inferior los movimientos de M1 a la izquierda de la
misma. La entrada de M2 está al comienzo del track superior. Al empezar, M2 marca su primera sub-celda inferior con el símbolo especial #. Los símbolos de Γ2 tienen la forma (x, y). Todo símbolo x está en Γ1, y todo símbolo y está en Γ1 o es #. El estado corriente de M2 indica si se está considerando el track superior o inferior. Mientras M1 está a la derecha de su posición inicial, incluyéndola, M2 trabaja sobre el track superior, moviéndose en el sentido de M1. Y mientras M1 está a la izquierda de su posición
inicial, M2 trabaja sobre el track inferior, moviéndose en el sentido opuesto al de M1. Los estados de Q2 son q2 (estado inicial) más los distintos estados qU y qD tales que los estados q están en Q1 (con U por up o arriba y D por down o abajo se indica si se está
procesando el track superior o inferior, respectivamente). En particular, los estados de F2 son los estados qU y qD tales que los estados q están en F1.
Construcción de la MT M2.
Ya se han descripto los estados y símbolos de M2. La función de transición δ2 se define de la siguiente manera. Para el inicio de M2, en que hay que escribir la marca inicial #, y establecer si se procesa el track superior o inferior, se define:
- Si δ1(q1, x) = (q, y, R), entonces δ2(q2, (x, B)) = (qU, (y, #), R).
Si δ1(q1, x) = (q, y, S), entonces δ2(q2, (x, B)) = (qU, (y, #), S).
Si δ1(q1, x) = (q, y, L), entonces δ2(q2, (x, B)) = (qD, (y, #), R).
Para el procesamiento de M2 cuando el símbolo corriente no tiene la marca #, se define:
- Para todo (x, y) de Γ2, siendo el símbolo y distinto de #:
Si δ1(q, x) = (p, z, R), entonces δ2(qU, (x, y)) = (pU, (z, y), R).
Si δ1(q, x) = (p, z, L), entonces δ2(qU, (x, y)) = (pU, (z, y), L).
Si δ1(q, x) = (p, z, S), entonces δ2(qU, (x, y)) = (pU, (z, y), S).
Si δ1(q, y) = (p, z, R), entonces δ2(qD, (x, y)) = (pD, (x, z), L).
Si δ1(q, y) = (p, z, L), entonces δ2(qD, (x, y)) = (pD, (x, z), R).
Si δ1(q, y) = (p, z, S), entonces δ2(qD, (x, y)) = (pD, (x, z), S).
Finalmente, para el procesamiento de M2 cuando el símbolo corriente tiene la marca #, se define:
- Si δ1(q, x) = (p, y, R), entonces δ2(qU, (x, #)) = δ2(qD, (x, #)) = (pU, (y, #), R).
Si δ1(q, x) = (p, y, S), entonces δ2(qU, (x, #)) = δ2(qD, (x, #)) = (pU, (y, #), S).
Si δ1(q, x) = (p, y, L), entonces δ2(qU, (x, #)) = δ2(qD, (x, #)) = (pD, (y, #), R).
Ejemplo 5. Máquina de Turing con varias cintas
En el siguiente ejemplo se demuestra que las MT no ganan poder computacional cuando utilizan más de una cinta. Utilizaremos generalmente este modelo, con estados finales qA y qR, porque facilita la presentación de los ejemplos y las demostraciones de los teoremas.
Las MT de este modelo tienen una cantidad finita K de cintas. La cinta de entrada es siempre la primera. Cuando es necesario se especifica también una cinta de salida. Por cada cinta existe un cabezal, y sigue habiendo una sola unidad de control (ver la figura
siguiente):
En la configuración inicial, la cinta 1 contiene la entrada, la unidad de control almacena el estado q0, el cabezal de la cinta 1 (cabezal 1) apunta al primer símbolo de la entrada, y el resto de los cabezales apuntan a alguna celda de las cintas correspondientes, al comienzo todas en blanco. Luego la MT se comporta de acuerdo a su función de transición δ. En cada paso lee un estado y una K-tupla de símbolos, los apuntados, respectivamente, por los cabezales 1 a K, eventualmente los modifica, y se mueve en cada cinta un lugar a la derecha, a la izquierda o no se mueve. En cada cinta la MT se comporta de manera independiente, es decir que en una cinta puede modificar un símbolo y moverse a la derecha, en otra puede mantener el símbolo corriente y moverse a la izquierda, etc. Formalmente, asumiendo el uso de los estados qA y qR, se define M = (Q, Ʃ, Γ, δ, q0, qA, qR), tal que
δ: Q x ΓK → (Q ∪ {qA, qR}) x (Γ x {L, R, S})K
Por ejemplo, sea L = {w | w ∈ {a, b}* y w es un palíndrome}. Una cadena w es un palíndrome si y sólo si w = wR, siendo wR la cadena inversa de w. Se va a construir una MT M con 2 cintas que acepta L.
Idea general.
La MT M copia la entrada desde la cinta 1 a la cinta 2. Apunta al primer símbolo de la cadena de la cinta 1 y al último símbolo de la cadena de la cinta 2. E itera de la siguiente manera: compara los símbolos apuntados; si son distintos rechaza; si son blancos acepta; y en otro caso se mueve a la derecha en la cinta 1, a la izquierda en la cinta 2, y vuelve a la comparación de símbolos.
Construcción de la MT M.
Se define M = (Q, Ʃ, Γ, δ, q0, qA, qR), con:
- Q = {q0, q1, q2}. El estado q0 es el estado de copia de la entrada desde la cinta 1 a la cinta 2. El estado q1 es el estado de posicionamiento de los cabezales 1 y 2 luego de la copia. Y el estado q2 es el estado de comparación de las cadenas de las cintas 1 y 2.
- Ʃ = {a, b}
- Γ = {a, b, B}
- q0 = q0
- La función de transición δ es
Que el elemento de la tabla correspondiente al estado q0 y al par de símbolos a, B, por ejemplo, contenga la 5-tupla q0, a, R, a, R, significa que δ(q0, (a, B)) = (q0, (a, R), (a, R)), simplificando paréntesis. Queda como ejercicio probar que L(M) = L. Veamos ahora que para toda MT M1 con K cintas, existe una MT M2 equivalente con una sola cinta (el sentido inverso se prueba trivialmente).
Idea general.
La cinta de M2 tiene 2K tracks. Los primeros dos tracks representan la cinta 1 de M1, los siguientes dos tracks representan la cinta 2, y así sucesivamente. Dado un par de tracks que representan una cinta de M1, el primer track almacena en sus distintas subceldas el contenido de las celdas correspondientes de M1, mientras que en el segundo track hay blancos en todas las sub-celdas salvo en una que lleva la marca C, para indicar que la celda representada está apuntada por un cabezal. La tabla siguiente ejemplifica la representación descripta, para el caso de 3 cintas y por lo tanto 6 tracks:
De acuerdo a este ejemplo, la celda i + 1 de la cinta 1 de M1 tiene el símbolo x1 y está apuntada por el cabezal 1, la celda i + 2 de la cinta 2 tiene el símbolo x5 y no está apuntada por el cabezal 2, etc. Si la entrada de M1 es w = w1…wn , entonces al comienzo la entrada de M2 es (w1, B, …, B) … (wn, B, …, B), y el cabezal apunta al símbolo (w1, B, …, B). M2 empieza transformando el primer símbolo de su entrada en el símbolo (w1, C, B, C, …, B, C), y luego pasa a un estado que simula el estado inicial de M1. A partir de acá, cada paso de M1 es simulado por un conjunto de pasos de M2, primero de izquierda a derecha y luego de derecha a izquierda, de la siguiente manera:
- Al inicio de este conjunto de pasos de M2 , su cabezal apunta a la celda con la marca C de más a la izquierda.
- Luego M2 se mueve a la derecha, memorizando por medio de sus estados uno a uno los símbolos que están acompañados por una marca y a qué cinta están asociados. Por ejemplo, si se reconoce un símbolo xi acompañado por una marca correspondiente a la cinta k, el estado corriente de M2 incluirá un índice con el par (k, xi). El estado corriente de M2 memoriza además el número de marcas que quedan por detectar, que se actualiza cuando se encuentra una nueva marca.
- Cuando M2 reconoce todas las marcas, emprende la vuelta a la izquierda hasta que se encuentra otra vez con la marca de más a la izquierda, y se va comportando de acuerdo al estado de M1 que está siendo simulado. Toda vez que encuentra una marca modifica eventualmente el símbolo asociado que representa el contenido de M1, y la ubicación de la marca, según la información obtenida en el camino de ida y la función de transición de M1. M2 otra vez se vale de un contador para detectar cuántas marcas le quedan por recorrer en el camino de vuelta, que actualiza correspondientemente.
- Finalmente, M2 modifica su estado acorde a cómo lo modifica M1. Si en particular el estado de M1 es de aceptación, entonces M2 se detiene y acepta, y si es de rechazo, se detiene y rechaza.
Queda como ejercicio construir M2 y probar que L(M1) = L(M2). Notar que como luego de h pasos de la MT M1 sus cabezales pueden distanciarse a lo sumo 2h celdas, entonces a la MT M2 le va a llevar simular h pasos de M1 a lo sumo unos (4 + 8 + 12 + … + 4h) = 4(1 + 2 + 3 + … + h) = O(h2) pasos. Esto significa que si bien la cantidad de cintas no influye en el poder computacional de una MT, sí impacta en su tiempo de trabajo. El tiempo de retardo cuando se reduce de K cintas a una cinta, independientemente del valor de K, es del orden cuadrático en el peor caso. Esta relación la utilizaremos cuando tratemos la complejidad computacional temporal, en la segunda parte del libro.
Ejemplo 6. Máquina de Turing con un solo estado
Vamos a probar que para toda MT M1 con varios estados existe una MT M2 equivalente con un solo estado (el sentido inverso se prueba trivialmente).
Idea general.
Supongamos que M1 tiene una cinta y además de qA y qR, los estados q0, …, qm. Con una MT M2 con dos cintas y un solo estado q, además de qA y qR, se puede simular M1. M2 simula M1 en la cinta 1, y en la cinta 2 representa con símbolos nuevos x0, …, xm, los estados de M1. Al comienzo, M2 escribe en la cinta 2 el símbolo x0 que representa el estado inicial q0 de M1, y luego simula paso a paso M1, haciendo lo mismo salvo que en lugar de cambiar de estado cambia de símbolo en la cinta 2.
Construcción de la MT M2.
Sea M1 = (Q1, Ʃ, Γ1, δ1, q0, qA, qR) con una cinta y estados q0, …, qm. Se hace M2 = ({q}, Ʃ, Γ1 ∪ {x0, …, xm}, δ2, q, qA, qR) con dos cintas. La función de transición δ2 se define de la siguiente manera:
- ∀x ∈ Ʃ: δ2(q, (x, B)) = (q, (x, S), (x0, S)).
- Si δ1(qi , x) = (qk, x’, d), entonces δ2(q, (x, xi)) = (q, (x’, d), (xk, S)), con d ∈{L, R, S}, qk distinto de qA y qR .
- Si δ1(qi, x) = (qA, x’, d), entonces δ2(q, (x, xi)) = (qA, (x’, d), (xi , S)), con d ∈{L, R, S}.
- Lo mismo que 3 pero considerando qR en lugar de qA.
Ejemplo 7. Máquina de Turing no determinística
El siguiente es un último ejemplo de modelo equivalente de MT,donde se demuestra que las MT tampoco ganan poder computacional cuando son no determinísticas, es decir cuando a partir de un par (q, x) pueden tener varias transiciones.
La elección de por cuál terna (q’, x’, d) a partir de (q, x) la MT no determinística (o MTN) continúa, es como el nombre del modelo lo indica no determinística. Ahora se considera una relación de transición ∆, en lugar de una función de transición δ. Una manera de interpretar cómo trabaja una MTN M es suponer que todas sus computaciones o secuencias de pasos se ejecutan en paralelo. Asumiendo que tiene los estados qA y qR, M acepta una entrada w si a partir de w al menos una computación se detiene en qA. En caso contrario, es decir si todas las computaciones de M terminan en el estado qR o son infinitas, M rechaza w. La siguiente figura ilustra un posible comportamiento de una MTN M:
En la figura, los términos sí, no y loop, indican que la computación correspondiente se detiene en qA, se detiene en qR, o no se detiene, respectivamente. En este caso la MTN acepta la entrada w porque al menos una de sus computaciones la acepta.
Formalmente, asumiendo una sola cinta, se define M = (Q, Ʃ, Γ, ∆, q0, qA, qR), con
∆: Q x Γ → P((Q ∪ {qA, qR}) x Γ x {L, R, S})
siendo P((Q ∪ {qA, qR}) x Γ x {L, R, S}) el conjunto de partes de (Q ∪ {qA, qR}) x Γ x {L, R, S}, dado que por cada par de Q x Γ puede haber más de una terna definida de (Q ∪ {qA, qR}) x Γ x {L, R, S}. La cantidad máxima de ternas asociadas por la relación ∆ a un mismo par (q, x) se denomina grado de ∆. Por convención, la expresión ∆(q, x) = ∅ establece que ∆ no está definida para (q, x).
Una MT determinística (o MTD) es un caso particular de MTN, tal que su relación de transición tiene grado 1. Se demuestra a continuación que para toda MTN M1 existe una MTD M2 equivalente.
Idea general.
Para todo estado y todo símbolo de una MTN M1, existe un número finito de posibles siguientes pasos, digamos las alternativas 1, …, K, siendo K el grado de la relación de transición ∆. De esta manera, se puede representar cualquier computación de M1 mediante una secuencia de dígitos entre 1 y K, que denominaremos discriminante. Por ejemplo, la secuencia (3, 4, 1, 3, 2) representa una computación de M1 en la que en el primer paso se elige la tercera alternativa de ∆, en el segundo paso la cuarta alternativa, en el tercero la primera, etc. Algunos discriminantes pueden representar computaciones no válidas, dado que no siempre hay K alternativas para un par (q, x).
Se puede construir una MTD M2 equivalente a M1 con tres cintas. La primera cinta tiene la entrada. En la segunda cinta M2 genera sistemáticamente los discriminantes, de menor a mayor longitud y en orden numérico creciente considerando la misma longitud. Por ejemplo, los primeros discriminantes son: (1), …, (K), (1, 1), …, (1, K), …, (K, 1), …, (K, K), (1, 1, 1), …, (1, 1, K), … Este orden se denomina orden lexical canónico, o simplemente orden canónico, y será utilizado frecuentemente. Por último, en la tercera cinta M2 lleva a cabo la simulación de M1.
Por cada discriminante generado en la cinta 2, M2 copia la entrada en la cinta 3 y simula M1 teniendo en cuenta el discriminante, seleccionando paso a paso las opciones representadas de la relación ∆ de M1. Si existe una alternativa no válida en el discriminante, M2 genera el siguiente según el orden canónico. Si M1 acepta, entonces M2 acepta (M2 solamente acepta o no se detiene).
La simulación efectuada por la MTD M2 consiste en recorrer a lo ancho, empleando la técnica de breadth first search, el árbol de computaciones asociado a la MTN M1, en el sentido de que primero simula un paso de todas las computaciones de M1, después dos, después tres, etc. Naturalmente no sirve recorrer el árbol de computaciones a lo largo, es decir rama por rama, empleando la técnica de depth first search, porque al simular una rama infinita de M1 antes que una de aceptación, M2 nunca podrá ejecutar esta última.
Construcción de la MTD M2.
La parte más compleja de la construcción consiste en transformar la relación de transición ∆ en una función de transición δ. Básicamente, si por ejemplo ∆(q, x) = {(q1, x1, d1), (q2, x2, d2)}, entonces δ tendría transiciones del tipo δ(q, (y, 1, x)) = (q1, (y, S),
(1, R), (x1, d1)) y δ(q, (y, 2, x)) = (q2, (y, S), (2, R), (x2, d2)).
Prueba de L(M1) = L(M2).
Si w ∈ L(M1), entonces alguna computación de la MTN M1 acepta w. Por construcción, M2 acepta w la vez que el discriminante asociado a dicha computación se genera en su cinta 2. Por lo tanto, w ∈ L(M2).
Si w ∈ L(M2), entonces M2 acepta w a partir de un determinado discriminante que genera alguna vez en su cinta 2. Esto significa que existe una computación de M1 que acepta w. Por lo tanto, w ∈ L(M1).
Notar que si K es el grado de la relación de transición ∆ de M1, h pasos de M1 se simulan con a lo sumo unos K + 2K2 + 3K3 + … + hKh = O(Kh) pasos de M2. Esto significa que si bien el no determinismo no le agrega poder computacional a las MT, el tiempo de ejecución sí se impacta cuando se simula determinísticamente una MTN. El tiempo de retardo es del orden exponencial en el peor caso.
Dimos un buen pantallazo general de lo que son las máquians de Turing. Veremos que nos trae el lunes que viene.
