Tamaño de letra
Tema
Ancho de lectura
Tipografía

Apuntes · Capítulo 7Computabilidad

Máquinas de Turing

Máquinas de Turing

Las dos primeras partes del curso terminaron de la misma manera: con un lenguaje que el modelo no alcanza. Un autómata finito tiene una cantidad fija de memoria y no reconoce { 0n1n:n≥0 }\{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\}. Un autómata de pila tiene memoria sin límite, pero solo ve la cima, y no reconoce { anbncn:n≥0 }\{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n : n \geq 0 \,\}: lo demostramos la semana pasada con el lema de bombeo para lenguajes libres de contexto. Y sin embargo cualquiera de ustedes escribe en cinco minutos un programa en C++ que decide ese lenguaje. Los modelos que tenemos se quedan cortos frente a lo que una computadora hace.

Esta semana empieza la tercera parte, la de computabilidad, con el modelo que no se queda corto: la máquina de Turing. Es un autómata finito al que se le da una cinta donde puede leer y escribir, yendo y viniendo las veces que quiera. La definición es casi tan simple como la de un DFA. Lo que cambia es lo que se sostiene sobre ella: que todo lo que se puede calcular con un procedimiento mecánico, en cualquier computadora y en cualquier lenguaje de programación, lo puede calcular una de estas máquinas. Esa afirmación es la tesis de Church-Turing. Con ella, “no existe ningún algoritmo para este problema” pasa a ser un enunciado matemático que se puede demostrar, y eso es lo que haremos desde la semana 9.

La semana tiene dos mitades. En la primera se define la máquina, se aprende a seguirla escribiendo sus configuraciones, y se construyen tres, una de ellas para el lenguaje que derrotó a las gramáticas. Aparece además algo que ningún modelo anterior tenía: una máquina puede no detenerse nunca, y de ahí sale la diferencia entre reconocer un lenguaje y decidirlo. En la segunda mitad se le cambian piezas al modelo (más cintas, no determinismo, una impresora) y se demuestra cada vez que no gana poder. Esa resistencia a los cambios es el primer argumento a favor de la tesis.

Ruta de lectura.

Antes de clase (15–20 minutos): la introducción, Lo que les faltaba a los modelos anteriores y La definición formal. Antes de la sesión B, El modelo es robusto. Con eso llegan sabiendo qué es la cinta, qué es el cabezal y cómo se lee una transición.

En clase: Sesión A, de Lo que les faltaba a los modelos anteriores a Los tres niveles de descripción. Sesión B, de El modelo es robusto a Codificar objetos como cadenas.

Después de clase: el Resumen y los Ejercicios, para repasar. Antes del laboratorio, Configuraciones y Aceptar, rechazar o no detenerse otra vez, y El código de la semana. Para ampliar, las lecturas de apoyo del recuadro siguiente.

Lectura. Sipser, sec. 3.1 (Turing Machines), 3.2 (Variants of Turing Machines) y 3.3 (The Definition of Algorithm). Erickson, Models of Computation, nota 6 (Turing machines). Son apoyo: estos apuntes se pueden estudiar solos.

Código. Los programas de este capítulo están en code/week-07. Dentro del entorno del curso, entren a esa carpeta y corran make para compilar los ejemplos y make test para comprobarlos. Los comandos de este capítulo se corren desde ahí. El laboratorio está en lab/tm_sim.

Lo que les faltaba a los modelos anteriores

Pongan lado a lado lo que cada modelo puede hacer con su memoria.

Modelo Memoria Cómo la usa Un lenguaje que no alcanza
DFA, NFA El estado: una cantidad fija Lee la entrada una vez, de izquierda a derecha { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\}
PDA El estado y una pila sin límite Solo ve la cima; para ver lo de abajo tiene que borrar lo de arriba { anbncn }\{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n \,\}
Máquina de Turing El estado y una cinta sin límite Lee y escribe en cualquier celda, y vuelve sobre lo escrito Los de la semana 9

Al autómata finito le falta dónde anotar. Al autómata de pila le falta poder volver sobre lo anotado sin destruirlo: para comparar la cantidad de b\mathtt{b} con la de a\mathtt{a} tiene que vaciar la pila, y cuando llegan las c\mathtt{c} ya no queda nada con qué compararlas. Las dos cosas que faltan son escribir y volver.

Una máquina de Turing tiene las dos, y nada más:

  • una cinta (tape), dividida en celdas. Cada celda guarda un símbolo. La cinta empieza en una primera celda y sigue hacia la derecha sin fin;
  • un cabezal (head), que está sobre una celda. Puede leer el símbolo de esa celda, cambiarlo por otro y moverse una celda a la izquierda o a la derecha;
  • un control con una cantidad finita de estados, como el de un DFA.

Al empezar, la cadena de entrada está escrita en las primeras celdas, una celda por símbolo, y el cabezal está sobre la primera. Todas las demás celdas tienen un símbolo especial, el símbolo blanco (blank symbol), que se escribe ⊔\sqcup y que no es parte del alfabeto de entrada. Así la máquina sabe dónde termina la entrada: en el primer blanco.

Tres recuadros, uno por modelo. Arriba a la izquierda, el autómata finito: un control unido a la entrada 000111, que se lee una sola vez de izquierda a derecha; su memoria es solo el estado, una cantidad fija, no anota nada y no alcanza el lenguaje 0ⁿ1ⁿ. Arriba a la derecha, el autómata de pila: el mismo control y la entrada aabbcc, más una pila de la que solo se resalta la cima; su memoria es el estado y una pila sin límite, pero solo ve la cima y para ver lo de abajo tiene que borrar, y no alcanza aⁿbⁿcⁿ. Abajo, a todo el ancho, la máquina de Turing: una cinta con las celdas X, 0, 0, 1, 1, 1 y después blancos, que empieza en una primera celda y sigue sin fin hacia la derecha; el control está en el estado q₁ y de él baja el cabezal, que está sobre la segunda celda, la del primer 0, y puede moverse en los dos sentidos. El cabezal lee la celda, escribe en ella y se mueve una celda a la izquierda o a la derecha. Su memoria es el estado y una cinta sin límite: lee y escribe en cualquier celda, caminando hasta ella.Tres recuadros, uno por modelo. Arriba a la izquierda, el autómata finito: un control unido a la entrada 000111, que se lee una sola vez de izquierda a derecha; su memoria es solo el estado, una cantidad fija, no anota nada y no alcanza el lenguaje 0ⁿ1ⁿ. Arriba a la derecha, el autómata de pila: el mismo control y la entrada aabbcc, más una pila de la que solo se resalta la cima; su memoria es el estado y una pila sin límite, pero solo ve la cima y para ver lo de abajo tiene que borrar, y no alcanza aⁿbⁿcⁿ. Abajo, a todo el ancho, la máquina de Turing: una cinta con las celdas X, 0, 0, 1, 1, 1 y después blancos, que empieza en una primera celda y sigue sin fin hacia la derecha; el control está en el estado q₁ y de él baja el cabezal, que está sobre la segunda celda, la del primer 0, y puede moverse en los dos sentidos. El cabezal lee la celda, escribe en ella y se mueve una celda a la izquierda o a la derecha. Su memoria es el estado y una cinta sin límite: lee y escribe en cualquier celda, caminando hasta ella.
Los tres modelos, por lo que pueden hacer con su memoria. Al autómata finito le falta dónde anotar y al de pila, volver sobre lo anotado; la máquina de Turing escribe en la cinta y vuelve.

En cada paso la máquina mira dos cosas, el estado en el que está y el símbolo bajo el cabezal, y con eso hace tres: escribe un símbolo en esa celda, mueve el cabezal una celda y cambia de estado. No hay nada más. No hay variables, ni contadores, ni manera de saltar a una celda lejana: para llegar a ella hay que caminar.

Con eso ya se puede decidir { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\}, y la idea es la que usaría una persona con un lápiz: tachar el primer 0\mathtt{0}, ir a buscar el primer 1\mathtt{1} y tacharlo, volver, y repetir. Si al final todo quedó tachado, cada cero tuvo su uno.

Hay cuatro diferencias con un autómata finito, y cada una se va a notar:

  1. La máquina escribe en la cinta, además de leerla.
  2. El cabezal se mueve en los dos sentidos. La entrada se puede leer cuantas veces haga falta.
  3. La cinta no se acaba. Después de la entrada hay tantos blancos como la máquina quiera usar.
  4. Hay un estado para aceptar y otro para rechazar, y tienen efecto de inmediato: al entrar a uno de ellos la máquina se detiene, haya leído toda la entrada o no. Un DFA responde al terminar de leer; una máquina de Turing responde cuando quiere. O no responde.

Esa última posibilidad es la novedad incómoda de la semana, y tiene su propia sección.

Idea clave. Una máquina de Turing es un autómata finito con una cinta en la que puede escribir y sobre la que puede volver. La cantidad de estados sigue siendo fija. Lo que no tiene tope es la cinta.

La definición formal

Definición. Una máquina de Turing (Turing machine) es una séptupla M=(Q,Σ,Γ,δ,q0,qaccept,qreject)M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}}), donde QQ, Σ\Sigma y Γ\Gamma son conjuntos finitos y:

  1. QQ es el conjunto de los estados.
  2. Σ\Sigma es el alfabeto de entrada. No contiene el símbolo blanco ⊔\sqcup.
  3. Γ\Gamma es el alfabeto de la cinta. Contiene a ⊔\sqcup y a todo Σ\Sigma: ⊔∈Γ\sqcup \in \Gamma y Σ⊆Γ\Sigma \subseteq \Gamma.
  4. δ:Q′×Γ→Q×Γ×{L,R}\delta : Q' \times \Gamma \to Q \times \Gamma \times \{\mathrm{L}, \mathrm{R}\} es la función de transición, donde Q′=Q−{qaccept,qreject}Q' = Q - \{q_{\text{accept}}, q_{\text{reject}}\}.
  5. q0∈Qq_0 \in Q es el estado inicial.
  6. qaccept∈Qq_{\text{accept}} \in Q es el estado de aceptación.
  7. qreject∈Qq_{\text{reject}} \in Q es el estado de rechazo, y qreject≠qacceptq_{\text{reject}} \neq q_{\text{accept}}.

La pieza que hay que aprender a leer es δ\delta. Una transición

δ(q,a)=(r,b,R)\delta(q, a) = (r, b, \mathrm{R})

dice: si la máquina está en el estado qq y el cabezal lee aa, entonces escribe bb en esa celda, mueve el cabezal una celda a la derecha y pasa al estado rr. Con L\mathrm{L} en lugar de R\mathrm{R}, el cabezal va a la izquierda. Las tres cosas pasan en un solo paso, y siempre pasan las tres: la máquina no puede quedarse quieta, ni dejar de escribir. Para “no escribir” se escribe el mismo símbolo que se leyó, b=ab = a.

Vale la pena leer despacio el resto.

  • Hay dos alfabetos. La entrada solo usa símbolos de Σ\Sigma. La cinta puede tener además otros símbolos, que la máquina usa para trabajar: marcas, tachaduras, separadores. El blanco está en Γ\Gamma y no en Σ\Sigma, y por eso la entrada no puede tener blancos: el primer blanco de la cinta marca el final de la entrada.
  • δ\delta es una función: para cada estado y cada símbolo de la cinta hay exactamente una acción. La máquina es determinista. En la segunda mitad del capítulo quitaremos esa condición.
  • De qacceptq_{\text{accept}} y de qrejectq_{\text{reject}} no sale nada. Por eso δ\delta se define sobre Q′Q' y no sobre QQ: al entrar a uno de esos dos estados la máquina se detiene. Sipser escribe δ\delta sobre todo QQ; lo que haya en esas dos filas no se usa nunca, así que es la misma máquina.
  • Hay un solo estado de aceptación y uno solo de rechazo. En un DFA hacía falta un conjunto FF, porque aceptar dependía de dónde quedaba la máquina al acabarse la entrada. Aquí la máquina decide cuándo terminar, y basta un estado para cada respuesta.
  • QQ y Γ\Gamma son finitos. La tabla de δ\delta tiene ∣Q′∣⋅∣Γ∣|Q'| \cdot |\Gamma| casillas: la máquina es un objeto finito, que se puede escribir completo en una hoja. Lo que no tiene tope es la cinta.

El borde izquierdo y las casillas vacías

La definición deja dos detalles abiertos, y este curso los fija igual que Sipser.

La cinta tiene una primera celda. Es infinita solo hacia la derecha. Si el cabezal está en la primera celda y la transición dice L\mathrm{L}, el cabezal se queda donde está. La máquina escribe y cambia de estado como siempre; lo único que no ocurre es el movimiento. No es un error, y la máquina no se entera: si necesita saber dónde empieza la cinta, tiene que dejar una marca en la primera celda.

Una casilla vacía lleva a qrejectq_{\text{reject}}. Las tablas de este capítulo, y los archivos, casi nunca traen las ∣Q′∣⋅∣Γ∣|Q'| \cdot |\Gamma| transiciones. Las que faltan son las de los pares que “no deberían pasar” si la entrada está en el lenguaje. La convención es que un par (q,a)(q, a) sin transición escrita tiene esta:

δ(q,a)=(qreject,a,R)\delta(q, a) = (q_{\text{reject}}, a, \mathrm{R})

Con eso δ\delta vuelve a ser una función total, como pide la definición. Es el estado trampa de la semana 1, con la diferencia de que aquí no hace falta dibujarlo: caer en él termina la ejecución.

La máquina de 0ⁿ1ⁿ, como séptupla y como archivo

La máquina que tacha un cero y un uno por vuelta tiene cuatro estados de trabajo. Lo que cada uno hace:

Estado Lo que está haciendo
q0q_0 Está sobre el primer símbolo sin tachar de la izquierda. Si es un 0\mathtt{0}, lo tacha con X\mathtt{X}
q1q_1 Acaba de tachar un 0\mathtt{0}: camina a la derecha buscando el primer 1\mathtt{1}, y lo tacha con Y\mathtt{Y}
q2q_2 Acaba de tachar un 1\mathtt{1}: camina a la izquierda hasta la última X\mathtt{X}
q3q_3 Ya no quedan ceros: comprueba que a la derecha solo haya Y\mathtt{Y} hasta el primer blanco

Como séptupla: Q={q0,q1,q2,q3,qaccept,qreject}Q = \{q_0, q_1, q_2, q_3, q_{\text{accept}}, q_{\text{reject}}\}, Σ={0,1}\Sigma = \{\mathtt{0}, \mathtt{1}\}, Γ={0,1,X,Y,⊔}\Gamma = \{\mathtt{0}, \mathtt{1}, \mathtt{X}, \mathtt{Y}, \sqcup\}, y δ\delta dada por esta tabla, donde cada casilla es (estado, símbolo que escribe, movimiento) y una casilla vacía lleva a qrejectq_{\text{reject}}:

δ\delta 0\mathtt{0} 1\mathtt{1} X\mathtt{X} Y\mathtt{Y} ⊔\sqcup
q0q_0 (q1,X,R)(q_1, \mathtt{X}, \mathrm{R}) (q3,Y,R)(q_3, \mathtt{Y}, \mathrm{R}) (qaccept,⊔,R)(q_{\text{accept}}, \sqcup, \mathrm{R})
q1q_1 (q1,0,R)(q_1, \mathtt{0}, \mathrm{R}) (q2,Y,L)(q_2, \mathtt{Y}, \mathrm{L}) (q1,Y,R)(q_1, \mathtt{Y}, \mathrm{R})
q2q_2 (q2,0,L)(q_2, \mathtt{0}, \mathrm{L}) (q0,X,R)(q_0, \mathtt{X}, \mathrm{R}) (q2,Y,L)(q_2, \mathtt{Y}, \mathrm{L})
q3q_3 (q3,Y,R)(q_3, \mathtt{Y}, \mathrm{R}) (qaccept,⊔,R)(q_{\text{accept}}, \sqcup, \mathrm{R})

La misma tabla, como diagrama de estados. Cada flecha lleva lo que la máquina lee, lo que escribe y hacia dónde mueve el cabezal:

Diagrama de estados de la máquina de 0ⁿ1ⁿ, con los estados q₀, q₁, q₂, q₃ y q_accept, que tiene doble borde. Una flecha sin origen entra a q₀, el estado inicial, que está sobre el primer símbolo sin tachar. De q₀ a q₁, la flecha 0 → X, R. En q₁, que busca el primer 1 hacia la derecha, un bucle con 0 → 0, R y Y → Y, R. De q₁ a q₂, la flecha 1 → Y, L. En q₂, que vuelve hasta la última X, un bucle con 0 → 0, L y Y → Y, L. De q₂ a q₀, la flecha X → X, R. De q₀ a q₃, la flecha Y → Y, R: ya no quedan ceros. En q₃, que comprueba que solo queden Y, un bucle con Y → Y, R. De q₃ a q_accept y de q₀ a q_accept, flechas con blanco → blanco, R. Al pie se explica que cada flecha dice qué lee, qué escribe y hacia dónde va, de modo que con 0 → X, R la máquina lee 0, escribe X y va a la derecha, y que lo que no está dibujado lleva a q_reject: son las 9 casillas vacías de la tabla.Diagrama de estados de la máquina de 0ⁿ1ⁿ, con los estados q₀, q₁, q₂, q₃ y q_accept, que tiene doble borde. Una flecha sin origen entra a q₀, el estado inicial, que está sobre el primer símbolo sin tachar. De q₀ a q₁, la flecha 0 → X, R. En q₁, que busca el primer 1 hacia la derecha, un bucle con 0 → 0, R y Y → Y, R. De q₁ a q₂, la flecha 1 → Y, L. En q₂, que vuelve hasta la última X, un bucle con 0 → 0, L y Y → Y, L. De q₂ a q₀, la flecha X → X, R. De q₀ a q₃, la flecha Y → Y, R: ya no quedan ceros. En q₃, que comprueba que solo queden Y, un bucle con Y → Y, R. De q₃ a q_accept y de q₀ a q_accept, flechas con blanco → blanco, R. Al pie se explica que cada flecha dice qué lee, qué escribe y hacia dónde va, de modo que con 0 → X, R la máquina lee 0, escribe X y va a la derecha, y que lo que no está dibujado lleva a q_reject: son las 9 casillas vacías de la tabla.
La máquina de 0ⁿ1ⁿ como diagrama. El ciclo q₀, q₁, q₂ es una vuelta: tacha un cero, tacha un uno y regresa. El estado de rechazo no se dibuja.

En el formato del curso, descrito en code/formats.md, la séptupla es un archivo de texto con un campo por componente. El blanco se escribe _. Este es machines/zeros_ones.tm:

# Decide { 0^n 1^n : n >= 0 }.
states: q0 q1 q2 q3 q_accept q_reject
alphabet: 0 1
tape: 0 1 X Y _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q1 X R
q0 Y -> q3 Y R
q0 _ -> q_accept _ R
q1 0 -> q1 0 R
q1 Y -> q1 Y R
q1 1 -> q2 Y L
q2 0 -> q2 0 L
q2 Y -> q2 Y L
q2 X -> q0 X R
q3 Y -> q3 Y R
q3 _ -> q_accept _ R

Después de delta: va una línea por cada casilla llena: estado lee -> destino escribe movimiento. El programa show_tm lee un archivo y lo muestra como séptupla y como tabla, con un punto en las casillas vacías:

$ build/show_tm machines/zeros_ones.tm
Q = {q0, q1, q2, q3, q_accept, q_reject}
Σ = {0, 1}
Γ = {0, 1, X, Y, _}
q0 = q0, q_accept = q_accept, q_reject = q_reject

δ         0             1             X             Y             _
q0        q1 X R        .             .             q3 Y R        q_accept _ R
q1        q1 0 R        q2 Y L        .             q1 Y R        .
q2        q2 0 L        .             q0 X R        q2 Y L        .
q3        .             .             .             q3 Y R        q_accept _ R

transiciones escritas: 11 de 20

De las 20 casillas, 9 están vacías. Cada una es una situación en la que la entrada ya no puede estar en el lenguaje: por ejemplo, q0q_0 leyendo un 1\mathtt{1} quiere decir que queda un uno sin su cero.

En C++. El struct Tm de tm.h tiene los siete componentes con los nombres del formato: states, alphabet, tape, delta, start, accept y reject. La función δ\delta es un std::map cuya clave es el par (estado, símbolo) y cuyo valor es un Action con los tres resultados:

struct Action {
    std::string state;  // r
    char write = BLANK; // b
    char move = 'R';    // D: 'L' o 'R'
};

Un std::map guarda un solo valor por clave, así que la estructura ya impide que haya dos acciones para el mismo par. read_tm rechaza un archivo que las trae, uno con una transición que sale de accept o de reject, y uno que escribe un símbolo que no está en tape. En errors/ hay un ejemplo de cada error.

Configuraciones

Para seguir un DFA bastaba anotar el estado después de cada símbolo. Para seguir una máquina de Turing hay que anotar tres cosas, porque las tres cambian: el estado, el contenido de la cinta y la posición del cabezal. Las tres juntas son una configuración (configuration).

Definición. Una configuración de MM se escribe

u q vu\,q\,v

donde q∈Qq \in Q es el estado, uu y vv son cadenas sobre Γ\Gamma, el contenido de la cinta es uvuv seguido de blancos, y el cabezal está sobre el primer símbolo de vv.

El estado se escribe justo antes de la celda que el cabezal está leyendo. Así, X q1 011\mathtt{X}\,q_1\,\mathtt{011} quiere decir: la cinta tiene X011\mathtt{X011} y después blancos, el estado es q1q_1, y el cabezal está sobre el primer 0\mathtt{0}, que es la segunda celda. Es el dibujo de la sección anterior, con un cero y un uno menos.

Como después de uvuv todo es blanco, u q vu\,q\,v y u q v⊔u\,q\,v\sqcup son la misma configuración. Para tener una sola manera de escribirla, vv llega hasta el último símbolo que no es blanco; y si desde el cabezal todo es blanco, vv es un solo ⊔\sqcup. Los programas del curso la escriben así, con _ en lugar de ⊔\sqcup y con espacios alrededor del estado.

Una configuración produce la siguiente cuando la máquina da un paso. Para todos los símbolos a,b,ca, b, c de Γ\Gamma y todas las cadenas u,vu, v sobre Γ\Gamma:

u q bv  produce  uc r vsi δ(q,b)=(r,c,R)ua q bv  produce  u r acvsi δ(q,b)=(r,c,L)q bv  produce  r cvsi δ(q,b)=(r,c,L): el borde izquierdo\begin{aligned} u\,q\,bv &\ \text{ produce }\ uc\,r\,v && \text{si } \delta(q, b) = (r, c, \mathrm{R}) \\ ua\,q\,bv &\ \text{ produce }\ u\,r\,acv && \text{si } \delta(q, b) = (r, c, \mathrm{L}) \\ q\,bv &\ \text{ produce }\ r\,cv && \text{si } \delta(q, b) = (r, c, \mathrm{L}) \text{: el borde izquierdo} \end{aligned}

Las tres líneas dicen lo mismo que la sección anterior, ahora sobre cadenas. Con un movimiento a la derecha, el símbolo escrito cc queda a la izquierda del estado. Con uno a la izquierda, el estado retrocede un símbolo, y aa, que estaba a su izquierda, pasa a ser lo que el cabezal lee. La tercera línea es el caso en que no hay ningún aa: el cabezal está en la primera celda y no se mueve. Si vv es vacía en la primera línea, a la derecha del estado queda un blanco.

Algunas configuraciones tienen nombre:

  • la configuración inicial de MM con la entrada ww es q0 wq_0\,w: el estado inicial, la entrada en la cinta y el cabezal en la primera celda. Con w=εw = \varepsilon es q0 ⊔q_0\,\sqcup;
  • una configuración de aceptación es una cuyo estado es qacceptq_{\text{accept}}, y una de rechazo, una cuyo estado es qrejectq_{\text{reject}}. Las dos son configuraciones finales: no producen ninguna otra.

La ejecución de MM con ww es la secuencia C0,C1,C2,…C_0, C_1, C_2, \ldots en la que C0C_0 es la configuración inicial y cada CiC_i produce Ci+1C_{i+1}. Es única, porque δ\delta es una función. Termina si llega a una configuración final, y si no, sigue sin fin. El programa run_tm la imprime, con el número de paso a la izquierda:

$ build/run_tm machines/zeros_ones.tm 0011
w = 0011
    0  q0 0011
    1  X q1 011
    2  X0 q1 11
    3  X q2 0Y1
    4  q2 X0Y1
    5  X q0 0Y1
    6  XX q1 Y1
    7  XXY q1 1
    8  XX q2 YY
    9  X q2 XYY
   10  XX q0 YY
   11  XXY q3 Y
   12  XXYY q3 _
   13  XXYY_ q_accept _
  acepta en 13 pasos

Síganla con la tabla al lado. En la configuración 0 la máquina está en q0q_0 y lee 0\mathtt{0}: la tabla dice (q1,X,R)(q_1, \mathtt{X}, \mathrm{R}), y sale la configuración 1. En la 2 está en q1q_1 y lee 1\mathtt{1}: la tabla dice (q2,Y,L)(q_2, \mathtt{Y}, \mathrm{L}), y en la 3 el estado aparece un símbolo más a la izquierda, con la Y\mathtt{Y} ya escrita. Entre la 3 y la 5 la máquina vuelve hasta la X\mathtt{X} y da un paso a la derecha: terminó la primera vuelta, con un cero y un uno tachados. La segunda vuelta va de la 5 a la 10. En la 10, q0q_0 ya no encuentra un cero sino una Y\mathtt{Y}, y pasa a q3q_3, que recorre las Y\mathtt{Y} y acepta al llegar al primer blanco.

Animación de la máquina de zeros_ones.tm con la entrada 0011, un paso por cuadro. A la izquierda está el diagrama de estados, con el estado actual resaltado y un punto que recorre la flecha de la transición que se aplica. A la derecha, arriba, la cinta, con el cabezal sobre una celda y el estado escrito encima; debajo se va armando la lista de configuraciones, como la imprime run_tm. Al empezar, la configuración es q₀ 0011: el cabezal está en la primera celda. Paso 1: en q₀ lee 0, escribe X y va a la derecha en q₁; queda X q₁ 011. Paso 2: q₁ pasa sobre el otro 0; X0 q₁ 11. Paso 3: q₁ lee el primer 1, escribe Y y va a la izquierda en q₂; X q₂ 0Y1. Paso 4: q₂ retrocede sobre el 0; q₂ X0Y1. Paso 5: q₂ lee la X y va a la derecha en q₀; X q₀ 0Y1, y terminó la primera vuelta. Paso 6: q₀ tacha el 0 que queda; XX q₁ Y1. Paso 7: q₁ pasa sobre la Y; XXY q₁ 1. Paso 8: q₁ tacha el segundo 1; XX q₂ YY. Paso 9: q₂ retrocede sobre la Y; X q₂ XYY. Paso 10: q₂ lee la X y vuelve a q₀; XX q₀ YY, y terminó la segunda vuelta. Paso 11: q₀ lee una Y y pasa a q₃; XXY q₃ Y. Paso 12: q₃ pasa sobre la Y; XXYY q₃ y un blanco. Paso 13: q₃ lee el primer blanco y pasa a q_accept: la máquina acepta en 13 pasos, con la cinta XXYY.Animación de la máquina de zeros_ones.tm con la entrada 0011, un paso por cuadro. A la izquierda está el diagrama de estados, con el estado actual resaltado y un punto que recorre la flecha de la transición que se aplica. A la derecha, arriba, la cinta, con el cabezal sobre una celda y el estado escrito encima; debajo se va armando la lista de configuraciones, como la imprime run_tm. Al empezar, la configuración es q₀ 0011: el cabezal está en la primera celda. Paso 1: en q₀ lee 0, escribe X y va a la derecha en q₁; queda X q₁ 011. Paso 2: q₁ pasa sobre el otro 0; X0 q₁ 11. Paso 3: q₁ lee el primer 1, escribe Y y va a la izquierda en q₂; X q₂ 0Y1. Paso 4: q₂ retrocede sobre el 0; q₂ X0Y1. Paso 5: q₂ lee la X y va a la derecha en q₀; X q₀ 0Y1, y terminó la primera vuelta. Paso 6: q₀ tacha el 0 que queda; XX q₁ Y1. Paso 7: q₁ pasa sobre la Y; XXY q₁ 1. Paso 8: q₁ tacha el segundo 1; XX q₂ YY. Paso 9: q₂ retrocede sobre la Y; X q₂ XYY. Paso 10: q₂ lee la X y vuelve a q₀; XX q₀ YY, y terminó la segunda vuelta. Paso 11: q₀ lee una Y y pasa a q₃; XXY q₃ Y. Paso 12: q₃ pasa sobre la Y; XXYY q₃ y un blanco. Paso 13: q₃ lee el primer blanco y pasa a q_accept: la máquina acepta en 13 pasos, con la cinta XXYY.
La ejecución con 0011: dos vueltas que tachan un cero y un uno cada una, y la comprobación final. En cada configuración, el estado se escribe justo antes de la celda que el cabezal lee.

En C++. Una configuración es un struct Config con el estado, las celdas y la posición del cabezal. Un paso es leer la casilla de δ\delta y aplicarla. La cinta crece solo cuando el cabezal llega a una celda que todavía no existe, y el borde izquierdo es el if del final:

inline void apply(Config& c, const Action& action) {
    if (c.head >= c.cells.size()) {
        c.cells.resize(c.head + 1, BLANK);
    }
    c.cells[c.head] = action.write;
    c.state = action.state;
    if (action.move == 'R') {
        c.head++;
    } else if (c.head > 0) {
        c.head--;  // en la primera celda, L no mueve el cabezal
    }
}

La cinta infinita se representa con un std::string finito: las celdas que no están en cells tienen un blanco. En cualquier momento la máquina ha visitado una cantidad finita de celdas, así que siempre alcanza.

Error común. Escribir el estado después del símbolo que se está leyendo. En u q vu\,q\,v el cabezal está sobre el primer símbolo de vv, a la derecha del estado. La configuración X q1 011\mathtt{X}\,q_1\,\mathtt{011} lee un 0\mathtt{0} y no la X\mathtt{X}.

Aceptar, rechazar o no detenerse

Definición. MM acepta ww si su ejecución con ww llega a una configuración de aceptación. La rechaza si llega a una de rechazo. El lenguaje de MM es el conjunto de las cadenas que acepta:

L(M)={ w∈Σ∗:M acepta w }L(M) = \{\, w \in \Sigma^* : M \text{ acepta } w \,\}

Se dice que MM reconoce L(M)L(M).

Hasta aquí es lo mismo que en las semanas anteriores. La diferencia está en lo que la definición no dice: que la ejecución llegue a alguna de las dos. Con una entrada, una máquina de Turing puede terminar de tres maneras:

  1. llega a qacceptq_{\text{accept}} y acepta;
  2. llega a qrejectq_{\text{reject}} y rechaza;
  3. no se detiene nunca: la ejecución es una secuencia infinita de configuraciones.

Un DFA no tenía la tercera, porque lee un símbolo por paso y la entrada se acaba. Aquí nada obliga a la máquina a avanzar hacia un final.

Las dos primeras maneras se ven en ejecuciones cortas de la máquina de la sección anterior:

$ build/run_tm machines/zeros_ones.tm '' 010
w = ε
    0  q0 _
    1  _ q_accept _
  acepta en 1 paso
w = 010
    0  q0 010
    1  X q1 10
    2  q2 XY0
    3  X q0 Y0
    4  XY q3 0
    5  XY0 q_reject _
  rechaza en 5 pasos

Con la cadena vacía, q0q_0 lee un blanco y acepta: cero ceros y cero unos. Con 010\mathtt{010}, en la configuración 4 la máquina está en q3q_3 y lee un 0\mathtt{0}. Esa casilla de la tabla está vacía, y la máquina pasa a qrejectq_{\text{reject}}.

Para la tercera manera hace falta otra máquina. Esta es machines/has_one_loops.tm: busca un 1\mathtt{1} caminando hacia la derecha, y no deja de buscar cuando la entrada se acaba.

# Reconoce las cadenas binarias que tienen algún 1, y NO decide ese lenguaje:
# con una cadena sin unos sigue buscando hacia la derecha para siempre.
states: q0 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q0 0 R
q0 1 -> q_accept 1 R
q0 _ -> q0 _ R

Un simulador no puede esperar para siempre, así que run_tm da a lo sumo una cantidad de pasos, que se fija con --limit. La opción --show 6 hace que imprima solo las primeras 6 configuraciones.

$ build/run_tm --limit 1000000 --show 6 machines/has_one_loops.tm 00 001
w = 00
    0  q0 00
    1  0 q0 0
    2  00 q0 _
    3  00_ q0 _
    4  00__ q0 _
    5  00___ q0 _
    …
  no se detuvo en 1000000 pasos
w = 001
    0  q0 001
    1  0 q0 01
    2  00 q0 1
    3  001 q_accept _
  acepta en 3 pasos

Con 001\mathtt{001} la máquina encuentra el uno y acepta. Con 00\mathtt{00} pasa la entrada y sigue caminando sobre blancos.

Hay que tener cuidado con lo que dice la última línea de la primera ejecución. “No se detuvo en 1 000 000 de pasos” es un hecho sobre un millón de pasos. No dice que la máquina no se detenga nunca: podría detenerse en el paso 1 000 001. Que esta máquina no se detiene con 00\mathtt{00} no lo muestra el programa. Se demuestra.

Afirmación. Sea w=0nw = \mathtt{0}^n. Para todo t≥nt \geq n, la configuración de la máquina después de tt pasos es 0n⊔t−n q0 ⊔\mathtt{0}^n\sqcup^{t-n}\,q_0\,\sqcup.

Demostración. Por inducción sobre tt. Durante los primeros nn pasos la máquina está en q0q_0 leyendo ceros, y la transición (q0,0,R)(q_0, \mathtt{0}, \mathrm{R}) la lleva una celda a la derecha cada vez sin cambiar nada: después de nn pasos la configuración es 0n q0 ⊔\mathtt{0}^n\,q_0\,\sqcup, que es la de la afirmación con t=nt = n. Si después de tt pasos la configuración es 0n⊔t−n q0 ⊔\mathtt{0}^n\sqcup^{t-n}\,q_0\,\sqcup, la máquina lee un blanco en q0q_0, y la transición (q0,⊔,R)(q_0, \sqcup, \mathrm{R}) produce 0n⊔t−n+1 q0 ⊔\mathtt{0}^n\sqcup^{t-n+1}\,q_0\,\sqcup, que es la de la afirmación con t+1t + 1. ∎

Ninguna de esas configuraciones es final, así que la ejecución no termina. Las pruebas de la semana comprueban la afirmación con 000\mathtt{000} hasta t=1 000 000t = 1\,000\,000.

En este ejemplo, además, ninguna configuración se repite: el cabezal está cada vez en una celda distinta. “No detenerse” no quiere decir dar vueltas por las mismas configuraciones. Puede pasar eso, y entonces es fácil de detectar. La máquina machines/left_end.tm va hasta el final de la entrada y después se mueve a la izquierda sin parar:

$ build/run_tm --limit 8 machines/left_end.tm 01
w = 01
    0  q0 01
    1  0 q0 1
    2  01 q0 _
    3  0 q1 1
    4  q1 01
    5  q1 01
    6  q1 01
    7  q1 01
    8  q1 01
  no se detuvo en 8 pasos

En la configuración 4 el cabezal llegó a la primera celda. Desde ahí cada paso es un movimiento L\mathrm{L} en el borde izquierdo: el cabezal no se mueve y la configuración es siempre la misma. Una configuración que se repite garantiza que la máquina no se detiene, porque de la misma configuración sale siempre la misma ejecución. Pero la máquina anterior muestra que no detenerse no exige repetir.

Idea clave. Con una entrada, una máquina de Turing acepta, rechaza o no se detiene. Mirar la ejecución no permite distinguir “no se detiene” de “todavía no se detuvo”. Esa es la diferencia con todos los modelos anteriores, y de ella sale la segunda mitad del curso.

En la práctica. El veredicto TLE del juez es exactamente la respuesta “no se detuvo en NN pasos”: el juez no sabe si su programa tiene un ciclo infinito o si solo era lento, y por eso corta a los 2 segundos. Lo mismo hacen el tiempo máximo de una consulta en una base de datos, el de una prueba en un sistema de integración continua y el aviso de “esta página no responde” del navegador. En la semana 9 veremos que no pueden hacer otra cosa.

Tres máquinas, paso a paso

Diseñar una máquina de Turing es programar con un solo puntero y sin variables. Lo que funciona casi siempre es lo mismo que en la primera máquina: marcar en la cinta lo que ya se procesó, y hacer vueltas que procesan un poco cada una. Los estados recuerdan en qué parte de la vuelta está la máquina, y a veces un símbolo que lleva de un lado a otro.

0ⁿ1ⁿ

Ya vimos la máquina y una ejecución. Falta demostrar que hace lo que decimos, y contar cuánto tarda.

Llamemos vuelta al tramo de la ejecución que empieza con la máquina en q0q_0 leyendo un 0\mathtt{0} y termina la siguiente vez que entra a q0q_0. En una vuelta, la máquina tacha ese cero con X\mathtt{X}, camina en q1q_1 hacia la derecha sobre ceros y Y\mathtt{Y} hasta un 1\mathtt{1}, lo tacha con Y\mathtt{Y}, y vuelve en q2q_2 hasta la X\mathtt{X} que acaba de escribir.

Afirmación (lo que conserva cada vuelta). Sea ww la entrada. Si la máquina completa ii vueltas, entonces al terminar la última está en q0q_0 con el cabezal en la celda ii (contando desde 0) y:

  1. las celdas 0,…,i−10, \ldots, i - 1 tienen X\mathtt{X}, y en ww tenían 0\mathtt{0};
  2. exactamente ii de las demás celdas tienen Y\mathtt{Y}, y en ww tenían 1\mathtt{1};
  3. todas las otras celdas están como en ww.

Demostración. Por inducción sobre ii. Para i=0i = 0 la máquina está en la configuración inicial: en q0q_0, en la celda 0, con la cinta igual a ww. Supongamos que vale para ii y que la máquina completa una vuelta más. La vuelta empieza en q0q_0 leyendo un 0\mathtt{0} en la celda ii. Esa celda no tiene X\mathtt{X} ni Y\mathtt{Y}, así que por (3) también era un 0\mathtt{0} en ww, y la máquina escribe ahí una X\mathtt{X}. Después, q1q_1 avanza sin cambiar nada hasta leer un 1\mathtt{1}; por la misma razón era un 1\mathtt{1} de ww, y la máquina lo cambia por Y\mathtt{Y}: ahora hay i+1i + 1 celdas con Y\mathtt{Y}. Por último, q2q_2 retrocede sobre las celdas que q1q_1 acaba de recorrer, que solo tienen ceros y Y\mathtt{Y}, hasta la primera X\mathtt{X} que encuentra, que es la de la celda ii, y da un paso a la derecha: queda en q0q_0 en la celda i+1i + 1. Las tres condiciones valen para i+1i + 1. ∎

Teorema. La máquina de zeros_ones.tm decide { 0n1n:n≥0 }\{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\}: acepta las cadenas de esa forma, y rechaza todas las demás.

Demostración. Son tres partes: acepta solo cadenas del lenguaje, acepta todas las del lenguaje, y se detiene siempre.

Si acepta ww, entonces w=0n1nw = \mathtt{0}^n\mathtt{1}^n. La máquina solo entra a qacceptq_{\text{accept}} leyendo un blanco, desde q0q_0 o desde q3q_3. Digamos que antes completó ii vueltas, y sea nn la longitud de ww. Como la máquina nunca escribe un blanco sobre la entrada ni un símbolo sobre un blanco, las celdas con algo escrito son siempre las nn primeras.

  • Si acepta desde q0q_0: está en la celda ii y lee un blanco, así que i=ni = n y las celdas 0,…,n−10, \ldots, n - 1 tienen todas X\mathtt{X} por (1). Por (2) hay además ii celdas con Y\mathtt{Y}, y no queda ninguna celda para ellas: i=0i = 0. Entonces n=0n = 0 y w=ε=0010w = \varepsilon = \mathtt{0}^0\mathtt{1}^0.
  • Si acepta desde q3q_3: la máquina leyó una Y\mathtt{Y} en la celda ii en el estado q0q_0, y después q3q_3 solo leyó Y\mathtt{Y} hasta el primer blanco. Entonces las celdas i,…,n−1i, \ldots, n - 1 tienen todas Y\mathtt{Y}. Por (2) son exactamente ii celdas, así que n=2in = 2i; por (1) las primeras ii celdas de ww eran ceros, y por (2) las otras ii eran unos. Es decir, w=0i1iw = \mathtt{0}^i\mathtt{1}^i.

Si w=0n1nw = \mathtt{0}^n\mathtt{1}^n, la acepta. Si n=0n = 0, acepta en un paso. Si n≥1n \geq 1, después de ii vueltas, con i<ni < n, la configuración es

Xi q0 0n−iYi1n−i\mathtt{X}^i\,q_0\,\mathtt{0}^{n-i}\mathtt{Y}^i\mathtt{1}^{n-i}

y la vuelta siguiente se completa: hay un cero bajo el cabezal, q1q_1 pasa sobre n−i−1n - i - 1 ceros e ii letras Y\mathtt{Y} y encuentra un uno, y q2q_2 vuelve. Se ve por inducción sobre ii, siguiendo la tabla. Después de nn vueltas la configuración es Xn q0 Yn\mathtt{X}^n\,q_0\,\mathtt{Y}^n: la máquina pasa a q3q_3, recorre las Y\mathtt{Y} y acepta en el primer blanco.

Se detiene con toda entrada. Sea n=∣w∣n = |w|. Cada vuelta tacha dos celdas que no estaban tachadas, y una celda tachada no se vuelve a cambiar: hay a lo sumo n/2n/2 vueltas. Una vuelta que empieza en la celda pp y tacha el uno de la celda jj da j−p+1j - p + 1 pasos hasta escribir la Y\mathtt{Y}, otros j−p−1j - p - 1 para volver, y uno más sobre la X\mathtt{X}: son 2(j−p)+1≤2n−12(j - p) + 1 \leq 2n - 1 pasos. Cuando la máquina entra a q0q_0 y ya no completa otra vuelta, a partir de ahí solo se mueve a la derecha, en q0q_0, q1q_1 o q3q_3, y se detiene a más tardar al leer el primer blanco, en la celda nn: son a lo sumo n+2n + 2 pasos. En total da a lo sumo

n2(2n−1)+n+2≤n2+n+2\frac{n}{2}(2n - 1) + n + 2 \leq n^2 + n + 2

pasos. Como se detiene siempre y solo acepta las cadenas del lenguaje, rechaza todas las demás. ∎

La cota no es exagerada. Con w=0n1nw = \mathtt{0}^n\mathtt{1}^n se puede contar exacto: en la vuelta número ii, la máquina tacha el cero (1 paso), avanza sobre n−in - i ceros e i−1i - 1 letras Y\mathtt{Y} (n−1n - 1 pasos), tacha el uno (1 paso), retrocede sobre lo mismo (n−1n - 1 pasos) y pasa sobre la X\mathtt{X} (1 paso). Son 2n+12n + 1 pasos por vuelta, y hay nn vueltas. Al final, q0q_0 lee una Y\mathtt{Y} (1 paso), q3q_3 recorre las otras n−1n - 1 y lee el blanco. En total:

n(2n+1)+1+(n−1)+1=2n2+2n+1.n(2n + 1) + 1 + (n - 1) + 1 = 2n^2 + 2n + 1.
$ build/run_tm --quiet machines/zeros_ones.tm 01 0011 000111 00001111
w = 01
  acepta en 5 pasos
w = 0011
  acepta en 13 pasos
w = 000111
  acepta en 25 pasos
w = 00001111
  acepta en 41 pasos

Para n=1,2,3,4n = 1, 2, 3, 4 la fórmula da 5, 13, 25 y 41. La entrada tiene longitud 2n2n, así que la máquina tarda un tiempo cuadrático en la longitud de la entrada: va y viene una vez por cada par. Un programa en C++ hace lo mismo con una sola pasada. Esa diferencia no importa esta semana, en la que solo preguntamos qué se puede calcular, y va a importar desde la semana 12.

w#w

Lenguaje. { w#w:w∈{0,1}∗ }\{\, w\mathtt{\#}w : w \in \{\mathtt{0}, \mathtt{1}\}^* \,\}: dos copias de la misma cadena, con un separador en medio. Sin el separador, { ww }\{\, ww \,\} es uno de los lenguajes que no eran libres de contexto la semana pasada. Con el separador tampoco lo es, y una máquina de Turing lo decide sin dificultad.

Una nota sobre el separador antes de seguir. En la teoría se escribe #\mathtt{\#}, como en Sipser. En los archivos del curso ese carácter empieza un comentario y no puede ser un símbolo, así que en el archivo y en lo que imprimen los programas el separador es =. La máquina es la misma.

La idea. Comparar el primer símbolo de la izquierda con el primero de la derecha, después el segundo con el segundo, y así. Como la máquina no puede recordar posiciones, tacha lo que ya comparó. Y como no puede recordar una cadena, lleva un símbolo por viaje, guardado en el estado: hay un estado para “llevo un 0\mathtt{0}” y otro para “llevo un 1\mathtt{1}”.

Estado Lo que está haciendo
q0q_0 Está sobre el primer símbolo sin tachar de la izquierda. Lo tacha y recuerda cuál era
q1q_1, q2q_2 Lleva un 0\mathtt{0} (q1q_1) o un 1\mathtt{1} (q2q_2): camina a la derecha hasta el separador
q3q_3, q4q_4 Ya pasó el separador llevando un 0\mathtt{0} (q3q_3) o un 1\mathtt{1} (q4q_4): salta las X\mathtt{X} y compara. Si coincide, lo tacha
q5q_5 Vuelve hacia la izquierda sobre las X\mathtt{X}, hasta el separador
q6q_6 Sigue volviendo sobre los símbolos sin tachar, hasta la última X\mathtt{X} de la izquierda
q7q_7 La izquierda se acabó: comprueba que a la derecha del separador solo haya X\mathtt{X}
$ build/show_tm machines/w_sep_w.tm
Q = {q0, q1, q2, q3, q4, q5, q6, q7, q_accept, q_reject}
Σ = {0, 1, =}
Γ = {0, 1, =, X, _}
q0 = q0, q_accept = q_accept, q_reject = q_reject

δ         0             1             =             X             _
q0        q1 X R        q2 X R        q7 = R        .             .
q1        q1 0 R        q1 1 R        q3 = R        .             .
q2        q2 0 R        q2 1 R        q4 = R        .             .
q3        q5 X L        .             .             q3 X R        .
q4        .             q5 X L        .             q4 X R        .
q5        .             .             q6 = L        q5 X L        .
q6        q6 0 L        q6 1 L        .             q0 X R        .
q7        .             .             .             q7 X R        q_accept _ R

transiciones escritas: 20 de 40

Las casillas vacías hacen buena parte del trabajo. La de q3q_3 con 1\mathtt{1} es la comparación que falla: la máquina lleva un cero y encuentra un uno. Las de q3q_3 con el separador y con el blanco rechazan una entrada en la que, donde tenía que estar el símbolo por comparar, hay otro separador o ya no hay nada. La de q0q_0 con el blanco rechaza la cadena vacía, que no tiene separador.

$ build/run_tm machines/w_sep_w.tm 01=01
w = 01=01
    0  q0 01=01
    1  X q1 1=01
    2  X1 q1 =01
    3  X1= q3 01
    4  X1 q5 =X1
    5  X q6 1=X1
    6  q6 X1=X1
    7  X q0 1=X1
    8  XX q2 =X1
    9  XX= q4 X1
   10  XX=X q4 1
   11  XX= q5 XX
   12  XX q5 =XX
   13  X q6 X=XX
   14  XX q0 =XX
   15  XX= q7 XX
   16  XX=X q7 X
   17  XX=XX q7 _
   18  XX=XX_ q_accept _
  acepta en 18 pasos

La primera vuelta va de la configuración 0 a la 7: la máquina tacha el 0\mathtt{0}, lo lleva en q1q_1 hasta el separador, lo compara en q3q_3 con el primer símbolo de la derecha, lo tacha, y vuelve. La segunda, de la 7 a la 14, hace lo mismo con el 1\mathtt{1}, en q2q_2 y q4q_4; en la configuración 9 se ve a q4q_4 saltando la X\mathtt{X} de la vuelta anterior. En la 14, q0q_0 encuentra el separador: la izquierda está toda tachada, y q7q_7 comprueba que la derecha también.

Una ejecución que rechaza, y el caso más pequeño que acepta:

$ build/run_tm machines/w_sep_w.tm 01=00 =
w = 01=00
    0  q0 01=00
    1  X q1 1=00
    2  X1 q1 =00
    3  X1= q3 00
    4  X1 q5 =X0
    5  X q6 1=X0
    6  q6 X1=X0
    7  X q0 1=X0
    8  XX q2 =X0
    9  XX= q4 X0
   10  XX=X q4 0
   11  XX=X0 q_reject _
  rechaza en 11 pasos
w = =
    0  q0 =
    1  = q7 _
    2  =_ q_accept _
  acepta en 2 pasos

En la configuración 10 la máquina lleva un 1\mathtt{1} y lee un 0\mathtt{0}. La entrada que es solo el separador está en el lenguaje, con w=εw = \varepsilon.

La máquina se detiene siempre, por el mismo argumento de antes: cada vuelta tacha al menos dos celdas, primero camina solo a la derecha y después solo a la izquierda, y lo que queda al final es un tramo hacia la derecha. La cota n2+n+2n^2 + n + 2 vale igual. Con w#ww\mathtt{\#}w y ∣w∣=n|w| = n son exactamente 2n2+4n+22n^2 + 4n + 2 pasos, y la cuenta queda como ejercicio; las pruebas la comprueban hasta n=40n = 40. La demostración de que acepta exactamente el lenguaje sigue el esquema de la anterior, con una afirmación sobre lo que conserva cada vuelta, y es el ejercicio 5.

aⁿbⁿcⁿ

Lenguaje. { anbncn:n≥0 }\{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n : n \geq 0 \,\}, el que no era libre de contexto.

La idea. La de la primera máquina, con un símbolo más: en cada vuelta se tacha una a\mathtt{a}, una b\mathtt{b} y una c\mathtt{c}. Lo que al autómata de pila le resultaba imposible aquí no cuesta nada, porque tachar no destruye: las marcas de las b\mathtt{b} siguen en la cinta cuando llega el turno de las c\mathtt{c}.

Estado Lo que está haciendo
q0q_0 Está sobre el primer símbolo sin tachar de la izquierda. Si es una a\mathtt{a}, la tacha con X\mathtt{X}
q1q_1 Busca la primera b\mathtt{b}, pasando sobre a\mathtt{a} e Y\mathtt{Y}. La tacha con Y\mathtt{Y}
q2q_2 Busca la primera c\mathtt{c}, pasando sobre b\mathtt{b} y Z\mathtt{Z}. La tacha con Z\mathtt{Z}
q3q_3 Vuelve a la izquierda hasta la última X\mathtt{X}
q4q_4, q5q_5 Ya no quedan a\mathtt{a}: comprueba que lo que sigue son solo Y\mathtt{Y} (q4q_4) y después solo Z\mathtt{Z} (q5q_5)
$ build/show_tm machines/anbncn.tm
Q = {q0, q1, q2, q3, q4, q5, q_accept, q_reject}
Σ = {a, b, c}
Γ = {a, b, c, X, Y, Z, _}
q0 = q0, q_accept = q_accept, q_reject = q_reject

δ         a             b             c             X             Y             Z             _
q0        q1 X R        .             .             .             q4 Y R        .             q_accept _ R
q1        q1 a R        q2 Y R        .             .             q1 Y R        .             .
q2        .             q2 b R        q3 Z L        .             .             q2 Z R        .
q3        q3 a L        q3 b L        .             q0 X R        q3 Y L        q3 Z L        .
q4        .             .             .             .             q4 Y R        q5 Z R        .
q5        .             .             .             .             .             q5 Z R        q_accept _ R

transiciones escritas: 18 de 42

El orden de los símbolos lo vigilan las casillas vacías. q1q_1 solo acepta pasar sobre a\mathtt{a} e Y\mathtt{Y} antes de la b\mathtt{b}, y q2q_2 solo sobre b\mathtt{b} y Z\mathtt{Z} antes de la c\mathtt{c}: si la entrada tiene una a\mathtt{a} después de una b\mathtt{b}, la máquina cae en una casilla vacía, en alguna vuelta o en la comprobación final. Las cantidades las vigila el final: cuando q0q_0 ya no encuentra una a\mathtt{a}, q4q_4 y q5q_5 exigen que no quede ninguna b\mathtt{b} ni ninguna c\mathtt{c} sin tachar.

$ build/run_tm machines/anbncn.tm aabbcc
w = aabbcc
    0  q0 aabbcc
    1  X q1 abbcc
    2  Xa q1 bbcc
    3  XaY q2 bcc
    4  XaYb q2 cc
    5  XaY q3 bZc
    6  Xa q3 YbZc
    7  X q3 aYbZc
    8  q3 XaYbZc
    9  X q0 aYbZc
   10  XX q1 YbZc
   11  XXY q1 bZc
   12  XXYY q2 Zc
   13  XXYYZ q2 c
   14  XXYY q3 ZZ
   15  XXY q3 YZZ
   16  XX q3 YYZZ
   17  X q3 XYYZZ
   18  XX q0 YYZZ
   19  XXY q4 YZZ
   20  XXYY q4 ZZ
   21  XXYYZ q5 Z
   22  XXYYZZ q5 _
   23  XXYYZZ_ q_accept _
  acepta en 23 pasos

Dos vueltas, de la 0 a la 9 y de la 9 a la 18, y la comprobación final. Con anbncn\mathtt{a}^n\mathtt{b}^n\mathtt{c}^n la máquina da 4n2+3n+14n^2 + 3n + 1 pasos (para n=2n = 2, los 23 de arriba), y con cualquier entrada de longitud nn, a lo sumo n2+n+2n^2 + n + 2, por el argumento de las vueltas.

Las pruebas de la semana comparan cada una de las tres máquinas con una función de C++ que decide el mismo lenguaje mirando la cadena completa: sobre las 16 383 cadenas binarias de longitud a lo sumo 13 para la primera, y sobre las 29 524 cadenas de longitud a lo sumo 9 de cada alfabeto de tres símbolos para las otras dos. En ninguna se pasa de la cota de pasos.

Idea clave. El lenguaje que separaba a las gramáticas de “lo que una computadora puede hacer” cae con la misma técnica que { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\}: marcar y volver. Lo que el autómata de pila no tenía era la posibilidad de volver sobre lo escrito sin borrarlo.

Reconocer y decidir

Las tres máquinas de la sección anterior se detienen con toda entrada. La de has_one_loops.tm no. Esa diferencia tiene nombre.

Definición. Una máquina de Turing es un decididor (decider) si se detiene con toda entrada: con cada cadena de Σ∗\Sigma^*, acepta o rechaza. Un decididor MM decide el lenguaje L(M)L(M).

Definición. Un lenguaje es reconocible (Turing-recognizable) si alguna máquina de Turing lo reconoce. Es decidible (decidable) si alguna máquina de Turing lo decide.

Dicho con las tres maneras de terminar:

Con w∈Lw \in L Con w∉Lw \notin L
MM reconoce LL acepta rechaza o no se detiene
MM decide LL acepta rechaza

Una máquina que decide LL da siempre una respuesta. Una que solo lo reconoce da el sí cuando corresponde, y cuando la respuesta es no puede quedarse callada para siempre. Quien la usa y lleva una hora esperando no sabe si la respuesta es no o si todavía no llegó el sí.

Todo decididor reconoce su lenguaje, así que todo lenguaje decidible es reconocible. La pregunta interesante es la otra dirección, y es el tema de la semana 9: hay lenguajes reconocibles que no son decidibles, y hay lenguajes que ni siquiera son reconocibles. En otros libros los lenguajes decidibles se llaman recursivos y los reconocibles, recursivamente enumerables; el segundo nombre se explica más abajo, con los enumeradores.

Ahora, con cuidado. La máquina has_one_loops.tm reconoce el lenguaje A={ w∈{0,1}∗:w tiene alguˊn 1 }A = \{\, w \in \{\mathtt{0}, \mathtt{1}\}^* : w \text{ tiene algún } \mathtt{1} \,\} y no lo decide, porque no se detiene con 00\mathtt{00}. ¿Es AA indecidible? No. Basta cambiarle una transición para que al llegar al primer blanco rechace. Esa máquina es machines/has_one.tm:

$ build/run_tm --quiet machines/has_one.tm 000 0010
w = 000
  rechaza en 4 pasos
w = 0010
  acepta en 3 pasos

Las dos máquinas reconocen el mismo lenguaje. Una lo decide y la otra no. Y AA es decidible, porque para eso basta que exista un decididor.

Una tabla y un diagrama de conjuntos sobre el lenguaje A de las cadenas que tienen algún 1. La tabla tiene una fila por máquina y una columna por entrada. La máquina has_one_loops.tm, con 001, que está en A, acepta en 3 pasos; con 00, que no está en A, no se detiene: sigue sobre los blancos. Esa máquina reconoce A y no lo decide. La máquina has_one.tm, con 001, acepta en 3 pasos, y con 00 rechaza en 3 pasos: decide A. A la derecha, un recuadro con el rótulo Reconocibles contiene otro con el rótulo Decidibles; dentro de los decidibles están A, al que apunta una flecha desde la fila de has_one.tm, y los lenguajes 0ⁿ1ⁿ, aⁿbⁿcⁿ y w#w. En la franja de los reconocibles que queda fuera de los decidibles hay una pregunta: si queda algo ahí se verá en la semana 9. Al pie: reconocer A es aceptar exactamente las cadenas de A; decidirlo es, además, detenerse con toda entrada. A es decidible porque existe un decididor, aunque otra máquina que lo reconoce no se detenga con 00.Una tabla y un diagrama de conjuntos sobre el lenguaje A de las cadenas que tienen algún 1. La tabla tiene una fila por máquina y una columna por entrada. La máquina has_one_loops.tm, con 001, que está en A, acepta en 3 pasos; con 00, que no está en A, no se detiene: sigue sobre los blancos. Esa máquina reconoce A y no lo decide. La máquina has_one.tm, con 001, acepta en 3 pasos, y con 00 rechaza en 3 pasos: decide A. A la derecha, un recuadro con el rótulo Reconocibles contiene otro con el rótulo Decidibles; dentro de los decidibles están A, al que apunta una flecha desde la fila de has_one.tm, y los lenguajes 0ⁿ1ⁿ, aⁿbⁿcⁿ y w#w. En la franja de los reconocibles que queda fuera de los decidibles hay una pregunta: si queda algo ahí se verá en la semana 9. Al pie: reconocer A es aceptar exactamente las cadenas de A; decidirlo es, además, detenerse con toda entrada. A es decidible porque existe un decididor, aunque otra máquina que lo reconoce no se detenga con 00.
Reconocer y decidir son afirmaciones sobre una máquina; reconocible y decidible, sobre un lenguaje. Basta un decididor para que el lenguaje sea decidible.

Error común. Decir que una máquina “decide” un lenguaje cuando hay entradas con las que no se detiene. Decidir es una afirmación sobre todas las entradas: con cada una, la máquina se detiene. Si con una sola cadena no se detiene, la máquina reconoce su lenguaje y no lo decide. Y al revés: que una máquina concreta no decida LL no dice que LL sea indecidible. Decidible es una propiedad del lenguaje, y para negarla hay que demostrar que ninguna máquina lo decide.

Para afirmar que una máquina decide hay que demostrar dos cosas, y la segunda es nueva: que acepta exactamente las cadenas del lenguaje, y que se detiene con toda entrada. En la máquina de { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\} fue la tercera parte de la demostración, con la cota de n2+n+2n^2 + n + 2 pasos. Una cota de pasos en función de la longitud de la entrada es la manera más directa de demostrar que una máquina se detiene.

Dos consecuencias inmediatas de las definiciones, que usaremos después.

Todo lenguaje regular es decidible. Sea B=(Q,Σ,δB,q0,F)B = (Q, \Sigma, \delta_B, q_0, F) un DFA. La máquina de Turing que lo imita tiene los estados de BB más qacceptq_{\text{accept}} y qrejectq_{\text{reject}}, nunca cambia la cinta y solo se mueve a la derecha: δ(q,a)=(δB(q,a),a,R)\delta(q, a) = (\delta_B(q, a), a, \mathrm{R}) para cada símbolo aa de Σ\Sigma. Al leer el primer blanco ya leyó toda la entrada, y pasa a qacceptq_{\text{accept}} si q∈Fq \in F y a qrejectq_{\text{reject}} si no. Con una entrada de longitud nn se detiene en n+1n + 1 pasos, y acepta exactamente cuando BB acepta. has_one.tm es una máquina de este tipo, que además se adelanta y acepta apenas ve el uno.

Los lenguajes decidibles son cerrados bajo complemento. Si MM decide LL, la máquina que resulta de intercambiar qacceptq_{\text{accept}} y qrejectq_{\text{reject}} decide el complemento de LL: se detiene con las mismas entradas, que son todas, y responde lo contrario. Con una máquina que solo reconoce, el mismo cambio no sirve: las entradas con las que MM no se detiene siguen sin respuesta, y deberían ser aceptadas. Es el mismo fenómeno que el complemento de un DFA sin estado trampa, en la semana 1: para dar vuelta las respuestas, la máquina tiene que responder siempre. En la semana 9 veremos que no es un defecto de la construcción: los lenguajes reconocibles no son cerrados bajo complemento, y que si un lenguaje y su complemento son los dos reconocibles, entonces es decidible.

Los tres niveles de descripción

Escribir la tabla de una máquina de Turing es lento, y leerla es peor. Para la máquina de { w#w }\{\, w\mathtt{\#}w \,\} hicieron falta 20 transiciones, y la idea se dice en una frase. Por eso una máquina se describe en uno de tres niveles, según para qué se la quiera, y el texto siempre dice cuál usa. Los tres, para esa misma máquina.

Nivel formal. La séptupla completa: los estados, los alfabetos y la tabla de δ\delta, o el archivo .tm. Es la salida de show_tm machines/w_sep_w.tm de la sección anterior. No deja nada a la interpretación: se puede ejecutar a mano o darle el archivo a un simulador. Es el nivel de esta semana y el del laboratorio.

Nivel de implementación. Se dice en prosa qué hace el cabezal: por dónde se mueve, qué marca, qué recuerda en el estado. No se nombran los estados ni se escribe δ\delta.

M = "Con la entrada w:
  1. Si la celda bajo el cabezal tiene el separador, ir al paso 5. Si tiene un blanco, rechazar.
     Si no, recordar su símbolo y tacharlo.
  2. Avanzar hasta el separador. Si antes aparece un blanco, rechazar.
  3. Avanzar sobre los símbolos tachados hasta el primero sin tachar. Si es igual al símbolo
     recordado, tacharlo. Si no, rechazar.
  4. Retroceder hasta el símbolo tachado que está más a la derecha entre los que quedan a la
     izquierda del separador, avanzar una celda y volver al paso 1.
  5. Avanzar sobre los símbolos tachados que siguen al separador. Si después de ellos viene
     un blanco, aceptar. Si no, rechazar."

Quien lea esto puede escribir la tabla sin tener que inventar nada, y puede contar los pasos. Es el nivel adecuado para convencerse de que algo cabe en una máquina de Turing: de que se puede hacer solo con un cabezal, marcas y una cantidad fija de estados.

Nivel alto. Un algoritmo en pasos numerados, sin mencionar la cinta ni el cabezal.

M = "Con la entrada w:
  1. Comprobar que w tiene exactamente un separador. Si no, rechazar.
  2. Comparar la parte de w que está antes del separador con la que está después.
     Si son iguales, aceptar. Si no, rechazar."

Es como se escribe un algoritmo en cualquier curso. Lo que una descripción de alto nivel tiene que cumplir es que cada paso sea claramente realizable por una máquina, con una cantidad finita de trabajo, y que quede claro cuándo acepta y cuándo rechaza. Si se afirma que la máquina decide, además tiene que verse que termina.

Nivel Qué se escribe Para qué sirve
Formal La séptupla: la tabla de δ\delta o el archivo Ejecutarla, programarla, demostrar algo sobre una máquina concreta
De implementación Los movimientos del cabezal y las marcas, en prosa Mostrar que una idea cabe en el modelo; contar pasos
Alto Un algoritmo en pasos numerados Todo lo demás, desde la semana 9

¿Con qué derecho se pasa del primer nivel al tercero? Cada vez que escribamos “comparar las dos partes” sin decir cómo, estaremos afirmando que existe una tabla que lo hace. Para los pasos de esta semana, esa tabla está a la vista. En general, lo que justifica el salto es la segunda mitad de este capítulo: el modelo aguanta cualquier comodidad que se le agregue, y todo lo que se sabe calcular con un procedimiento mecánico se puede calcular con una máquina de Turing. Después de esta semana casi no volveremos a escribir una tabla.

En la práctica. Los tres niveles son los de cualquier software. El nivel formal es el código de máquina: lo único que de verdad se ejecuta, y casi nadie lo lee. El de implementación es el código fuente, con sus punteros y sus ciclos. El alto es el pseudocódigo de un libro de algoritmos, o la descripción de una función en su documentación. Se confía en el nivel alto porque se sabe que hay un compilador que lo baja hasta el primero.

El modelo es robusto

La definición de la sesión anterior tiene decisiones que parecen arbitrarias. ¿Por qué una sola cinta? ¿Por qué infinita solo hacia la derecha? ¿Por qué el cabezal no puede quedarse quieto? Si alguna de esas decisiones cambiara lo que la máquina puede calcular, el modelo sería frágil, y sería difícil sostener que captura algo tan general como “lo calculable”.

No lo cambian. Un modelo es robusto cuando sus variantes razonables reconocen exactamente los mismos lenguajes, y la máquina de Turing lo es en un grado que ningún modelo anterior tenía.

La manera de demostrarlo es siempre la misma, y conviene tenerla clara antes de ver los casos.

Idea clave. Para mostrar que dos modelos tienen el mismo poder, se muestra que cada uno puede simular al otro: dada una máquina cualquiera de un modelo, se construye una del otro que reconoce el mismo lenguaje. Una dirección suele ser trivial, porque un modelo es un caso particular del otro. El trabajo está en la otra.

Un calentamiento. Supongan que se permite un tercer movimiento, S\mathrm{S}, que deja el cabezal donde está. Toda máquina sin S\mathrm{S} es también una máquina con S\mathrm{S} que no lo usa: esa dirección no pide nada. Al revés, dada una máquina que usa S\mathrm{S}, cada transición δ(q,a)=(r,b,S)\delta(q, a) = (r, b, \mathrm{S}) se cambia por dos: una que escribe bb, va a la derecha y pasa a un estado nuevo r′r', y otra que desde r′r', lea lo que lea, lo deja igual, va a la izquierda y pasa a rr. Después de un paso a la derecha el cabezal nunca está en la primera celda, así que el paso a la izquierda lo devuelve a donde estaba. La máquina nueva reconoce el mismo lenguaje, con el doble de pasos como mucho. Quedarse quieto es una comodidad y no agrega poder.

Las tres variantes que siguen son menos triviales, y cada una enseña una técnica que volverá: más cintas, no determinismo, y una máquina que en lugar de responder imprime.

Máquinas de varias cintas

Una máquina de Turing de kk cintas (multitape Turing machine) tiene kk cintas, cada una con su propio cabezal. Al empezar, la entrada está en la primera cinta y las demás están en blanco. En cada paso la máquina lee los kk símbolos que están bajo los cabezales, y con eso y el estado decide qué escribir en cada cinta y cómo mover cada cabezal:

δ:Q′×Γk→Q×Γk×{L,R,S}k\delta : Q' \times \Gamma^k \to Q \times \Gamma^k \times \{\mathrm{L}, \mathrm{R}, \mathrm{S}\}^k

Con varias cintas es natural permitir S\mathrm{S}: a menudo un cabezal espera mientras otro trabaja.

Con dos cintas, { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\} se decide sin ir y venir. La máquina copia los ceros a la segunda cinta, y después retrocede en ella un cero por cada uno que lee en la primera.

Estado Lee (cinta 1, cinta 2) Escribe Mueve Pasa a Para qué
q0q_0 ⊔\sqcup, ⊔\sqcup ⊔\sqcup, ⊔\sqcup S, S qacceptq_{\text{accept}} La entrada vacía
q0q_0 0\mathtt{0}, ⊔\sqcup 0\mathtt{0}, $ S, R q1q_1 Marca el inicio de la cinta 2
q1q_1 0\mathtt{0}, ⊔\sqcup 0\mathtt{0}, 0\mathtt{0} R, R q1q_1 Copia un cero
q1q_1 1\mathtt{1}, ⊔\sqcup 1\mathtt{1}, ⊔\sqcup S, L q2q_2 Primer uno: la cinta 2 vuelve al último cero
q2q_2 1\mathtt{1}, 0\mathtt{0} 1\mathtt{1}, 0\mathtt{0} R, L q2q_2 Un uno por cada cero
q2q_2 ⊔\sqcup, $ ⊔\sqcup, $ S, S qacceptq_{\text{accept}} Se acabaron a la vez

Cualquier otra combinación lleva a qrejectq_{\text{reject}}. La marca $ en la primera celda de la segunda cinta es la manera de saber dónde empieza, como dijimos al hablar del borde izquierdo. El formato .tm del curso describe máquinas de una cinta, así que esta máquina está escrita en C++, en la función two_tape_zeros_ones de multitape.h. En la salida, el símbolo bajo cada cabezal va entre corchetes:

$ build/multitape_demo run 0011
w = 0011
  0  q0   cinta 1: [0]011   cinta 2: [_]
  1  q1   cinta 1: [0]011   cinta 2: $[_]
  2  q1   cinta 1: 0[0]11   cinta 2: $0[_]
  3  q1   cinta 1: 00[1]1   cinta 2: $00[_]
  4  q2   cinta 1: 00[1]1   cinta 2: $0[0]
  5  q2   cinta 1: 001[1]   cinta 2: $[0]0
  6  q2   cinta 1: 0011[_]   cinta 2: [$]00
  7  q_accept   cinta 1: 0011[_]   cinta 2: [$]00
  acepta en 7 pasos

Con 0n1n\mathtt{0}^n\mathtt{1}^n y n≥1n \geq 1 son 2n+32n + 3 pasos: uno para la marca, nn para copiar, uno para dar la vuelta, nn para comparar y uno para aceptar. La máquina de una cinta necesitaba 2n2+2n+12n^2 + 2n + 1. Dos cintas son, claramente, más cómodas y más rápidas. Lo que afirma el teorema siguiente es que no son más poderosas.

Teorema. Para toda máquina de Turing de varias cintas hay una máquina de Turing de una cinta que reconoce el mismo lenguaje.

Demostración. Por construcción. Sea MM una máquina de kk cintas. Construimos una máquina SS de una cinta que simula a MM paso a paso, y después mostramos que reconoce el mismo lenguaje.

Qué se construye: la cinta de SS. SS guarda en su única cinta el contenido de las kk cintas de MM, una después de otra, con un separador #\mathtt{\#} antes de la primera, entre cada dos y después de la última. De cada cinta de MM guarda solo un tramo inicial: las celdas que MM ya usó. Para saber dónde está cada cabezal de MM, el símbolo que está bajo él lleva una marca. Formalmente, el alfabeto de la cinta de SS tiene, por cada símbolo aa de Γ\Gamma, dos símbolos: aa y aa con marca. Aquí la marca se escribe con corchetes. Si las cintas de MM son las de la configuración 2 del ejemplo, la cinta de SS es

#0[0]11#$0[_]#

Cada tramo tiene exactamente una marca.

Qué se construye: cómo trabaja SS.

S = "Con la entrada w = w1 w2 … wn:
  1. Preparar la cinta: correr w una celda a la derecha y dejar  #[w1]w2…wn#[_]#[_]#…#,
     con k tramos. Volver a la primera celda.
  2. Para simular un paso de M:
     a. Recorrer la cinta de la primera celda al último separador, anotando el símbolo
        marcado de cada tramo. Volver a la primera celda.
     b. Con el estado de M y los k símbolos anotados, buscar en δ lo que M hace: los k
        símbolos que escribe, los k movimientos y el estado nuevo. Si δ no tiene esa
        transición, rechazar.
     c. Recorrer la cinta otra vez. En cada tramo, cambiar el símbolo marcado por el que
        M escribe ahí y mover la marca una celda según el movimiento de ese cabezal.
        Si la marca tendría que pasar a la izquierda del separador que abre el tramo, se
        queda donde está: el cabezal de M estaba en su primera celda.
        Si la marca tendría que caer sobre el separador que cierra el tramo, el cabezal
        de M llega a una celda que el tramo todavía no tiene: escribir ahí un blanco con
        marca y correr todo lo que sigue, hasta el último separador, una celda a la
        derecha.
     d. Volver a la primera celda. Si el estado nuevo de M es q_accept, aceptar. Si es
        q_reject, rechazar. Si no, repetir desde 2."

Esta es una descripción de implementación, y lo que hay que revisar es que cabe en una máquina de una cinta con una cantidad fija de estados. Lo que SS recuerda fuera de la cinta es: el estado de MM, los kk símbolos anotados, lo que δ\delta dice que hay que hacer con cada tramo, el símbolo que lleva en la mano mientras corre la cinta, y cuántos separadores ha pasado. Cada uno de esos datos tiene una cantidad finita de valores posibles, que depende de MM y no de la entrada. Todas las combinaciones son una cantidad finita, y cada una es un estado de SS. Contar separadores le sirve a SS para saber en qué tramo está y para reconocer el primero y el último, que son el número 1 y el número k+1k + 1.

Por qué reconoce el mismo lenguaje. Se demuestra por inducción sobre tt que, después de simular tt pasos, la cinta de SS representa la configuración de MM después de tt pasos: el tramo ii tiene el contenido de la cinta ii de MM, salvo blancos al final, la marca del tramo ii está en la posición del cabezal ii, y SS recuerda el estado de MM. Para t=0t = 0 es lo que deja el paso 1. Si vale para tt, en el paso 2a SS anota exactamente los símbolos que MM lee, en 2b obtiene la misma acción que MM, y en 2c aplica a cada tramo el cambio que MM aplica a cada cinta, incluidos los dos casos del borde: vale para t+1t + 1. Entonces SS llega a aceptar si y solo si MM llega a qacceptq_{\text{accept}}, y lo mismo con rechazar. Si MM no se detiene, SS tampoco. Luego L(S)=L(M)L(S) = L(M), y SS es un decididor exactamente cuando MM lo es. ∎

El programa multitape_demo sim ejecuta esa simulación. La cinta de SS se toca solo como la tocaría un cabezal, con una operación que lee la celda actual, escribe en ella y se mueve una celda, y cada operación se cuenta como un paso de SS:

$ build/multitape_demo sim 01
w = 01
pasos de M   estado de M   cinta de S              pasos de S
         0   q0            #[0]1#[_]#                      12
         1   q1            #[0]1#$[_]#                     36
         2   q1            #0[1]#$0[_]#                    64
         3   q2            #0[1]#$[0]_#                    94
         4   q2            #01[_]#[$]0_#                  136
         5   q_accept      #01[_]#[$]0_#                  168
  acepta: 5 pasos de M, 168 pasos de S (12 para preparar la cinta)

En la primera fila la cinta está recién preparada. De la fila 0 a la 1, el segundo cabezal de MM escribe $ y va a la derecha, a una celda que su tramo no tenía: el tramo crece y el último separador se corre. De la 3 a la 4 crece el primer tramo, y se corre todo el segundo. Simular 5 pasos de MM costó 168 pasos de SS.

Animación de la simulación de la máquina de dos cintas con la entrada 01. Arriba está M, con su estado, sus dos cintas y un cabezal sobre cada una, y un contador de sus pasos. Abajo está S, con una sola cinta, su cabezal y un contador de sus pasos; en la cinta de S los separadores # delimitan dos tramos, uno por cinta de M, y la celda que tiene marca, con un punto y un contorno dorado, es la que está bajo el cabezal de M. Entre un cuadro y el siguiente el cabezal de S recorre toda su cinta dos veces: en el primer recorrido lee los símbolos marcados y en el segundo escribe y mueve las marcas. Al empezar, M está en q₀ con 01 en la cinta 1 y la cinta 2 en blanco, y S ya preparó su cinta en 12 pasos: #, 0 con marca, 1, #, un blanco con marca, #. Paso 1 de M: escribe la marca de inicio, un signo de dólar, en la cinta 2 y mueve ese cabezal a la derecha; en S el tramo 2 crece una celda y el último # se corre, y van 36 pasos. Paso 2: M copia el 0 en la cinta 2 y avanzan los dos cabezales; en S se mueven las dos marcas y el tramo 2 vuelve a crecer; 64 pasos. Paso 3: M ve el primer 1 y el cabezal de la cinta 2 retrocede hasta el 0; en S la marca del tramo 2 retrocede y el blanco que quedó atrás sigue en el tramo; 94 pasos. Paso 4: M empareja el 1 con el 0, el cabezal 1 llega a una celda nueva y el cabezal 2 retrocede hasta la marca de inicio; en S crece el tramo 1 y todo el tramo 2 se corre una celda a la derecha; 136 pasos. Paso 5: M lee un blanco y la marca de inicio, y acepta; S recorre su cinta, encuentra que M pasa a q_accept y acepta. Los 5 pasos de M costaron 168 pasos de S.Animación de la simulación de la máquina de dos cintas con la entrada 01. Arriba está M, con su estado, sus dos cintas y un cabezal sobre cada una, y un contador de sus pasos. Abajo está S, con una sola cinta, su cabezal y un contador de sus pasos; en la cinta de S los separadores # delimitan dos tramos, uno por cinta de M, y la celda que tiene marca, con un punto y un contorno dorado, es la que está bajo el cabezal de M. Entre un cuadro y el siguiente el cabezal de S recorre toda su cinta dos veces: en el primer recorrido lee los símbolos marcados y en el segundo escribe y mueve las marcas. Al empezar, M está en q₀ con 01 en la cinta 1 y la cinta 2 en blanco, y S ya preparó su cinta en 12 pasos: #, 0 con marca, 1, #, un blanco con marca, #. Paso 1 de M: escribe la marca de inicio, un signo de dólar, en la cinta 2 y mueve ese cabezal a la derecha; en S el tramo 2 crece una celda y el último # se corre, y van 36 pasos. Paso 2: M copia el 0 en la cinta 2 y avanzan los dos cabezales; en S se mueven las dos marcas y el tramo 2 vuelve a crecer; 64 pasos. Paso 3: M ve el primer 1 y el cabezal de la cinta 2 retrocede hasta el 0; en S la marca del tramo 2 retrocede y el blanco que quedó atrás sigue en el tramo; 94 pasos. Paso 4: M empareja el 1 con el 0, el cabezal 1 llega a una celda nueva y el cabezal 2 retrocede hasta la marca de inicio; en S crece el tramo 1 y todo el tramo 2 se corre una celda a la derecha; 136 pasos. Paso 5: M lee un blanco y la marca de inicio, y acepta; S recorre su cinta, encuentra que M pasa a q_accept y acepta. Los 5 pasos de M costaron 168 pasos de S.
Cada tramo de la cinta de S es una cinta de M, y la marca es su cabezal. Simular un solo paso de M obliga a S a recorrer toda su cinta: de ahí sale el costo cuadrático.

Hay que ser precisos sobre qué es este programa. No construye la tabla de δ\delta de SS: es la descripción de implementación de arriba escrita en C++, con la disciplina de tocar la cinta solo a través del cabezal. Las pruebas comprueban la afirmación de la inducción después de cada paso, comparando la cinta de SS con la configuración de MM, para la máquina de dos cintas con las 4095 cadenas binarias de longitud a lo sumo 11 y para 180 máquinas de una, dos y tres cintas con transiciones al azar.

Cuánto cuesta la simulación

Esta semana solo importa que la simulación existe. En la semana 12 va a importar cuánto cuesta, así que dejamos hecha la cuenta.

Teorema. Sea MM una máquina de kk cintas que con la entrada ww, de longitud nn, se detiene en tt pasos. Entonces la máquina SS de la construcción se detiene con ww en a lo sumo

2(n+2k+1)+t⋅(2k+6)⋅(n+2k+1+kt)2(n + 2k + 1) + t \cdot (2k + 6) \cdot (n + 2k + 1 + kt)

pasos. En particular, si t≥nt \geq n, son O(t2)O(t^2) pasos, con una constante que depende solo de kk.

Demostración. Se cuenta por partes. Llamemos ℓ\ell a la cantidad de celdas que SS tiene en uso, de la primera al último separador.

El largo de la cinta. Recién preparada, la cinta tiene n+2kn + 2k celdas en uso si n≥1n \geq 1: un separador, los nn símbolos de la entrada, otro separador, y un blanco con marca y un separador por cada una de las otras k−1k - 1 cintas. Si n=0n = 0 tiene 2k+12k + 1. En los dos casos, a lo sumo n+2k+1n + 2k + 1. Al simular un paso de MM, cada tramo crece a lo sumo una celda, porque cada cabezal de MM avanza a lo sumo una. Entonces, después de simular tt pasos,

ℓ≤n+2k+1+kt.\ell \leq n + 2k + 1 + kt.

Preparar la cinta. SS escribe las celdas de izquierda a derecha, una por paso, y vuelve a la primera: a lo sumo 2(n+2k+1)2(n + 2k + 1) pasos.

Simular un paso de MM. Sea ℓ\ell el largo de la cinta al terminar de simularlo.

Parte Pasos de SS, a lo sumo
2a: ir hasta el último separador y volver 2ℓ2\ell
2c: avanzar de la primera celda al último separador ℓ\ell
2c: en cada tramo, mover la marca una celda a la izquierda y regresar 22 por tramo: 2k2k
2c: en cada tramo que crece, correr el resto de la cinta y regresar 2ℓ2\ell por tramo: 2kℓ2k\ell
2d: volver a la primera celda ℓ\ell

La suma es (2k+4)ℓ+2k(2k + 4)\ell + 2k, y como ℓ≥k\ell \geq k, es a lo sumo (2k+6)ℓ(2k + 6)\ell.

El total. Durante toda la simulación ℓ≤n+2k+1+kt\ell \leq n + 2k + 1 + kt, y se simulan tt pasos. Sumando la preparación sale la cota del enunciado. Si t≥nt \geq n, el factor n+2k+1+ktn + 2k + 1 + kt es a lo sumo (k+1)t+2k+1(k + 1)t + 2k + 1, y la cota es un polinomio de grado 2 en tt cuyos coeficientes dependen solo de kk. ∎

La razón del cuadrado está en la tabla: simular un paso de MM obliga a SS a recorrer toda su cinta, y esa cinta puede medir tanto como pasos lleva MM. Son tt pasos, cada uno de costo proporcional a tt.

multitape_demo table mide las tres maneras de decidir { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\} que tenemos, con la entrada 0n1n\mathtt{0}^n\mathtt{1}^n:

$ build/multitape_demo table
Entrada 0^n 1^n, de longitud 2n. Pasos hasta aceptar:

    n   una cinta (zeros_ones.tm)   dos cintas   dos cintas simuladas en una
    5                  61                   13                  992
   10                 221                   23                 3012
   20                 841                   43                10352
   40                3281                   83                38232
   80               12961                  163               146792
  160               51521                  323               575112
  320              205441                  643              2276552

La columna de dos cintas es 2n+32n + 3: al duplicar nn, se duplica. La última columna se multiplica por un número cada vez más cercano a 4 cuando nn se duplica (575 112/146 792≈3,92575\,112 / 146\,792 \approx 3{,}92 y 2 276 552/575 112≈3,962\,276\,552 / 575\,112 \approx 3{,}96), que es lo que hace una función cuadrática. La primera columna también es cuadrática, con una constante unas once veces menor: una máquina pensada para una cinta le gana a la simulación genérica, pero las dos están en el mismo orden. Son cantidades de pasos, exactas, y no tiempos: no dependen de la computadora donde se corra el programa.

Idea clave. Varias cintas no agregan poder: una cinta las simula guardándolas una después de otra, con una marca en el lugar de cada cabezal. Sí agregan velocidad, pero poca: lo que una máquina de varias cintas hace en tt pasos, una de una cinta lo hace en O(t2)O(t^2).

En C++. En multitape.h, la cinta de SS es un struct OneTape con una sola operación que la modifica, write_move(c, direction), que escribe en la celda del cabezal, lo mueve una celda y suma uno a steps. El resto de la simulación está escrito encima de esa operación, sin índices: para llegar a una celda hay que caminar hasta ella. Así el contador de pasos es el de una máquina de Turing de verdad.

Máquinas no deterministas

La segunda variante cambia la función de transición. En una máquina de Turing no determinista (nondeterministic Turing machine), δ(q,a)\delta(q, a) no es una acción sino un conjunto de acciones posibles:

δ:Q′×Γ→P(Q×Γ×{L,R})\delta : Q' \times \Gamma \to \mathcal{P}(Q \times \Gamma \times \{\mathrm{L}, \mathrm{R}\})

Es el mismo cambio que llevó del DFA al NFA en la semana 2. Desde una configuración puede haber varias configuraciones siguientes, una por cada acción. Las ejecuciones posibles con una entrada ww ya no forman una secuencia sino un árbol: la raíz es la configuración inicial, y los hijos de cada configuración son las que produce en un paso. Cada camino que baja desde la raíz es una rama: una ejecución posible.

Definición. Una máquina no determinista NN acepta ww si alguna rama del árbol llega a una configuración de aceptación. No importa cuántas ramas rechacen, ni cuántas no se detengan.

En el formato del curso, una máquina no determinista se escribe igual que una determinista, con varias líneas para el mismo par. Esta es machines/nondet_branch.tm, hecha para que una de sus opciones sea una trampa:

# No determinista: con un 0 en q0 hay dos opciones. La primera se va por una rama que no se
# detiene nunca; la segunda sigue buscando un 1. Acepta las cadenas que tienen algún 1.
states: q0 q1 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q1 0 R
q0 0 -> q0 0 R
q0 1 -> q_accept 1 R
q1 0 -> q1 0 R
q1 1 -> q1 1 R
q1 _ -> q1 _ R

En q0q_0, con un 0\mathtt{0}, la máquina puede pasar a q1q_1 o seguir en q0q_0. El estado q1q_1 avanza hacia la derecha para siempre, lea lo que lea. El programa ntm_demo imprime el árbol nivel por nivel: en el nivel dd están las configuraciones a las que se llega con dd pasos.

$ build/ntm_demo machines/nondet_branch.tm 001
w = 001
nivel 0:   q0 001
nivel 1:   0 q1 01   0 q0 01
nivel 2:   00 q1 1   00 q1 1   00 q0 1
nivel 3:   001 q1 _   001 q1 _   001 q_accept _
por niveles: acepta en el nivel 3, después de revisar 9 configuraciones
siempre la primera opción: no se detuvo en 1000000 pasos

En el nivel 2 la configuración 00 q1 1\mathtt{00}\,q_1\,\mathtt{1} aparece dos veces: se llega a ella por dos ramas distintas, y el árbol las cuenta por separado. En el nivel 3 una rama acepta, y con eso la máquina acepta 001\mathtt{001}, aunque las otras dos ramas sigan sin fin.

Un NFA no ganaba poder con el no determinismo: la construcción de subconjuntos lo volvía determinista. Un autómata de pila sí ganaba, como vimos la semana pasada con los palíndromos. Con las máquinas de Turing se vuelve al primer caso.

Teorema. Para toda máquina de Turing no determinista hay una máquina de Turing determinista que reconoce el mismo lenguaje.

La idea, y el intento que falla. La máquina determinista DD tiene que buscar en el árbol de NN una configuración de aceptación. Hay dos maneras conocidas de recorrer un árbol. La primera que se le ocurre a cualquiera que haya programado un backtracking es el recorrido en profundidad: seguir una rama hasta el final, y si no acepta, volver atrás y probar la siguiente. Con un árbol finito funciona. Aquí no, porque una rama puede no tener final. En el ejemplo, la primera opción en q0q_0 lleva a q1q_1, y esa rama no termina nunca: el recorrido en profundidad entra en ella y no vuelve, aunque la aceptación estaba a tres pasos de la raíz por otra rama. Es la última línea de la salida de arriba. Cambiar el orden de las opciones no lo arregla: para cualquier orden fijo hay una máquina cuya rama infinita está primero.

El recorrido que sirve es por niveles (breadth-first): primero todas las configuraciones a un paso de la raíz, después todas las que están a dos, y así. Una rama infinita ya no estorba, porque el recorrido avanza un paso en todas las ramas antes de dar el segundo en ninguna.

El árbol de ejecuciones de nondet_branch.tm con la entrada 001, dibujado por niveles, con cada configuración numerada en el orden del recorrido por niveles. Nivel 0: la raíz, q₀ 001, con el número 1. Nivel 1: sus dos hijos, 0 q₁ 01 por la primera opción, con el número 2, y 0 q₀ 01 por la segunda, con el 3. Nivel 2: 00 q₁ 1, hijo único de la número 2, con el número 4; y los dos hijos de la número 3, 00 q₁ 1 por la primera opción, con el 5, y 00 q₀ 1 por la segunda, con el 6. Nivel 3: 001 q₁ y un blanco, con el 7; otra vez 001 q₁ y un blanco, con el 8; y 001 q_accept, con el 9, resaltada como de aceptación. Debajo de las dos configuraciones con q₁ hay puntos suspensivos: q₁ avanza para siempre. Las flechas de la rama de la izquierda, la que sigue siempre la primera opción, están resaltadas. La leyenda dice: en profundidad se sigue siempre la primera opción, se entra en la rama de q₁ y no se vuelve nunca; por niveles, los números son el orden en que D revisa las configuraciones, y la novena es de aceptación. La configuración 00 q₁ 1 aparece dos veces, porque se llega a ella por dos ramas y el árbol las cuenta por separado.El árbol de ejecuciones de nondet_branch.tm con la entrada 001, dibujado por niveles, con cada configuración numerada en el orden del recorrido por niveles. Nivel 0: la raíz, q₀ 001, con el número 1. Nivel 1: sus dos hijos, 0 q₁ 01 por la primera opción, con el número 2, y 0 q₀ 01 por la segunda, con el 3. Nivel 2: 00 q₁ 1, hijo único de la número 2, con el número 4; y los dos hijos de la número 3, 00 q₁ 1 por la primera opción, con el 5, y 00 q₀ 1 por la segunda, con el 6. Nivel 3: 001 q₁ y un blanco, con el 7; otra vez 001 q₁ y un blanco, con el 8; y 001 q_accept, con el 9, resaltada como de aceptación. Debajo de las dos configuraciones con q₁ hay puntos suspensivos: q₁ avanza para siempre. Las flechas de la rama de la izquierda, la que sigue siempre la primera opción, están resaltadas. La leyenda dice: en profundidad se sigue siempre la primera opción, se entra en la rama de q₁ y no se vuelve nunca; por niveles, los números son el orden en que D revisa las configuraciones, y la novena es de aceptación. La configuración 00 q₁ 1 aparece dos veces, porque se llega a ella por dos ramas y el árbol las cuenta por separado.
Los dos recorridos sobre el árbol de 001. En profundidad, la rama de la izquierda no termina y la aceptación no se alcanza nunca. Por niveles, es la novena configuración que se revisa.

Demostración. Por construcción.

Qué se construye. DD guarda una cola de configuraciones de NN.

D = "Con la entrada w:
  1. Poner en la cola la configuración inicial de N con w.
  2. Mientras la cola no esté vacía:
     a. Sacar la configuración C que está al frente de la cola.
     b. Si C es de aceptación, aceptar.
     c. Por cada acción de δ que N puede aplicar en C, agregar al final de la cola la
        configuración que resulta. (Si C es de rechazo, no se agrega nada.)
  3. Rechazar."

DD es una máquina de Turing: se puede armar con varias cintas, que ya sabemos reducir a una. Una configuración de NN es una cadena finita, u q vu\,q\,v. La cola es una cinta con las configuraciones escritas una después de otra y separadas por #\mathtt{\#}, y una marca en la que está al frente. Sacar del frente es avanzar la marca. Agregar al final es copiar CC al final de la cinta, cambiando solo lo que cambia en un paso: el estado, un símbolo y la posición del estado. Las acciones posibles en CC son una cantidad finita, y están en la tabla de NN, que DD lleva en sus estados.

Por qué reconoce el mismo lenguaje: si DD acepta ww, NN acepta ww. Toda configuración que entra a la cola es la inicial o se produjo en un paso de NN a partir de una que estaba en la cola. Por inducción, toda configuración de la cola está en el árbol de NN con ww. Si DD acepta, sacó de la cola una configuración de aceptación, que es entonces el final de una rama de NN.

Si NN acepta ww, DD acepta ww. Sea bb la mayor cantidad de acciones que tiene una casilla de la tabla de NN. Es un número finito, y cada configuración tiene a lo sumo bb hijos, así que el nivel dd del árbol tiene a lo sumo bdb^d configuraciones. La cola respeta los niveles: las configuraciones salen en el orden en que entraron, y los hijos de una configuración del nivel dd entran después de todas las del nivel dd. Por inducción, DD saca todas las del nivel dd antes que cualquiera del nivel d+1d + 1. Si NN acepta ww, hay una configuración de aceptación en algún nivel dd. Antes de llegar a ella, DD procesa a lo sumo

1+b+b2+⋯+bd1 + b + b^2 + \cdots + b^d

configuraciones, que es una cantidad finita, y procesar cada una toma una cantidad finita de pasos. Entonces DD llega a esa configuración, o a otra de aceptación que estaba antes en la cola, y acepta. ∎

Hay un detalle en el paso 3 que vale la pena. Si todas las ramas de NN se detienen, el árbol es finito: un árbol en el que cada nodo tiene una cantidad finita de hijos y ninguna rama es infinita tiene una cantidad finita de nodos (es el lema de König). En ese caso la cola se vacía y DD rechaza. Así que si NN se detiene en todas sus ramas con toda entrada, DD es un decididor. Como una máquina determinista es un caso particular de una no determinista, un lenguaje es decidible si y solo si lo reconoce alguna máquina no determinista que se detiene en todas sus ramas.

Si alguna rama no se detiene y ninguna acepta, DD tampoco se detiene, y está bien: NN no aceptaba esa entrada, y DD solo tiene que reconocer el mismo lenguaje.

$ build/ntm_demo machines/nondet_branch.tm 00 5
w = 00
nivel 0:   q0 00
nivel 1:   0 q1 0   0 q0 0
nivel 2:   00 q1 _   00 q1 _   00 q0 _
nivel 3:   00_ q1 _   00_ q1 _   00_ q_reject _
nivel 4:   00__ q1 _   00__ q1 _
nivel 5:   00___ q1 _   00___ q1 _
por niveles: ninguna rama aceptó hasta el nivel 5
siempre la primera opción: no se detuvo en 1000000 pasos

Una rama rechaza en el nivel 3 y desaparece. Las otras dos siguen para siempre, y el recorrido con ellas.

En C++. breadth_first en ntm.h es la máquina DD. Guarda la cola nivel por nivel, en dos std::vector<Config>, que es el mismo orden: todas las configuraciones de un nivel antes que las del siguiente. Los hijos de una configuración los calcula successors, que aplica cada acción posible a una copia.

El costo. La simulación es correcta y es carísima. Si la rama que acepta tiene tt pasos, DD puede tener que procesar del orden de btb^t configuraciones antes de llegar a ella: un tiempo exponencial en tt. No se conoce ninguna simulación determinista que evite ese salto. Varias cintas costaban un cuadrado; el no determinismo, hasta donde se sabe, cuesta una exponencial. Esta semana no importa, porque solo preguntamos qué se puede calcular. En la semana 12, esa diferencia entre un cuadrado y una exponencial es la pregunta de si P es igual a NP.

Error común. Pensar que una máquina no determinista “prueba todas las ramas” y que eso es un algoritmo. La máquina no determinista no recorre nada: la definición solo dice que acepta si existe una rama que acepta. Quien recorre el árbol es la máquina determinista que la simula, y paga por cada configuración.

Enumeradores

La tercera variante cambia lo que la máquina hace con un lenguaje. Las máquinas de hasta ahora reciben una cadena y responden. Un enumerador (enumerator) no recibe nada: es una máquina de Turing con una impresora, que empieza con la cinta en blanco y, mientras trabaja, va imprimiendo cadenas. El lenguaje que enumera es el conjunto de todas las cadenas que imprime en algún momento.

No se le pide ningún orden, puede imprimir la misma cadena muchas veces, y puede no detenerse nunca. De hecho, si el lenguaje es infinito, no se detiene. Formalmente la impresora es una segunda cinta, de solo escritura, y “imprimir” es pasar por un estado especial que da por terminada la cadena escrita ahí. No necesitaremos más detalle que ese.

Reconocer y enumerar parecen tareas distintas: una responde preguntas sobre cadenas sueltas, la otra produce la lista. Son la misma.

Teorema. Un lenguaje es reconocible si y solo si algún enumerador lo enumera.

Demostración. Por construcción, en las dos direcciones.

De un enumerador a una máquina que reconoce. Sea EE un enumerador de LL. La máquina MM es:

M = "Con la entrada w:
  1. Ejecutar E. Cada vez que E imprime una cadena, compararla con w.
  2. Si alguna vez son iguales, aceptar. Si E se detiene sin haber impreso w, rechazar."

MM acepta ww exactamente cuando EE imprime ww en algún momento, es decir, cuando w∈Lw \in L. Con una cadena que no está en LL, MM espera para siempre si EE no se detiene. No importa: MM solo tiene que reconocer.

De una máquina que reconoce a un enumerador: el intento que falla. Sea MM una máquina que reconoce LL. Lo natural sería tomar las cadenas de Σ∗\Sigma^* en el orden de siempre, s1,s2,s3,…s_1, s_2, s_3, \ldots (primero las más cortas, como en la semana 1), y hacer: ejecutar MM con s1s_1, y si acepta, imprimirla; después con s2s_2; y así. Falla en cuanto MM no se detiene con alguna cadena: el enumerador se queda ahí para siempre y nunca llega a las que siguen. Con has_one_loops.tm falla en el primer intento, porque s1=εs_1 = \varepsilon no tiene unos.

El arreglo es el mismo que con el no determinismo: no terminar una cosa antes de empezar la siguiente.

E = "Sin mirar la entrada:
  1. Para i = 1, 2, 3, …:
  2.     Ejecutar M durante i pasos con cada una de las cadenas s1, s2, …, si.
  3.     Imprimir cada cadena que M haya aceptado en esos i pasos."

Por qué funciona. Cada ronda termina: son ii ejecuciones de a lo sumo ii pasos. Así que EE llega a todas las rondas.

  • EE solo imprime cadenas de LL: imprime sjs_j únicamente si MM la aceptó.
  • EE imprime todas las cadenas de LL: si w∈Lw \in L, entonces w=sjw = s_j para algún jj, y MM la acepta en alguna cantidad de pasos tt. En la ronda i=max⁡(j,t)i = \max(j, t), la cadena sjs_j está entre las ii primeras y MM tiene pasos suficientes: EE la imprime. La imprime también en todas las rondas siguientes, y un enumerador puede repetir. ∎

El programa enumerate hace eso con una máquina del curso. Con la que no se detiene:

$ build/enumerate machines/has_one_loops.tm 8
ronda 1:
ronda 2:
ronda 3: 1
ronda 4: 1
ronda 5: 1 01
ronda 6: 1 01 10
ronda 7: 1 01 10 11
ronda 8: 1 01 10 11
cadenas distintas impresas en 8 rondas (4): 1 01 10 11

Las cadenas en orden son ε\varepsilon, 0\mathtt{0}, 1\mathtt{1}, 00\mathtt{00}, 01\mathtt{01}, 10\mathtt{10}, 11\mathtt{11}, … La cadena 1\mathtt{1} es s3s_3 y la máquina la acepta en un paso: sale por primera vez en la ronda max⁡(3,1)=3\max(3, 1) = 3. La cadena 01\mathtt{01} es s5s_5 y se acepta en dos pasos: sale en la ronda 5. Con ε\varepsilon, 0\mathtt{0} y 00\mathtt{00} la máquina no se detiene, y el enumerador las vuelve a intentar en cada ronda con un paso más, sin quedarse atascado en ninguna.

Esta técnica, repartir el trabajo entre infinitas tareas dándole a cada una un poco más cada vez, se llama en inglés dovetailing. La volveremos a usar.

El teorema explica el otro nombre de los lenguajes reconocibles: recursivamente enumerables. Son los lenguajes cuyos elementos se pueden listar con un procedimiento mecánico.

En la práctica. Un sistema operativo hace lo mismo que el enumerador con los procesos que corre: no espera a que uno termine para atender al siguiente, porque alguno puede no terminar nunca. Le da a cada uno un rato de procesador y pasa al que sigue. Es la misma solución al mismo problema: no se puede saber de antemano cuál de las tareas va a terminar.

Otros modelos equivalentes

Las tres variantes de este capítulo son máquinas de Turing con algo cambiado. Más convincente es lo que pasó con modelos que no se parecen en nada a una máquina de Turing y que se propusieron por separado, en los mismos años, para responder la misma pregunta: qué quiere decir “calculable”.

  • El cálculo λ\lambda, de Alonzo Church (década de 1930). No tiene máquina ni memoria: solo funciones que se aplican a funciones, y una regla para reemplazar un parámetro por su argumento. Es el antepasado de los lenguajes funcionales.
  • Las funciones recursivas, de Gödel, Herbrand y Kleene. Son funciones sobre los números naturales que se arman a partir de unas pocas funciones básicas, con composición, recursión y búsqueda del menor número que cumple una condición.
  • Las máquinas de Turing (1936), pensadas por Alan Turing a partir de lo que hace una persona que calcula con lápiz y papel.
  • La máquina con memoria de acceso directo (RAM), el modelo de los cursos de algoritmos: registros que guardan números, y un programa con instrucciones para sumar, leer y escribir en la celda cuyo número está en un registro, y saltar. Es una idealización de una computadora real.
  • Cualquier lenguaje de programación de uso general: C++, Python, o el ensamblador de un procesador, con memoria sin límite.

Para cada par de modelos de la lista se demostró que uno simula al otro. Todos calculan exactamente lo mismo que una máquina de Turing. Esos resultados sí son teoremas, cada uno con su construcción.

Una de esas simulaciones la tienen a la vista. tm.h es un programa en C++ que ejecuta cualquier máquina de Turing: C++ puede hacer todo lo que hace una máquina de Turing. En la otra dirección, la cadena es más larga pero cada eslabón es conocido: un programa en C++ se compila a instrucciones de máquina; esas instrucciones operan sobre registros y sobre celdas de memoria numeradas; y una máquina de Turing de varias cintas simula eso guardando la memoria en una cinta, como una lista de pares de dirección y contenido, y cada registro en otra. Leer una celda de memoria le cuesta a la máquina recorrer la lista, en lugar de un solo paso. Es más lento. No es menos.

Error común. Creer que una computadora real calcula más que una máquina de Turing porque es más rápida. La velocidad no es poder de cómputo. La pregunta de esta parte del curso es qué problemas tienen solución, y una máquina más rápida resuelve los mismos problemas en menos tiempo: ni uno más. Si se compara con cuidado, la que pierde es la computadora real, porque su memoria es finita: en rigor es un autómata finito con una cantidad enorme de estados. La máquina de Turing es el modelo de una computadora a la que nunca se le acaba la memoria.

La tesis de Church-Turing

Todo lo anterior apunta en una dirección, y la afirmación a la que apunta tiene nombre.

Tesis de Church-Turing. Lo que se puede calcular con un procedimiento mecánico es exactamente lo que se puede calcular con una máquina de Turing.

Un “procedimiento mecánico” es lo que siempre se entendió por algoritmo: una receta finita, de instrucciones precisas, que una persona puede seguir con lápiz y papel sin necesidad de ingenio ni de suerte, y que no usa más que una cantidad finita de trabajo en cada paso.

Una de las dos direcciones no tiene nada de discutible: lo que una máquina de Turing calcula, lo calcula un procedimiento mecánico, porque seguir una tabla de transiciones es uno. Lo que la tesis afirma es la otra: que no hay ningún procedimiento mecánico que quede fuera.

Por qué no es un teorema

Un teorema relaciona objetos matemáticos, y se demuestra a partir de sus definiciones. La tesis relaciona un objeto matemático, la máquina de Turing, con una noción que no tiene definición matemática: la idea intuitiva de procedimiento mecánico, que existía siglos antes que las máquinas. No se puede demostrar que una definición captura una intuición. Lo que se puede hacer es dar razones para creerlo, y estar atentos a un contraejemplo.

La tesis es entonces una afirmación sobre el mundo: dice algo sobre lo que las personas y los aparatos pueden llegar a calcular. Se parece más a una ley de la física que a un teorema. Y como una ley de la física, se podría refutar: bastaría mostrar un procedimiento que todos reconozcan como mecánico y que ninguna máquina de Turing pueda seguir. Lo que la sostiene es evidencia.

La evidencia

Son cuatro tipos de evidencia, y conviene distinguirlos.

  1. Todos los modelos coinciden. El cálculo λ\lambda, las funciones recursivas, las máquinas de Turing, las máquinas RAM y todos los lenguajes de programación se propusieron con ideas muy distintas, y se demostró que calculan lo mismo. Si “calculable” fuera una noción vaga, cada formalización habría trazado la frontera en un lugar diferente.
  2. El modelo es robusto. Darle a la máquina más cintas, una cinta infinita hacia los dos lados, no determinismo o un movimiento más no cambia lo que puede calcular. Es lo que se demostró en este capítulo. La definición no depende de sus detalles.
  3. El análisis de Turing. Turing no propuso su máquina al azar. Partió de una persona que calcula sobre papel y argumentó que solo puede distinguir una cantidad finita de símbolos de un vistazo, que solo puede estar en una cantidad finita de “estados mentales” distintos, y que en cada momento mira una parte acotada del papel y cambia una parte acotada. Una máquina con esas tres limitaciones es una máquina de Turing. Es un argumento de que la definición no deja nada fuera, y es el que convenció a sus contemporáneos.
  4. No hay contraejemplo. En casi noventa años, cada algoritmo que alguien ha inventado, en cualquier área, se ha podido programar. Y cada modelo nuevo de cómputo que se ha propuesto, incluidas las computadoras cuánticas, calcula las mismas funciones: una máquina de Turing puede simular una computadora cuántica. Lo que una computadora cuántica podría cambiar es cuánto se tarda, que es otra pregunta.

Ninguno de los cuatro es una demostración. Juntos son la razón por la que la tesis se acepta sin reservas en la práctica.

Error común. Citar la tesis de Church-Turing como si fuera un teorema: “por el teorema de Church-Turing, este algoritmo se puede hacer con una máquina de Turing”. Que una máquina de varias cintas tiene una equivalente de una cinta es un teorema, y tiene demostración. Que todo algoritmo se puede escribir como máquina de Turing es la tesis, y lo que tiene es evidencia.

Qué permite

La tesis le da al curso dos cosas.

Una definición. Desde ahora, algoritmo quiere decir máquina de Turing, y más precisamente, máquina de Turing que se detiene con toda entrada. Parece poca cosa, y es lo que hace posible la semana 9. Para mostrar que un problema tiene algoritmo nunca hizo falta una definición: basta escribir uno, y todos lo reconocen. Para demostrar que un problema no tiene ningún algoritmo hay que razonar sobre todos los algoritmos posibles a la vez, y eso solo se puede hacer si “algoritmo” es un objeto matemático. Con la tesis, “ningún algoritmo decide LL” se convierte en “ninguna máquina de Turing decide LL”, que es un enunciado que se puede demostrar.

Hay un caso famoso. En 1900, David Hilbert pidió “un proceso” que, dado un polinomio con coeficientes enteros y varias variables, determinara “en una cantidad finita de operaciones” si tiene una raíz entera. Hilbert daba por hecho que ese proceso existía y que faltaba encontrarlo. En 1970, Yuri Matiyasevich, completando el trabajo de Martin Davis, Hilary Putnam y Julia Robinson, demostró que no existe. Esa demostración no se podía ni empezar en 1900: hacía falta saber qué era exactamente un “proceso” para poder mostrar que ninguno servía.

Un permiso. Si todo procedimiento mecánico tiene su máquina de Turing, no hace falta escribir la tabla cada vez. Desde la semana 9 las máquinas se describen en el nivel alto, como algoritmos en pasos numerados, y cuando haga falta se usa cualquier comodidad: varias cintas, variables, estructuras de datos. Cada vez que lo hagamos estaremos afirmando que existe una tabla que hace eso, y la tesis, con los teoremas de este capítulo detrás, es lo que respalda esa afirmación.

Con el problema de Hilbert se ve cómo se usa el nivel alto, y vuelve la diferencia entre reconocer y decidir. Tomemos el caso de una sola variable:

D1={ ⟨p⟩:p es un polinomio en x con coeficientes enteros y alguna raıˊz entera }D_1 = \{\, \langle p \rangle : p \text{ es un polinomio en } x \text{ con coeficientes enteros y alguna raíz entera} \,\}

Una máquina que reconoce D1D_1 prueba todos los enteros, uno por uno:

M1 = "Con la entrada ⟨p⟩, donde p es un polinomio en x con coeficientes enteros:
  1. Evaluar p en x = 0, 1, −1, 2, −2, 3, −3, …, en ese orden.
  2. Si alguna vez el resultado es 0, aceptar."

Si pp tiene una raíz entera, M1M_1 la encuentra y acepta. Si no la tiene, M1M_1 no se detiene nunca. Reconoce y no decide. Para decidir hace falta saber cuándo dejar de buscar, y aquí un poco de álgebra lo da. Sea p(x)=adxd+⋯+a1x+a0p(x) = a_d x^d + \cdots + a_1 x + a_0. Si rr es una raíz entera distinta de 0, entonces a0=−r(adrd−1+⋯+a1)a_0 = -r(a_d r^{d-1} + \cdots + a_1), y por lo tanto rr divide a a0a_0. Si además a0≠0a_0 \neq 0, se sigue que ∣r∣≤∣a0∣|r| \leq |a_0|.

M2 = "Con la entrada ⟨p⟩, donde p es un polinomio en x con coeficientes enteros:
  1. Si el término independiente a0 es 0, aceptar: x = 0 es una raíz.
  2. Evaluar p en cada entero x con 1 ≤ |x| ≤ |a0|.
  3. Si algún resultado es 0, aceptar. Si no, rechazar."

M2M_2 prueba una cantidad finita de valores y se detiene siempre: D1D_1 es decidible. Con varias variables, la máquina que prueba todas las combinaciones de enteros sigue reconociendo el lenguaje, pero lo que Matiyasevich demostró es que ese lenguaje no es decidible: ningún cálculo da una cota que juegue el papel de ∣a0∣|a_0| y diga cuándo dejar de buscar. No lo demostraremos, pero en la semana 9 veremos el primer lenguaje reconocible y no decidible, con su demostración completa.

Codificar objetos como cadenas

Las dos máquinas anteriores reciben “un polinomio”. Pero una máquina de Turing recibe una cadena. Lo que permite hablar de máquinas que trabajan con polinomios, grafos, autómatas o gramáticas es que cualquier objeto finito se puede escribir como una cadena.

Notación. Si OO es un objeto, ⟨O⟩\langle O \rangle es una codificación (encoding) de OO como cadena. Si son varios, ⟨O1,O2,…,Ok⟩\langle O_1, O_2, \ldots, O_k \rangle es una sola cadena que los codifica a todos.

Ya lo hicieron muchas veces. Un grafo no dirigido con nodos 1, 2, 3, 4 y aristas entre 1 y 2, entre 2 y 3, entre 3 y 1, y entre 1 y 4 se puede escribir como la lista de sus nodos seguida de la lista de sus aristas:

(1,2,3,4)((1,2),(2,3),(3,1),(1,4))

Eso es una cadena sobre el alfabeto de los dígitos, los paréntesis y la coma, y es un ⟨G⟩\langle G \rangle posible. La matriz de adyacencia escrita fila por fila sería otro. Con las codificaciones, un problema sobre grafos es un lenguaje, como vimos en la semana 1:

A={ ⟨G⟩:G es un grafo no dirigido conexo, con al menos un nodo }A = \{\, \langle G \rangle : G \text{ es un grafo no dirigido conexo, con al menos un nodo} \,\}

Y una máquina que lo decide se describe en el nivel alto, hablando del grafo y no de la cadena:

M = "Con la entrada ⟨G⟩, la codificación de un grafo no dirigido G con al menos un nodo:
  1. Marcar el primer nodo de G.
  2. Repetir hasta que no se marque ningún nodo nuevo:
  3.     Por cada nodo de G, marcarlo si tiene una arista hacia un nodo ya marcado.
  4. Si todos los nodos de G quedaron marcados, aceptar. Si no, rechazar."

Es un decididor: cada repetición del paso 2 marca al menos un nodo nuevo o es la última, así que hay a lo sumo tantas repeticiones como nodos, más una.

Tres acuerdos sobre las codificaciones, que valen desde ahora.

  • La primera línea dice qué se espera. “Con la entrada ⟨G⟩\langle G \rangle, la codificación de un grafo” incluye un paso que no se escribe: la máquina comprueba primero que la cadena recibida codifica de verdad un grafo, y si no, rechaza. Una cadena mal formada no está en el lenguaje, como dijimos en la semana 1.
  • Para la computabilidad, los detalles de la codificación no importan. Una máquina de Turing puede convertir una lista de aristas en una matriz de adyacencia, y al revés. Así que si un lenguaje es decidible con una codificación razonable, lo es con cualquier otra. Por eso se escribe ⟨G⟩\langle G \rangle sin decir cuál.
  • Para el costo sí van a importar. Un número escrito en binario ocupa muchísimo menos que el mismo número escrito con palitos, y un algoritmo que parece rápido medido contra la segunda escritura puede ser lento medido contra la primera. Es un tema de la semana 12.

Entre los objetos finitos que se pueden codificar hay uno especial: una máquina de Turing. Una máquina es una séptupla de conjuntos finitos y una tabla finita. Se puede escribir completa, y ya lo hemos hecho: el archivo machines/zeros_ones.tm es una cadena de 327 caracteres que describe a la máquina sin ambigüedad. Ese archivo es un ⟨M⟩\langle M \rangle.

$ wc -c machines/zeros_ones.tm
327 machines/zeros_ones.tm

Entonces una máquina de Turing puede recibir como entrada otra máquina de Turing. La entrada del laboratorio de esta semana es exactamente eso: una máquina y unas cadenas, ⟨M,w⟩\langle M, w \rangle, y el programa que van a escribir hace con ellas lo que MM haría con ww. Que una máquina pueda recibir máquinas, ejecutarlas y hacerse preguntas sobre ellas es el punto de partida de la semana 9. Ahí la pregunta será qué se puede averiguar sobre una máquina leyendo su descripción, y la primera respuesta ya la conocen: ejecutarla y esperar no alcanza, porque puede no detenerse.

En la práctica. Un programa que recibe programas es lo más común que hay: un compilador, un intérprete, un depurador, un antivirus, el juez del curso. El código fuente es ⟨M⟩\langle M \rangle. Que los programas sean datos es la idea que hizo posible la computadora de propósito general: una sola máquina que ejecuta cualquier programa que se le entregue, en lugar de una máquina distinta para cada tarea.

El código de la semana

code/week-07/
├── tm.h                  struct Tm, lectura del formato .tm, configuraciones, un paso, ejecutar con límite
├── show_tm.cpp           muestra un .tm como séptupla y como tabla
├── run_tm.cpp            la ejecución de una máquina, configuración por configuración
├── multitape.h           máquinas de k cintas y su simulación con una sola cinta
├── multitape_demo.cpp    la máquina de dos cintas, la simulación y la tabla de pasos
├── ntm.h                 máquinas no deterministas y el recorrido por niveles
├── ntm_demo.cpp          el árbol de ejecuciones, nivel por nivel
├── enumerate.cpp         de una máquina que reconoce a un enumerador
├── machines/             las máquinas del capítulo, en formato .tm
├── errors/               cuatro descripciones que no son una máquina determinista válida
├── test_tm.cpp           cada máquina contra un predicado; las cuentas de pasos; la que no se detiene
├── test_multitape.cpp    la simulación coincide paso a paso y respeta la cota cuadrática
├── test_variants.cpp     el recorrido por niveles y el enumerador
└── lab/tm_sim/           el laboratorio

make compila todo, y make test corre las pruebas con ASan y UBSan. Las pruebas comprueban con assert lo que este capítulo afirma.

  • test_tm compara cada decididor de machines/ con una función de C++ que decide el mismo lenguaje, sobre todas las cadenas hasta cierta longitud, con un límite de 100 000 pasos, y comprueba que el límite no se alcanza nunca y que ninguna ejecución pasa de n2+n+2n^2 + n + 2 pasos. Comprueba las fórmulas exactas de pasos de las tres máquinas, las ejecuciones copiadas en estos apuntes, que has_one_loops.tm pasa de 1 000 000 de pasos con 000\mathtt{000} en la configuración que dice la afirmación, el borde izquierdo y que los archivos de errors/ no se cargan.
  • test_multitape comprueba que la máquina de dos cintas decide { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\} en a lo sumo n+3n + 3 pasos con entradas de longitud nn, que la cinta de la simulación representa la configuración de la máquina simulada después de cada paso, las tres cotas de la cuenta de costo, y los números de la tabla.
  • test_variants comprueba que el recorrido por niveles acepta las cadenas con algún 1\mathtt{1} en el nivel esperado, que seguir siempre la primera opción no termina con las cadenas que empiezan con 0\mathtt{0}, que una máquina determinista vista como no determinista responde lo mismo, y que el enumerador imprime cada cadena en la ronda max⁡(j,t)\max(j, t).
$ make test
test_tm:
  zeros_ones: 16383 cadenas, a lo sumo 98 pasos
  w_sep_w:    29524 cadenas, a lo sumo 50 pasos
  anbncn:     29524 cadenas, a lo sumo 46 pasos
  has_one:    16383 cadenas, a lo sumo 14 pasos
test_tm: ok
test_multitape:
  dos cintas: 4095 cadenas, la simulación coincide paso a paso
  180 máquinas al azar de 1, 2 y 3 cintas: la simulación coincide paso a paso
test_multitape: ok
test_variants: ok
Todas las pruebas pasaron.

Los archivos de machines/ son:

Archivo Qué hace Estados
zeros_ones.tm Decide { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\} 6
w_sep_w.tm Decide { w#w }\{\, w\mathtt{\#}w \,\}, con = como separador 10
anbncn.tm Decide { anbncn }\{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n \,\} 8
has_one.tm Decide las cadenas con algún 1\mathtt{1} 3
has_one_loops.tm Reconoce el mismo lenguaje y no lo decide 3
left_end.tm No se detiene con ninguna entrada: repite una configuración en el borde izquierdo 4
nondet_branch.tm No determinista, con una rama que no se detiene 4

La cuenta de estados incluye a q_accept y q_reject. Para experimentar, copien una máquina, cámbienle una transición y vuelvan a correr run_tm con las mismas cadenas.

En tm.h, igual que en el dfa.h de la semana 1, δ\delta es un std::map con los nombres de los estados como cadenas. Se eligió así para que el código se lea como la definición, y no por velocidad: cada paso busca en el mapa comparando nombres. Para los ejemplos del capítulo sobra. Para el laboratorio no.

El laboratorio

En lab/tm_sim está el enunciado, un esqueleto y los casos. El problema es escribir un simulador: la entrada es una máquina de Turing determinista en formato .tm, un límite de pasos NN y una lista de cadenas, y la salida es, por cada cadena, acepta, rechaza o no se detuvo en N pasos.

cd lab/tm_sim
make        # compila solution.cpp
make test   # corre el juez con todos los casos

solution.cpp se escribe sin incluir tm.h. El trabajo está en tres sitios. El primero es leer el formato completo: la línea limit: va entre la última transición y el bloque strings:. El segundo son los casos de borde, que son los de este capítulo: la cadena vacía, un movimiento a la izquierda en la primera celda, una transición que falta, una máquina que no se detiene, y una que se detiene justo en el paso NN. El tercero es la cinta. Tiene que crecer hacia la derecha sin un tamaño fijo, y cada paso tiene que costar tiempo constante: los casos grandes dan decenas de millones de pasos sobre cintas de cientos de miles de celdas, y una cinta que se copia o se corre en cada paso no termina a tiempo. El enunciado propone además una opción para imprimir las configuraciones, que el juez no usa y que les va a servir para depurar sus propias máquinas.

Resumen

  • Una máquina de Turing es M=(Q,Σ,Γ,δ,q0,qaccept,qreject)M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}}): un control finito, una cinta infinita hacia la derecha y un cabezal que lee, escribe y se mueve una celda por paso. δ(q,a)=(r,b,D)\delta(q, a) = (r, b, D): pasar a rr, escribir bb, mover hacia DD.
  • En este curso, un movimiento L\mathrm{L} en la primera celda deja el cabezal donde está, y un par sin transición lleva a qrejectq_{\text{reject}}.
  • Una configuración u q vu\,q\,v es el estado, la cinta y la posición del cabezal, que está sobre el primer símbolo de vv. La ejecución es la secuencia de configuraciones, cada una produce la siguiente.
  • Con una entrada, la máquina acepta, rechaza o no se detiene. Que no se haya detenido en NN pasos no dice que no se vaya a detener.
  • Las máquinas de { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\}, { w#w }\{\, w\mathtt{\#}w \,\} y { anbncn }\{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n \,\} usan la misma técnica: marcar lo procesado y dar vueltas. Las tres se detienen en a lo sumo n2+n+2n^2 + n + 2 pasos.
  • MM reconoce L(M)L(M). Si además se detiene con toda entrada, es un decididor y lo decide. Un lenguaje es reconocible o decidible si alguna máquina lo reconoce o lo decide. Todo decidible es reconocible.
  • Una máquina se describe en tres niveles: formal (la tabla), de implementación (el cabezal, en prosa) y alto (un algoritmo en pasos).
  • Varias cintas no agregan poder: una cinta las simula con separadores y marcas, en O(t2)O(t^2) pasos.
  • El no determinismo tampoco: una máquina determinista recorre el árbol de ejecuciones por niveles. En profundidad no sirve, porque una rama puede ser infinita. La simulación cuesta un tiempo exponencial.
  • Un lenguaje es reconocible si y solo si algún enumerador lo enumera. La construcción ejecuta la máquina ii pasos con las primeras ii cadenas, para i=1,2,3,…i = 1, 2, 3, \ldots
  • El cálculo λ\lambda, las funciones recursivas, la máquina RAM y los lenguajes de programación calculan lo mismo que las máquinas de Turing. Una computadora más rápida no calcula más.
  • La tesis de Church-Turing dice que lo calculable por un procedimiento mecánico es lo calculable por una máquina de Turing. No es un teorema: relaciona una definición con una noción intuitiva, y se sostiene con evidencia. Permite definir algoritmo y describir las máquinas en el nivel alto.
  • ⟨O⟩\langle O \rangle es la codificación de un objeto como cadena. Una máquina de Turing también se codifica, ⟨M⟩\langle M \rangle, y puede ser la entrada de otra.

Ejercicios

  1. Escriban a mano las configuraciones de la máquina de machines/zeros_ones.tm con las entradas 0011\mathtt{0011}, 001\mathtt{001} y 0101\mathtt{0101}, y comprueben con run_tm. En las dos que rechaza, digan qué casilla vacía de la tabla usó y qué quiere decir sobre la entrada.
  2. Para cada configuración, escriban la que produce, con la máquina de machines/w_sep_w.tm y las tres reglas de la sección Configuraciones: (a) X q1 1#01\mathtt{X}\,q_1\,\mathtt{1\#01}; (b) X1 q5 #X1\mathtt{X1}\,q_5\,\mathtt{\#X1}; (c) q6 X1#X1q_6\,\mathtt{X1\#X1}; (d) XX#XX q7 ⊔\mathtt{XX\#XX}\,q_7\,\sqcup. Después expliquen con la tercera regla por qué left_end.tm repite la configuración q1 01q_1\,\mathtt{01}.
  3. Modifiquen la máquina de { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\} para que decida { 0n12n:n≥0 }\{\, \mathtt{0}^n\mathtt{1}^{2n} : n \geq 0 \,\}. Den la tabla de lo que hace cada estado y el archivo .tm, y pruébenlo con run_tm --quiet en diez cadenas, cinco del lenguaje y cinco que no. ¿Cuántos pasos da con 0n12n\mathtt{0}^n\mathtt{1}^{2n}?
  4. Den una descripción de implementación de una máquina que decide { aibjck:i×j=k e i,j,k≥1 }\{\, \mathtt{a}^i\mathtt{b}^j\mathtt{c}^k : i \times j = k \text{ e } i, j, k \geq 1 \,\}. Digan qué marcas usa y por qué se detiene siempre. Después escriban el archivo .tm y compruébenlo con todas las cadenas de la forma aibjck\mathtt{a}^i\mathtt{b}^j\mathtt{c}^k con i,j≤3i, j \leq 3 y k≤9k \leq 9.
  5. Demuestren que la máquina de machines/w_sep_w.tm decide { w#w }\{\, w\mathtt{\#}w \,\}, con el esquema de la demostración de { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\}: enuncien qué conserva cada vuelta, y úsenlo para mostrar que si la máquina acepta, la entrada está en el lenguaje. Después cuenten los pasos con w#ww\mathtt{\#}w y ∣w∣=n|w| = n, y verifiquen que son 2n2+4n+22n^2 + 4n + 2.
  6. Diseñen una máquina de Turing que decida los palíndromos sobre {0,1}\{\mathtt{0}, \mathtt{1}\}. Den los tres niveles de descripción. En el formal, ¿cómo sabe la máquina dónde está el borde izquierdo de lo que falta revisar? Den una cota para la cantidad de pasos con una entrada de longitud nn.
  7. Demuestren que los lenguajes decidibles son cerrados bajo unión y bajo intersección, describiendo en el nivel alto la máquina que decide. Después demuestren que los reconocibles son cerrados bajo unión. ¿Por qué no sirve “ejecutar M1M_1 con ww; si acepta, aceptar; si no, ejecutar M2M_2 con ww”? ¿Qué técnica de este capítulo lo arregla?
  8. Una máquina con cinta infinita hacia los dos lados no tiene primera celda: el cabezal siempre puede ir a la izquierda. Describan, en el nivel de implementación, cómo la simula una máquina del modelo del curso. Una idea: doblar la cinta por la mitad, de modo que cada celda guarde dos símbolos. Digan qué tiene que recordar el estado.
  9. Den una máquina de dos cintas que decida { w#w }\{\, w\mathtt{\#}w \,\} en una cantidad de pasos lineal en la longitud de la entrada: la tabla en el formato de la sección Máquinas de varias cintas, y la cuenta de pasos. ¿Qué cota da el teorema del costo para su simulación con una cinta? Compárenla con los 2n2+4n+22n^2 + 4n + 2 pasos de la máquina de una cinta.
  10. En la demostración de que el recorrido por niveles funciona, ¿dónde se usa que cada configuración tiene una cantidad finita de hijos? Supongan un modelo en el que una configuración pudiera tener infinitos hijos: muestren que el recorrido por niveles podría no llegar nunca al nivel 2. Después den una máquina no determinista de tres estados de trabajo en la que el recorrido en profundidad falle aunque se elija siempre la última opción en lugar de la primera.
  11. Un enumerador imprime en orden si imprime las cadenas de su lenguaje primero las más cortas y, entre las de igual longitud, en el orden del alfabeto, sin repetir. Demuestren que un lenguaje es decidible si y solo si algún enumerador lo imprime en orden. Una de las dos direcciones necesita tratar aparte el caso en que el lenguaje es finito: digan cuál y por qué.
  12. Para programar. Modifiquen enumerate.cpp para que imprima cada cadena una sola vez, sin guardar la lista de las que ya imprimió. Pista: la cadena sjs_j, que la máquina acepta en tt pasos, sale por primera vez en la ronda max⁡(j,t)\max(j, t); ¿cómo se reconoce, dentro de una ronda, que es la primera?
  13. Para programar. Agreguen a tm.h una función que ejecute una máquina y se detenga cuando una configuración se repite, respondiendo “no se detiene”. Pruébenla con left_end.tm y con has_one_loops.tm. ¿Con cuál de las dos no sirve, y por qué? ¿Puede esa función responder “no se detiene” con una máquina que sí se detiene?
  14. Digan si cada afirmación es un teorema, es la tesis de Church-Turing o una consecuencia de ella, o es falsa, y justifiquen: (a) toda máquina de tres cintas tiene una equivalente de una cinta; (b) todo lo que hace un programa en Python lo puede hacer una máquina de Turing; (c) cualquier método de cálculo que se invente en el futuro se podrá simular con una máquina de Turing; (d) una computadora con el doble de memoria RAM decide lenguajes que la anterior no podía decidir, si las dos se idealizan con memoria sin límite; (e) si una máquina no se detuvo después de 1010010^{100} pasos, no se detiene.