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

Apuntes · Capítulo 9Computabilidad

Lo decidible y lo indecidible

Lo decidible y lo indecidible

En la semana 7 definimos la máquina de Turing y, con ella, qué es un algoritmo. Quedaron tres cosas que esta semana se usan todo el tiempo. La primera: una máquina de Turing puede terminar de tres maneras, porque acepta, rechaza o no se detiene nunca. La segunda: por eso hay dos maneras de “resolver” un lenguaje. Una máquina lo decide si se detiene con todas las entradas y acepta exactamente las cadenas del lenguaje. Lo reconoce si acepta exactamente esas cadenas, y con las demás puede rechazar o quedarse corriendo. Para abreviar, a una máquina que se detiene con todas las entradas la llamamos decididor (decider), y a una de la que solo pedimos que reconozca su lenguaje, reconocedor (recognizer). La tercera es la tesis de Church-Turing: todo lo que se puede calcular con un procedimiento mecánico se puede calcular con una máquina de Turing. Por eso desde ahora describimos las máquinas como algoritmos, en pasos numerados, sin escribir su tabla.

Con esas tres cosas ya se puede hacer la pregunta que el curso anunció el primer día: ¿qué no se puede calcular? En la semana 1 vimos, contando, que hay más lenguajes que programas, así que algún lenguaje se queda sin programa. Ese argumento no decía cuál. Esta semana lo dice: hay un problema concreto, natural y útil que ninguna máquina decide.

El capítulo tiene dos mitades que van en sentidos opuestos.

  • En la primera todo sale bien. Tomamos las preguntas que uno le haría a un autómata o a una gramática (¿acepta esta cadena?, ¿acepta alguna?, ¿estos dos son equivalentes?) y mostramos que cada una se puede decidir, con un algoritmo que siempre termina. Las construcciones de las semanas 1 a 5 vuelven, ahora como pasos de esos algoritmos.
  • En la segunda hacemos las mismas preguntas sobre máquinas de Turing, y la primera ya no se puede decidir: no existe un algoritmo que reciba una máquina MM y una cadena ww y diga siempre, correctamente, si MM acepta ww. La demostración es corta y usa una sola idea, la diagonal de Cantor. De ahí sale el problema de la parada, y también un lenguaje que ni siquiera se puede reconocer.

Es el centro del curso. Lo que sigue en las semanas 10 y 11 son consecuencias de la segunda mitad, y la parte de complejidad repite sus técnicas con un límite de tiempo.

Ruta de lectura.

Antes de clase (15–20 minutos): la introducción, Las máquinas como entradas y Aceptación: A_DFA, A_NFA y A_REX. Antes de la sesión B, La máquina universal y Conjuntos numerables y la diagonal de Cantor, que es un repaso de Matemática Discreta.

En clase: Sesión A, de Las máquinas como entradas a Todo lenguaje libre de contexto es decidible. Sesión B, de La máquina universal a Qué significa en la práctica.

Después de clase: el Resumen y los Ejercicios. Escriban la demostración de A_TM es indecidible sin mirar los apuntes: es la que hay que saber de memoria y, sobre todo, entender. Antes del laboratorio, Sin construir el producto y El código de la semana. Para ampliar, las lecturas de apoyo del recuadro siguiente.

Lectura. Sipser, sec. 4.1 (Decidable Languages) y sec. 4.2 (Undecidability). Erickson, Models of Computation, nota 7 (Undecidability). Son apoyo: estos apuntes se pueden estudiar solos.

Código. Los programas de este capítulo están en code/week-09. 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/dfa_equiv.

Las máquinas como entradas

Hasta ahora las entradas de nuestras máquinas fueron cadenas sin estructura: ceros y unos, paréntesis. Esta semana las entradas son otras máquinas. Queremos algoritmos que reciban un autómata y respondan algo sobre él.

Eso no pide nada nuevo. La entrada de una máquina de Turing es una cadena, y cualquier objeto finito se puede escribir como una cadena: lo vimos al final de la semana 7. Escribimos ⟨B⟩\langle B \rangle para la cadena que representa al objeto BB, y ⟨B,w⟩\langle B, w \rangle para la que representa al par formado por BB y ww. Ustedes ya tienen una codificación concreta de cada tipo de máquina: los archivos .dfa, .nfa, .cfg y .tm de code/formats.md son eso, cadenas que representan autómatas, gramáticas y máquinas de Turing. Un archivo .dfa es un ⟨B⟩\langle B \rangle.

Con esa notación, una pregunta sobre autómatas se vuelve un lenguaje, igual que cualquier otro problema de decisión. “¿El DFA BB acepta la cadena ww?” es el lenguaje

ADFA={ ⟨B,w⟩:B es un DFA que acepta w }A_{\mathrm{DFA}} = \{\, \langle B, w \rangle : B \text{ es un DFA que acepta } w \,\}

Fíjense en qué tipo de objeto es. No es el lenguaje de un autómata: es un lenguaje sobre autómatas. Sus cadenas son descripciones. La cadena ⟨B,w⟩\langle B, w \rangle está en ADFAA_{\mathrm{DFA}} cuando w∈L(B)w \in L(B). Preguntar si ADFAA_{\mathrm{DFA}} es decidible es preguntar si existe un solo algoritmo que sirva para todos los DFA y todas las cadenas.

Esta semana aparecen siete lenguajes de esta familia, y tres más sobre máquinas de Turing. Los nombres son los de Sipser: la letra dice la pregunta y el subíndice dice el modelo.

Lenguaje La pregunta Modelo
ADFAA_{\mathrm{DFA}}, ANFAA_{\mathrm{NFA}}, AREXA_{\mathrm{REX}} ¿Acepta (o genera) la cadena ww? DFA, NFA, expresión regular
EDFAE_{\mathrm{DFA}} ¿Su lenguaje es vacío? DFA
EQDFA\mathrm{EQ}_{\mathrm{DFA}} ¿Los dos reconocen el mismo lenguaje? Dos DFA
ACFGA_{\mathrm{CFG}}, ECFGE_{\mathrm{CFG}} ¿Genera ww? ¿Su lenguaje es vacío? Gramática libre de contexto
ATMA_{\mathrm{TM}}, HALTTM\mathrm{HALT}_{\mathrm{TM}} ¿Acepta ww? ¿Se detiene con ww? Máquina de Turing

La AA viene de acceptance, la EE de emptiness y EQ\mathrm{EQ} de equivalence.

Cómo se describe una máquina desde hoy

En la semana 7 vimos tres niveles para describir una máquina de Turing: formal, de implementación y de alto nivel. Desde este capítulo usamos el alto nivel: un algoritmo en pasos numerados, entre comillas, que empieza diciendo qué forma tiene la entrada.

M = "Con la entrada ⟨B, w⟩, donde B es un DFA y w una cadena:
  1. Simular B con la entrada w.
  2. Si la simulación termina en un estado de aceptación, aceptar. Si no, rechazar."

Tres acuerdos sobre este formato.

  • La primera línea incluye una comprobación. “Con la entrada ⟨B,w⟩\langle B, w \rangle, donde BB es un DFA” quiere decir que la máquina empieza revisando que la entrada sea de verdad la descripción de un DFA seguida de una cadena sobre su alfabeto. Si no lo es, rechaza. Es lo que hace load_dfa cuando un archivo está mal escrito. No lo repetimos en cada máquina.
  • Cada paso tiene que ser algo que una máquina de Turing sabe hacer, y que ustedes sabrían programar. “Simular BB con ww” lo es: es el laboratorio de la semana 1. “Decidir si L(B)L(B) es infinito” no es un paso legítimo hasta que alguien diga cómo.
  • Cada paso tiene que terminar, si lo que queremos es decidir. Es lo que más se va a mirar hoy.

Qué hay que demostrar

Para demostrar que un lenguaje LL es decidible se da una máquina y se demuestran dos cosas:

  1. Termina siempre. Con toda entrada, esté o no en LL, la máquina se detiene.
  2. Responde bien. Acepta las cadenas de LL y rechaza las demás.

La técnica es siempre una construcción: se exhibe el algoritmo. Y lo delicado casi siempre es el punto 1. Un algoritmo que responde bien cuando termina, pero que con algunas entradas no termina, reconoce y no decide.

Idea clave. Las máquinas son datos. Un autómata se escribe como una cadena ⟨B⟩\langle B \rangle, y una pregunta sobre autómatas es un lenguaje de descripciones. Decidir ese lenguaje es tener un programa que recibe cualquier autómata y siempre responde.

Aceptación: A_DFA, A_NFA y A_REX

A_DFA: decidir es simular

Teorema. ADFAA_{\mathrm{DFA}} es decidible.

Demostración. Por construcción. La máquina es la del ejemplo de arriba:

M = "Con la entrada ⟨B, w⟩, donde B es un DFA y w una cadena:
  1. Simular B con la entrada w.
  2. Si la simulación termina en un estado de aceptación, aceptar. Si no, rechazar."

Termina siempre. Simular BB es llevar la cuenta de un estado. Se empieza en el inicial y, por cada símbolo de ww, se busca en la tabla de δ\delta la transición que corresponde. Son exactamente ∣w∣|w| búsquedas en una tabla finita, y después MM responde.

Responde bien. Al terminar, el estado que MM tiene anotado es δ∗(q0,w)\delta^*(q_0, w). Por la definición de la semana 1, BB acepta ww si y solo si ese estado está en FF, que es lo que MM comprueba en el paso 2. ∎

Es el simulador que escribieron en el primer laboratorio. El programa a_dfa lo corre con uno de los autómatas de la semana 1, el de las cadenas binarias que terminan en 01\mathtt{01}:

$ build/a_dfa machines/ends_01.dfa 0101 ''
B = machines/ends_01.dfa, 3 estados
w = 0101
  q0 -0-> q1 -1-> q2 -0-> q1 -1-> q2
  4 pasos; termina en q2, que está en F: ⟨B, w⟩ ∈ A_DFA
w = ε
  q0
  0 pasos; termina en q0, que no está en F: ⟨B, w⟩ ∉ A_DFA

La demostración parece no decir nada, y conviene ver por qué sí dice algo. Lo que hace fácil a ADFAA_{\mathrm{DFA}} es que un DFA siempre termina: da un paso por símbolo y se acaba la entrada. La simulación hereda esa propiedad. Guarden esta observación, porque en la sesión B vamos a escribir la misma máquina con “máquina de Turing” en lugar de “DFA”, y la parte de “termina siempre” va a dejar de ser cierta.

A_NFA: convertir y simular

ANFA={ ⟨N,w⟩:N es un NFA que acepta w }A_{\mathrm{NFA}} = \{\, \langle N, w \rangle : N \text{ es un NFA que acepta } w \,\}

Teorema. ANFAA_{\mathrm{NFA}} es decidible.

Demostración. Por construcción, usando la máquina MM del teorema anterior como subrutina.

N' = "Con la entrada ⟨N, w⟩, donde N es un NFA y w una cadena:
  1. Convertir N en un DFA equivalente D, con la construcción de subconjuntos.
  2. Correr M con la entrada ⟨D, w⟩.
  3. Si M acepta, aceptar. Si M rechaza, rechazar."

Termina siempre. La construcción de subconjuntos de la semana 2 genera a lo sumo 2∣Q∣2^{|Q|} estados, uno por cada subconjunto de estados de NN, y calcula una transición por cada estado y cada símbolo: es una cantidad finita de trabajo. El paso 2 termina porque MM decide.

Responde bien. En la semana 2 demostramos que L(D)=L(N)L(D) = L(N). Entonces NN acepta ww si y solo si DD acepta ww, si y solo si MM acepta ⟨D,w⟩\langle D, w \rangle. ∎

El programa a_nfa hace esos dos pasos con el NFA de “el tercer símbolo desde el final es 1\mathtt{1}”:

$ build/a_nfa machines/third_from_end.nfa 0100 0010
N = machines/third_from_end.nfa, 4 estados
1. Construcción de subconjuntos: un DFA D con 8 estados (los subconjuntos alcanzables)
2. Correr D con cada cadena:
w = 0100
  {q0} -0-> {q0} -1-> {q0,q1} -0-> {q0,q2} -0-> {q0,q3}
  acepta: ⟨N, w⟩ ∈ A_NFA
w = 0010
  {q0} -0-> {q0} -0-> {q0} -1-> {q0,q1} -0-> {q0,q2}
  rechaza: ⟨N, w⟩ ∉ A_NFA

Dos cosas que esta demostración estrena y que se repiten todo el capítulo.

Una máquina puede llamar a otra. N′N' usa a MM como una función. Está permitido porque MM es un algoritmo, y un algoritmo puede ser un paso de otro. Lo que hay que cuidar es que la máquina llamada termine: si MM pudiera quedarse corriendo, N′N' también.

Las demostraciones de antes ahora son algoritmos. En la semana 2 el teorema decía “para todo NFA existe un DFA equivalente”. Lo demostramos construyendo el DFA, y por eso hoy podemos usarlo como el paso 1 de una máquina. Una demostración de existencia que no construyera nada no serviría aquí. Es la razón por la que el curso insiste en demostrar por construcción y en programar cada construcción en el laboratorio.

No hacía falta pasar por el DFA: se puede simular el NFA directamente, llevando el conjunto de estados activos, como en el laboratorio de la semana 2. Es otra máquina que decide el mismo lenguaje, y la más rápida de las dos. Para saber si un lenguaje es decidible cualquiera sirve, y la demostración más corta es la mejor. Cuánto cuesta decidir es la pregunta de la parte 4 del curso.

A_REX: otra conversión

AREX={ ⟨R,w⟩:R es una expresioˊn regular que genera w }A_{\mathrm{REX}} = \{\, \langle R, w \rangle : R \text{ es una expresión regular que genera } w \,\}

Teorema. AREXA_{\mathrm{REX}} es decidible.

Demostración. Por construcción, con la misma idea.

P = "Con la entrada ⟨R, w⟩, donde R es una expresión regular y w una cadena:
  1. Convertir R en un NFA equivalente N, con la construcción de Thompson.
  2. Correr N' con la entrada ⟨N, w⟩.
  3. Si N' acepta, aceptar. Si N' rechaza, rechazar."

Termina siempre. La construcción de Thompson de la semana 3 recorre la expresión una vez y agrega una cantidad fija de estados por cada operador y cada símbolo. El paso 2 termina porque N′N' decide.

Responde bien. En la semana 3 demostramos que L(N)=L(R)L(N) = L(R), y acabamos de demostrar que N′N' acepta ⟨N,w⟩\langle N, w \rangle exactamente cuando NN acepta ww. ∎

Esta cadena de conversiones, de expresión regular a NFA, de NFA a DFA y a simular, es lo que hace una herramienta como grep: es el laboratorio de la semana 3.

Idea clave. Para los tres modelos de los lenguajes regulares, “¿acepta esta cadena?” es decidible, y la demostración es la misma: convertir al modelo anterior con una construcción que ya demostramos, y simular. Lo que sostiene todo es que un DFA termina siempre.

¿El lenguaje es vacío?: E_DFA

La segunda pregunta ya no es sobre una cadena. Es sobre todas las cadenas a la vez:

EDFA={ ⟨A⟩:A es un DFA y L(A)=∅ }E_{\mathrm{DFA}} = \{\, \langle A \rangle : A \text{ es un DFA y } L(A) = \emptyset \,\}

Atención con el sentido: ⟨A⟩\langle A \rangle está en EDFAE_{\mathrm{DFA}} cuando AA no acepta nada.

Un primer intento es el que usarían para probar un programa: darle cadenas al autómata, de las más cortas a las más largas, y ver si acepta alguna.

"Con la entrada ⟨A⟩:
  1. Para cada cadena w de Σ*, en orden de longitud: simular A con w. Si A acepta, rechazar."

Si L(A)L(A) no es vacío, este procedimiento encuentra una cadena aceptada y rechaza, bien. Pero si L(A)L(A) es vacío, sigue probando cadenas para siempre, porque Σ∗\Sigma^* es infinito. Nunca llega a aceptar. Lo más que da esta idea es una máquina que confirma que el lenguaje no es vacío, cuando no lo es: un reconocedor del complemento de EDFAE_{\mathrm{DFA}}. No decide nada. No se puede decidir una pregunta sobre infinitas cadenas probándolas una por una.

La salida es dejar de mirar las cadenas y mirar el autómata, que es finito. AA acepta alguna cadena exactamente cuando hay un camino, en su diagrama, desde el estado inicial hasta algún estado de aceptación. Y eso es un problema de grafos que ya saben resolver.

Teorema. EDFAE_{\mathrm{DFA}} es decidible.

Demostración. Por construcción. La máquina marca los estados alcanzables.

T = "Con la entrada ⟨A⟩, donde A es un DFA:
  1. Marcar el estado inicial de A.
  2. Repetir hasta que no se marque ningún estado nuevo:
  3.     Marcar todo estado que tenga una transición que llega desde un estado ya marcado.
  4. Si ningún estado de aceptación quedó marcado, aceptar. Si alguno quedó marcado, rechazar."

Termina siempre. Cada repetición del paso 3 marca al menos un estado nuevo, o es la última. Como AA tiene ∣Q∣|Q| estados, hay a lo sumo ∣Q∣|Q| repeticiones, y cada una revisa una tabla finita.

Responde bien. Hay que ver que, al terminar, los estados marcados son exactamente los alcanzables: los de la forma δ∗(q0,w)\delta^*(q_0, w) para alguna cadena ww. Son dos direcciones.

  • Todo estado marcado es alcanzable. Por inducción sobre el orden en que se marcan. El primero es q0=δ∗(q0,ε)q_0 = \delta^*(q_0, \varepsilon). Si un estado rr se marca en el paso 3, es porque r=δ(q,a)r = \delta(q, a) para un estado qq marcado antes, que por hipótesis es δ∗(q0,x)\delta^*(q_0, x) para alguna xx. Entonces r=δ∗(q0,xa)r = \delta^*(q_0, xa).
  • Todo estado alcanzable queda marcado. Por inducción sobre ∣w∣|w|, se muestra que δ∗(q0,w)\delta^*(q_0, w) está marcado al terminar. Si w=εw = \varepsilon, es q0q_0, que se marcó en el paso 1. Si w=xaw = xa, el estado q=δ∗(q0,x)q = \delta^*(q_0, x) está marcado por hipótesis. Entonces δ(q,a)\delta(q, a) también lo está: si no, el paso 3 tendría todavía algo que marcar, y la máquina no habría salido del ciclo.

Ahora, L(A)≠∅L(A) \neq \emptyset si y solo si existe una cadena ww con δ∗(q0,w)∈F\delta^*(q_0, w) \in F, es decir, si y solo si algún estado de aceptación es alcanzable, es decir, si y solo si algún estado de aceptación quedó marcado. En ese caso TT rechaza, y en el otro acepta. ∎

El programa e_dfa muestra las marcas ronda por ronda. En la ronda dd quedan marcados los estados a distancia dd del inicial, porque la función que lo calcula es una búsqueda en anchura.

$ build/e_dfa machines/ends_01.dfa
A = machines/ends_01.dfa, 3 estados, F = {q2}
ronda 0: se marca q0
ronda 1: se marca q1
ronda 2: se marca q2
marcados: 3 de 3
hay un estado de aceptación marcado: L(A) ≠ ∅, ⟨A⟩ ∉ E_DFA
una cadena más corta de L(A): 01

Y un autómata que tiene un estado de aceptación y aun así no acepta nada. Este es machines/unreachable_accept.dfa:

δ\delta 0\mathtt{0} 1\mathtt{1}
aa (inicial) bb aa
bb bb aa
cc dd aa
dd (aceptación) dd cc

Desde aa solo se llega a aa y a bb. Los estados cc y dd se alcanzan entre sí, pero ninguna flecha entra a ellos desde los otros dos.

$ build/e_dfa machines/unreachable_accept.dfa
A = machines/unreachable_accept.dfa, 4 estados, F = {d}
ronda 0: se marca a
ronda 1: se marca b
marcados: 2 de 4
ningún estado de aceptación está marcado: L(A) = ∅, ⟨A⟩ ∈ E_DFA

Error común. Creer que L(A)=∅L(A) = \emptyset quiere decir F=∅F = \emptyset. Un autómata sin estados de aceptación no acepta nada, pero al revés no vale: el de arriba tiene F={d}F = \{d\} y su lenguaje es vacío. Lo que importa es si algún estado de FF es alcanzable.

En C++. shortest_accepted, en decide.h, es la máquina TT con una cola: una búsqueda en anchura desde start. Además de marcar, guarda desde qué estado y con qué símbolo llegó a cada uno, y con eso devuelve una cadena aceptada de longitud mínima, o std::nullopt si no hay ninguna. is_empty solo mira cuál de las dos cosas pasó.

¿Dos DFA son equivalentes?: EQ_DFA

EQDFA={ ⟨A,B⟩:A y B son DFA y L(A)=L(B) }\mathrm{EQ}_{\mathrm{DFA}} = \{\, \langle A, B \rangle : A \text{ y } B \text{ son DFA y } L(A) = L(B) \,\}

Esta pregunta parece más difícil que las anteriores. Dos autómatas pueden tener distinta cantidad de estados y diagramas que no se parecen, y reconocer lo mismo. Comparar los diagramas no sirve, y comparar las respuestas cadena por cadena tampoco, por la misma razón que en EDFAE_{\mathrm{DFA}}: son infinitas.

La idea es convertir la pregunta en una que ya resolvimos. Dos lenguajes son iguales cuando ninguna cadena está en uno y no en el otro. El conjunto de las cadenas que están en exactamente uno de los dos se llama la diferencia simétrica:

L(A) △ L(B)=(L(A)∩L(B)‾)∪(L(A)‾∩L(B))L(A) \,\triangle\, L(B) = \bigl(L(A) \cap \overline{L(B)}\bigr) \cup \bigl(\overline{L(A)} \cap L(B)\bigr)

La raya de arriba es el complemento. Entonces

L(A)=L(B)si y solo siL(A) △ L(B)=∅L(A) = L(B) \quad\text{si y solo si}\quad L(A) \,\triangle\, L(B) = \emptyset

y preguntar si un lenguaje es vacío es EDFAE_{\mathrm{DFA}}, siempre que tengamos un DFA para ese lenguaje. Lo tenemos: los lenguajes regulares son cerrados bajo complemento, intersección y unión, y las tres demostraciones de la semana 1 son construcciones.

El autómata de la diferencia simétrica

No hace falta encadenar tres construcciones. Sale de una sola vez con la construcción del producto, eligiendo bien los estados de aceptación. Sean A=(QA,Σ,δA,qA,FA)A = (Q_A, \Sigma, \delta_A, q_A, F_A) y B=(QB,Σ,δB,qB,FB)B = (Q_B, \Sigma, \delta_B, q_B, F_B), con el mismo alfabeto. Definimos C=(QA×QB,Σ,δC,(qA,qB),FC)C = (Q_A \times Q_B, \Sigma, \delta_C, (q_A, q_B), F_C) con

δC((p,q),a)=(δA(p,a),δB(q,a))FC={ (p,q):exactamente uno de p∈FA, q∈FB es cierto }\begin{aligned} \delta_C((p, q), a) &= (\delta_A(p, a), \delta_B(q, a)) \\ F_C &= \{\, (p, q) : \text{exactamente uno de } p \in F_A,\ q \in F_B \text{ es cierto} \,\} \end{aligned}

CC corre AA y BB a la vez, y acepta cuando no coinciden.

Lema. L(C)=L(A) △ L(B)L(C) = L(A) \,\triangle\, L(B).

Demostración. En la semana 1 demostramos, por inducción sobre ∣w∣|w|, que el producto avanza en los dos autómatas a la vez: δC∗((p,q),w)=(δA∗(p,w),δB∗(q,w))\delta_C^*((p, q), w) = (\delta_A^*(p, w), \delta_B^*(q, w)). Con eso:

w∈L(C)  ⟺  δC∗((qA,qB),w)∈FC  ⟺  (δA∗(qA,w),δB∗(qB,w))∈FClema del producto  ⟺  exactamente uno de δA∗(qA,w)∈FA, δB∗(qB,w)∈FBdefinicioˊn de FC  ⟺  exactamente uno de w∈L(A), w∈L(B)  ⟺  w∈L(A) △ L(B)\begin{aligned} w \in L(C) &\iff \delta_C^*((q_A, q_B), w) \in F_C \\ &\iff (\delta_A^*(q_A, w), \delta_B^*(q_B, w)) \in F_C && \text{lema del producto} \\ &\iff \text{exactamente uno de } \delta_A^*(q_A, w) \in F_A,\ \delta_B^*(q_B, w) \in F_B && \text{definición de } F_C \\ &\iff \text{exactamente uno de } w \in L(A),\ w \in L(B) \\ &\iff w \in L(A) \,\triangle\, L(B) \end{aligned}

∎

Teorema. EQDFA\mathrm{EQ}_{\mathrm{DFA}} es decidible.

Demostración. Por construcción, con la máquina TT de EDFAE_{\mathrm{DFA}} como subrutina.

F = "Con la entrada ⟨A, B⟩, donde A y B son DFA con el mismo alfabeto:
  1. Construir el DFA C de la diferencia simétrica, con la construcción del producto.
  2. Correr T con la entrada ⟨C⟩.
  3. Si T acepta, aceptar. Si T rechaza, rechazar."

Termina siempre. CC tiene ∣QA∣⋅∣QB∣|Q_A| \cdot |Q_B| estados y una transición por cada estado y cada símbolo: construirlo es llenar una tabla finita. El paso 2 termina porque TT decide.

Responde bien. TT acepta ⟨C⟩\langle C \rangle si y solo si L(C)=∅L(C) = \emptyset. Por el lema, eso pasa si y solo si L(A) △ L(B)=∅L(A) \,\triangle\, L(B) = \emptyset, es decir, si y solo si L(A)=L(B)L(A) = L(B). ∎

Para verlo funcionar usamos dos autómatas para “termina en 01\mathtt{01}”. Uno es el de 3 estados de la semana 1. El otro, machines/ends_01_history.dfa, es el que escribe quien no busca ahorrar: recuerda los dos últimos símbolos leídos, con un estado ee para “todavía nada”, s0s_0 y s1s_1 para “un solo símbolo”, y s00s_{00}, s01s_{01}, s10s_{10}, s11s_{11} para los dos últimos. Son 7 estados, y acepta en s01s_{01}.

$ build/eq_dfa machines/ends_01.dfa machines/ends_01_history.dfa --producto
A = machines/ends_01.dfa, 3 estados
B = machines/ends_01_history.dfa, 7 estados
C, el producto completo: 21 estados, 8 de aceptación, 7 alcanzables
L(C) = ∅
equivalentes: L(A) = L(B), ⟨A, B⟩ ∈ EQ_DFA

CC tiene 3⋅7=213 \cdot 7 = 21 estados, y 8 de ellos son de aceptación: los pares en los que uno acepta y el otro no. La cuenta sale a mano. q2q_2 es el único estado de aceptación de AA y s01s_{01} el único de BB. Los pares en los que solo acepta AA son los (q2,s)(q_2, s) con ss distinto de s01s_{01}, que son 6. Los pares en los que solo acepta BB son (q0,s01)(q_0, s_{01}) y (q1,s01)(q_1, s_{01}), que son 2. Ninguno de los 8 es alcanzable, así que L(C)=∅L(C) = \emptyset y los autómatas son equivalentes.

Ahora un autómata equivocado. machines/ends_01_wrong.dfa es el de 3 estados con una sola transición cambiada: desde q2q_2, con 0\mathtt{0}, vuelve a q0q_0 en lugar de ir a q1q_1. Es un error razonable (“ya acepté, empiezo de nuevo”), y probando cadenas cortas no se nota.

$ build/eq_dfa machines/ends_01.dfa machines/ends_01_wrong.dfa --producto
A = machines/ends_01.dfa, 3 estados
B = machines/ends_01_wrong.dfa, 3 estados
C, el producto completo: 9 estados, 4 de aceptación, 5 alcanzables
L(C) ≠ ∅
distintos: ⟨A, B⟩ ∉ EQ_DFA
una cadena más corta que los separa: 0101 (4 símbolos); A la acepta y B la rechaza

Los dos autómatas responden igual con las 15 cadenas de longitud a lo sumo 3. La primera diferencia aparece en 0101\mathtt{0101}: después de 010\mathtt{010}, el correcto recuerda que lo último fue un 0\mathtt{0} y el equivocado lo olvidó.

Idea clave. Para decidir EQDFA\mathrm{EQ}_{\mathrm{DFA}} se construye un autómata que acepta justo las cadenas en las que los dos no coinciden, y se pregunta si su lenguaje es vacío. Una pregunta sobre dos autómatas se convirtió en una pregunta, ya resuelta, sobre uno. Convertir un problema en otro es la técnica de toda la semana 10.

Sin construir el producto

La máquina FF es una demostración correcta y un programa malo. Construye los ∣QA∣⋅∣QB∣|Q_A| \cdot |Q_B| estados de CC y después TT visita solo los alcanzables, que en los dos ejemplos de arriba eran 7 de 21 y 5 de 9. Con dos autómatas de 50 000 estados, CC tendría 2 500 000 000 de estados.

No hace falta construir lo que no se va a visitar. La máquina TT parte del estado inicial de CC y sigue transiciones, y las transiciones de CC se pueden calcular en el momento: para saber a dónde va (p,q)(p, q) con aa basta mirar δA(p,a)\delta_A(p, a) y δB(q,a)\delta_B(q, a). Juntando los dos pasos de FF en uno:

algoritmo equivalentes(A, B)
    cola ← [(qA, qB)]
    marcar (qA, qB)
    mientras la cola no esté vacía
        (p, q) ← sacar el primero de la cola
        si exactamente uno de p ∈ FA, q ∈ FB es cierto entonces
            devolver distintos, con la cadena que llevó a (p, q)
        fin si
        para cada símbolo a de Σ
            (p', q') ← (δA(p, a), δB(q, a))
            si (p', q') no está marcado entonces
                marcar (p', q'), anotar que se llegó desde (p, q) con a
                agregar (p', q') al final de la cola
            fin si
        fin para
    fin mientras
    devolver equivalentes
fin algoritmo

Es la búsqueda en anchura de Algoritmos sobre un grafo que nunca se escribe completo. Termina porque cada par se marca una sola vez y hay a lo sumo ∣QA∣⋅∣QB∣|Q_A| \cdot |Q_B| pares. Responde lo mismo que FF porque visita exactamente los estados alcanzables de CC. eq_dfa sin opciones hace esto, y con --pares muestra los pares en el orden en que salen de la cola:

$ build/eq_dfa machines/ends_01.dfa machines/ends_01_history.dfa --pares
A = machines/ends_01.dfa, 3 estados
B = machines/ends_01_history.dfa, 7 estados
pares visitados: 7 de 21
  (q0,e)
  (q1,s0)
  (q0,s1)
  (q1,s00)
  (q2,s01)
  (q1,s10)
  (q0,s11)
equivalentes: L(A) = L(B), ⟨A, B⟩ ∈ EQ_DFA

La lista dice más que “equivalentes”: dice por qué. Cada estado del autómata de 7 aparece con un solo estado del de 3, el que significa lo mismo. Por ejemplo s00s_{00} y s10s_{10} van los dos con q1q_1: “lo último fue un 0\mathtt{0}”. Es la fusión de estados que haría la minimización de la semana 4.

Con el autómata equivocado, la búsqueda se detiene en el primer par que separa:

$ build/eq_dfa machines/ends_01.dfa machines/ends_01_wrong.dfa --pares
A = machines/ends_01.dfa, 3 estados
B = machines/ends_01_wrong.dfa, 3 estados
pares visitados: 5 de 9
  (q0,q0)
  (q1,q1)
  (q2,q2)
  (q1,q0)
  (q2,q0)  <- uno acepta y el otro no
distintos: ⟨A, B⟩ ∉ EQ_DFA
una cadena más corta que los separa: 0101 (4 símbolos); A la acepta y B la rechaza

Los tres primeros pares son “los dos van juntos”. En el cuarto se separan: AA está en q1q_1 y BB en q0q_0. Un símbolo después, AA acepta y BB no.

Animación de la búsqueda en anchura sobre los pares de ends_01.dfa, que es A, y ends_01_wrong.dfa, que es B. Arriba están los dos diagramas de tres estados, q₀, q₁ y q₂, con q₂ de aceptación; se diferencian en que en B, desde q₂ y con 0, se vuelve a q₀ y no a q₁. Abajo se van dibujando los pares en el orden en que salen de la cola, y en cada paso se resaltan el par actual y el estado de cada autómata. Al empezar se marca el par inicial (q₀, q₀) y entra a la cola. Sale (q₀, q₀): ninguno acepta; con 0 va a (q₁, q₁), que es nuevo, y con 1 vuelve a (q₀, q₀), ya marcado. Sale (q₁, q₁): ninguno acepta; con 0 se queda en (q₁, q₁) y con 1 va a (q₂, q₂), nuevo. Sale (q₂, q₂): los dos aceptan; con 0 va a (q₁, q₀), nuevo, y con 1 a (q₀, q₀), ya marcado. Sale (q₁, q₀): ninguno acepta; con 0 va a (q₁, q₁), ya marcado, y con 1 a (q₂, q₀), nuevo. Sale (q₂, q₀): A acepta y B no, y la búsqueda termina. Las flechas que llevaron hasta ese par, 0, 1, 0 y 1, quedan resaltadas: son la cadena 0101. Se marcaron 5 pares de 9.Animación de la búsqueda en anchura sobre los pares de ends_01.dfa, que es A, y ends_01_wrong.dfa, que es B. Arriba están los dos diagramas de tres estados, q₀, q₁ y q₂, con q₂ de aceptación; se diferencian en que en B, desde q₂ y con 0, se vuelve a q₀ y no a q₁. Abajo se van dibujando los pares en el orden en que salen de la cola, y en cada paso se resaltan el par actual y el estado de cada autómata. Al empezar se marca el par inicial (q₀, q₀) y entra a la cola. Sale (q₀, q₀): ninguno acepta; con 0 va a (q₁, q₁), que es nuevo, y con 1 vuelve a (q₀, q₀), ya marcado. Sale (q₁, q₁): ninguno acepta; con 0 se queda en (q₁, q₁) y con 1 va a (q₂, q₂), nuevo. Sale (q₂, q₂): los dos aceptan; con 0 va a (q₁, q₀), nuevo, y con 1 a (q₀, q₀), ya marcado. Sale (q₁, q₀): ninguno acepta; con 0 va a (q₁, q₁), ya marcado, y con 1 a (q₂, q₀), nuevo. Sale (q₂, q₀): A acepta y B no, y la búsqueda termina. Las flechas que llevaron hasta ese par, 0, 1, 0 y 1, quedan resaltadas: son la cadena 0101. Se marcaron 5 pares de 9.
La ejecución de eq_dfa con el autómata equivocado. Solo se dibujan los pares a los que se llega, y el camino hasta el primer par en que uno acepta y el otro no es la cadena que los separa.

La cadena es de las más cortas. La búsqueda en anchura saca los pares de la cola por distancia creciente desde el par inicial, y la distancia de un par es la longitud de la cadena más corta que lleva hasta él. El primer par “malo” que sale de la cola es entonces uno de los más cercanos, y la cadena anotada tiene longitud mínima entre todas las que separan a AA de BB.

Y nunca es muy larga. Si AA y BB no son equivalentes, la cadena más corta que los separa tiene longitud menor que ∣QA∣⋅∣QB∣|Q_A| \cdot |Q_B|. La razón es el principio del palomar, como en el lema de bombeo. Sea ww una cadena de longitud mínima en L(C)L(C). Al leerla, CC pasa por ∣w∣+1|w| + 1 estados. Si ∣w∣≥∣QA∣⋅∣QB∣|w| \geq |Q_A| \cdot |Q_B|, dos de esos estados serían el mismo par, y el tramo de ww entre las dos visitas se podría quitar: la cadena que queda llega al mismo par final, sigue en L(C)L(C) y es más corta. Eso contradice que ww era mínima.

Esta cota da un tercer algoritmo, correcto y sin ninguna construcción: probar todas las cadenas de longitud menor que ∣QA∣⋅∣QB∣|Q_A| \cdot |Q_B| y responder “equivalentes” si ninguna separa. Termina, porque son finitas. Pero con el ejemplo de 3 y 7 estados son todas las cadenas binarias de longitud hasta 20, más de dos millones, para confirmar algo que la búsqueda vio con 7 pares.

En la práctica. Comparar dos autómatas es lo que hace una herramienta que verifica circuitos: el circuito que salió de una optimización debe comportarse igual que el original con todas las secuencias de entradas, y cuando no, la herramienta entrega la secuencia más corta que lo muestra. También lo hace quien prueba que dos expresiones regulares son la misma: se convierten a DFA y se comparan. En los dos casos se recorren solo los pares alcanzables.

En C++. symmetric_difference, en decide.h, construye CC completo y es la demostración. compare es el algoritmo de esta sección: una cola de pares, un std::set de pares marcados y un std::map que anota de dónde vino cada uno. Las pruebas comprueban que las dos maneras dan siempre la misma respuesta y cadenas de la misma longitud, con 400 pares de autómatas al azar.

Gramáticas: A_CFG y E_CFG

Las mismas preguntas, un modelo más arriba.

ACFG={ ⟨G,w⟩:G es una gramaˊtica libre de contexto que genera w }A_{\mathrm{CFG}} = \{\, \langle G, w \rangle : G \text{ es una gramática libre de contexto que genera } w \,\}

A_CFG: cuándo dejar de buscar

Con los autómatas, “¿acepta ww?” era simular. Una gramática no se simula: genera. Para saber si GG genera ww hay que buscar una derivación S⇒∗wS \Rightarrow^* w, y el primer intento es buscarlas todas.

"Con la entrada ⟨G, w⟩:
  1. Listar las derivaciones de G: primero las de 1 paso, después las de 2, y así.
  2. Si alguna termina en w, aceptar."

Si GG genera ww, alguna derivación la produce, tiene una cantidad finita de pasos, y este procedimiento la encuentra. Pero si GG no genera ww, nunca se entera: una gramática con una regla como S→SSS \to SS tiene derivaciones de cualquier longitud, y siempre queda una más larga por probar. Otra vez un procedimiento que reconoce y no decide.

Lo que falta es una cota: un número de pasos a partir del cual se sabe que ya no vale la pena seguir. Una gramática cualquiera no la da, porque las reglas A→εA \to \varepsilon y A→BA \to B permiten dar pasos sin avanzar. La forma normal de Chomsky de la semana 5 sí: es el teorema de la longitud de las derivaciones que vimos allí, y lo repetimos porque aquí es la pieza que hace terminar a la máquina.

Lema. Si GG está en forma normal de Chomsky y ww es una cadena de longitud n≥1n \geq 1, toda derivación de ww en GG tiene exactamente 2n−12n - 1 pasos.

Demostración. En forma normal de Chomsky, las reglas son A→BCA \to BC, A→aA \to a y, solo para la variable inicial, S→εS \to \varepsilon; además SS no aparece a la derecha de ninguna regla. Una derivación de ww con n≥1n \geq 1 no usa S→εS \to \varepsilon: esa regla solo se podría aplicar a la SS del principio, y daría ε\varepsilon. Quedan dos tipos de paso.

  • Un paso con A→BCA \to BC alarga la cadena en un símbolo. La derivación empieza con una cadena de longitud 1, que es SS, y termina con una de longitud nn: hay exactamente n−1n - 1 pasos de este tipo.
  • Un paso con A→aA \to a cambia una variable por un terminal y no cambia la longitud. Al final hay nn terminales y cada uno salió de un paso de este tipo: hay exactamente nn.

En total, (n−1)+n=2n−1(n - 1) + n = 2n - 1. ∎

Teorema. ACFGA_{\mathrm{CFG}} es decidible.

Demostración. Por construcción.

S = "Con la entrada ⟨G, w⟩, donde G es una gramática libre de contexto y w una cadena:
  1. Convertir G en una gramática equivalente G' en forma normal de Chomsky.
  2. Sea n = |w|. Listar todas las derivaciones de G' de 2n − 1 pasos. Si n = 0, las de 1 paso.
  3. Si alguna de ellas genera w, aceptar. Si ninguna, rechazar."

Termina siempre. La conversión del paso 1 es el algoritmo de la semana 5, que aplica cuatro transformaciones finitas. En el paso 2, una derivación de kk pasos se arma eligiendo kk veces una variable de la cadena actual y una regla para ella. Las cadenas intermedias tienen longitud a lo sumo nn (o 1, si n=0n = 0) y las reglas son finitas, así que en cada paso hay una cantidad finita de opciones, y la lista de derivaciones de 2n−12n - 1 pasos es finita.

Responde bien. L(G′)=L(G)L(G') = L(G) por la semana 5. Por el lema, si G′G' genera ww con n≥1n \geq 1, lo hace con una derivación de exactamente 2n−12n - 1 pasos, que está en la lista. Si n=0n = 0, la única derivación posible de ε\varepsilon es S⇒εS \Rightarrow \varepsilon, de 1 paso. Y si ninguna derivación de la lista genera ww, ninguna derivación la genera. ∎

La gramática machines/anbn_chomsky.cfg genera { anbn:n≥0 }\{\, \mathtt{a}^n\mathtt{b}^n : n \geq 0 \,\} y ya está en forma normal de Chomsky:

variables: S0 S T A B
terminals: a b
start: S0
rules:
S0 -> A T | A B | eps
S -> A T | A B
T -> S B
A -> a
B -> b

Por ejemplo, aabb\mathtt{aabb} se deriva en 2⋅4−1=72 \cdot 4 - 1 = 7 pasos:

S0⇒AT⇒aT⇒aSB⇒aABB⇒aaBB⇒aabB⇒aabbS_0 \Rightarrow AT \Rightarrow \mathtt{a}T \Rightarrow \mathtt{a}SB \Rightarrow \mathtt{a}ABB \Rightarrow \mathtt{aa}BB \Rightarrow \mathtt{aab}B \Rightarrow \mathtt{aabb}

Tres de esos pasos usan una regla A→BCA \to BC y cuatro una regla A→aA \to a. El programa a_cfg responde de las dos maneras, con la máquina SS y con CYK, y comprueba que coinciden:

$ build/a_cfg machines/anbn_chomsky.cfg aabb abab '' ab
G = machines/anbn_chomsky.cfg, 8 reglas, en forma normal de Chomsky: sí
w = aabb: n = 4, derivaciones de 7 pasos; G la genera, ⟨G, w⟩ ∈ A_CFG
w = abab: n = 4, derivaciones de 7 pasos; G no la genera, ⟨G, w⟩ ∉ A_CFG
w = ε: n = 0, derivaciones de 1 paso; G la genera, ⟨G, w⟩ ∈ A_CFG
w = ab: n = 2, derivaciones de 3 pasos; G la genera, ⟨G, w⟩ ∈ A_CFG

La máquina SS decide, y es lentísima: la cantidad de derivaciones de 2n−12n - 1 pasos crece exponencialmente con nn. Ustedes ya conocen una mejor. El algoritmo CYK de la semana 5 llena una tabla con las variables que generan cada subcadena de ww, de las más cortas a las más largas, y responde mirando si SS está en la celda de la cadena completa. Hace una cantidad de trabajo del orden de n3⋅∣G∣n^3 \cdot |G| y, sobre todo, termina siempre: es una tabla finita que se llena una vez. Como máquina:

S' = "Con la entrada ⟨G, w⟩, donde G es una gramática libre de contexto y w una cadena:
  1. Convertir G en una gramática equivalente G' en forma normal de Chomsky.
  2. Llenar la tabla de CYK de G' para w.
  3. Si la variable inicial está en la celda de la cadena completa, aceptar. Si no, rechazar."

Las dos máquinas demuestran el mismo teorema. Para la decidibilidad alcanza con SS, cuya corrección sale de un lema de tres líneas. Para un parser, y para la semana 12, donde importará que ACFGA_{\mathrm{CFG}} se decide en tiempo polinomial, hace falta S′S'.

Error común. Decir que ACFGA_{\mathrm{CFG}} es decidible porque “se prueban todas las derivaciones”. Sin una cota en el número de pasos, eso no termina cuando la respuesta es no. La forma normal de Chomsky no está en la demostración por comodidad: es lo que da la cota.

E_CFG: marcar desde abajo

ECFG={ ⟨G⟩:G es una gramaˊtica libre de contexto y L(G)=∅ }E_{\mathrm{CFG}} = \{\, \langle G \rangle : G \text{ es una gramática libre de contexto y } L(G) = \emptyset \,\}

Una gramática puede no generar nada. Pasa cuando toda derivación desde SS se queda para siempre con alguna variable, como en una recursión sin caso base. Este es machines/no_base_case.cfg:

S→ASB∣CAA→a∣aAB→bC→Cb∣Sa\begin{aligned} S &\to ASB \mid CA \\ A &\to \mathtt{a} \mid \mathtt{a}A \\ B &\to \mathtt{b} \\ C &\to C\mathtt{b} \mid S\mathtt{a} \end{aligned}

La idea de EDFAE_{\mathrm{DFA}}, partir del inicio y ver a dónde se llega, aquí no alcanza. Desde SS se “llega” a las cuatro variables, y eso no dice nada: lo que importa no es qué variables aparecen, sino si alguna derivación termina. Hay que mirar desde el otro extremo. Se empieza por las variables que generan una cadena de terminales en un paso, y se sube.

Decimos que una variable AA genera si A⇒∗xA \Rightarrow^* x para alguna cadena xx de terminales.

Teorema. ECFGE_{\mathrm{CFG}} es decidible.

Demostración. Por construcción. La máquina marca los símbolos que generan.

R = "Con la entrada ⟨G⟩, donde G es una gramática libre de contexto:
  1. Marcar todos los terminales de G.
  2. Repetir hasta que no se marque ninguna variable nueva:
  3.     Marcar toda variable A que tenga una regla A → U1 U2 … Uk con todos los símbolos
         U1, …, Uk ya marcados.
  4. Si la variable inicial no quedó marcada, aceptar. Si quedó marcada, rechazar."

Una regla A→εA \to \varepsilon tiene k=0k = 0: no hay ningún símbolo por revisar, así que AA se marca en la primera repetición.

Termina siempre. Cada repetición del paso 3 marca al menos una variable nueva, o es la última. Hay a lo sumo ∣V∣|V| repeticiones que marcan algo.

Responde bien. Hay que ver que, al terminar, una variable está marcada si y solo si genera. En la semana 5 llamamos productivas a las variables que generan alguna cadena de terminales: son las que quedan marcadas.

  • Toda variable marcada genera. Por inducción sobre el orden en que se marcan. Si AA se marca por la regla A→U1⋯UkA \to U_1 \cdots U_k, cada UiU_i es un terminal, y entonces ponemos xi=Uix_i = U_i, o es una variable marcada antes, que por hipótesis genera alguna cadena de terminales xix_i. Entonces A⇒U1⋯Uk⇒∗x1⋯xkA \Rightarrow U_1 \cdots U_k \Rightarrow^* x_1 \cdots x_k.
  • Toda variable que genera queda marcada. Por inducción sobre el número de pasos de una derivación A⇒∗xA \Rightarrow^* x, con xx de terminales. El primer paso usa una regla A→U1⋯UkA \to U_1 \cdots U_k, y después cada UiU_i que es una variable deriva un trozo de xx con menos pasos que la derivación completa. Por hipótesis, esas variables quedan marcadas. Los UiU_i que son terminales se marcaron en el paso 1. Entonces todos los símbolos de la regla están marcados al terminar, y AA también: si no, el paso 3 tendría todavía algo que marcar. (Si la derivación tiene un solo paso, todos los UiU_i son terminales, o k=0k = 0, y es el mismo argumento sin usar la hipótesis.)

Por último, L(G)≠∅L(G) \neq \emptyset si y solo si SS genera, si y solo si SS quedó marcada. ∎

$ build/e_cfg machines/no_base_case.cfg
G = machines/no_base_case.cfg, 4 variables, 7 reglas, inicial S
ronda 1:  se marca A por A → a;  se marca B por B → b;
ronda 2:  no se marca nada, termina
marcadas: 2 de 4
S no está marcada: L(G) = ∅, ⟨G⟩ ∈ E_CFG

AA y BB generan. SS necesita que genere SS misma (en ASBASB) o CC (en CACA), y CC necesita a CC o a SS: ninguna de las dos tiene por dónde empezar. Con la gramática de {anbn}\{\mathtt{a}^n\mathtt{b}^n\} todas quedan marcadas, en tres rondas:

$ build/e_cfg machines/anbn_chomsky.cfg
G = machines/anbn_chomsky.cfg, 5 variables, 8 reglas, inicial S0
ronda 1:  se marca S0 por S0 → ε;  se marca A por A → a;  se marca B por B → b;
ronda 2:  se marca S por S → A B;
ronda 3:  se marca T por T → S B;
ronda 4:  no se marca nada, termina
marcadas: 5 de 5
S0 está marcada: L(G) ≠ ∅, ⟨G⟩ ∉ E_CFG

Idea clave. EDFAE_{\mathrm{DFA}} y ECFGE_{\mathrm{CFG}} se deciden marcando, y en los dos casos el algoritmo termina porque marca cosas de un conjunto finito y nunca desmarca. La diferencia es el sentido: en un DFA se marca desde el estado inicial hacia adelante, y en una gramática desde los terminales hacia arriba.

En la práctica. El algoritmo de marcas es el que usa un generador de parsers para avisar que una regla de la gramática es inútil, y es la misma idea con la que un compilador detecta código al que nunca se llega o un make decide qué objetivos se pueden construir: un punto fijo sobre un conjunto finito.

Por qué EQ_CFG no sale igual

Falta la tercera pregunta: ¿dos gramáticas generan el mismo lenguaje?

EQCFG={ ⟨G,H⟩:G y H son gramaˊticas libres de contexto y L(G)=L(H) }\mathrm{EQ}_{\mathrm{CFG}} = \{\, \langle G, H \rangle : G \text{ y } H \text{ son gramáticas libres de contexto y } L(G) = L(H) \,\}

Tenemos ECFGE_{\mathrm{CFG}}, así que lo natural es repetir la demostración de EQDFA\mathrm{EQ}_{\mathrm{DFA}}: construir una gramática para la diferencia simétrica L(G) △ L(H)L(G) \,\triangle\, L(H) y preguntar si es vacía.

El intento falla en el primer paso. La diferencia simétrica se arma con complementos e intersecciones, y en la semana 6 vimos que los lenguajes libres de contexto no son cerrados bajo complemento ni bajo intersección. El lenguaje L(G) △ L(H)L(G) \,\triangle\, L(H) puede no ser libre de contexto: puede no existir ninguna gramática que lo genere, y entonces no hay nada que darle a la máquina RR.

Hay que leer bien qué se concluye de esto. Que una demostración no se pueda copiar no demuestra que el lenguaje sea indecidible: podría haber otro algoritmo, con otra idea. En este caso no lo hay. EQCFG\mathrm{EQ}_{\mathrm{CFG}} es indecidible, y demostrarlo pide las herramientas de la semana 10. Queda como deuda.

Es el primer aviso de que el terreno cambia al subir de modelo. Con autómatas finitos, todas las preguntas de esta sesión son decidibles. Con gramáticas, dos de tres. Con máquinas de Turing, en la sesión B, ninguna.

Todo lenguaje libre de contexto es decidible

Los teoremas anteriores hablan de lenguajes de descripciones, como ACFGA_{\mathrm{CFG}}. De ellos sale un resultado sobre los lenguajes libres de contexto mismos, que ubica a las partes 1 y 2 del curso dentro de la parte 3.

Teorema. Todo lenguaje libre de contexto es decidible.

Demostración. Por construcción. Sea LL un lenguaje libre de contexto. Por definición existe una gramática GG con L(G)=LL(G) = L. Esa gramática queda fija y se escribe dentro de la máquina:

M_G = "Con la entrada w:
  1. Correr S con la entrada ⟨G, w⟩.
  2. Si S acepta, aceptar. Si S rechaza, rechazar."

SS es la máquina que decide ACFGA_{\mathrm{CFG}}. Termina siempre, así que MGM_G también, y MGM_G acepta ww si y solo si GG genera ww, es decir, si y solo si w∈Lw \in L. ∎

Vale la pena notar la diferencia entre SS y MGM_G. La máquina SS recibe la gramática como parte de la entrada: es un programa que sirve para todas. La máquina MGM_G recibe solo ww, y hay una distinta para cada gramática: es SS con el primer argumento ya puesto. La técnica de fijar una parte de la entrada dentro de la máquina vuelve en la semana 10.

Uno podría haber intentado otra demostración: todo lenguaje libre de contexto tiene un autómata de pila, y una máquina de Turing puede simular una pila. El problema es que el autómata de pila es no determinista y puede tener caminos que nunca terminan, apilando símbolos con transiciones ε\varepsilon sin leer la entrada. Una simulación directa podría quedarse en uno de esos caminos. Se puede arreglar, pero la gramática en forma normal de Chomsky ya resuelve el problema de la terminación.

Como todo lenguaje regular es libre de contexto (semana 5), también todo lenguaje regular es decidible. Y todo lenguaje decidible es reconocible, porque una máquina que decide en particular reconoce. El mapa del curso hasta hoy:

regulares⊂libres de contexto⊂decidibles⊂reconocibles\text{regulares} \subset \text{libres de contexto} \subset \text{decidibles} \subset \text{reconocibles}
Cinco recuadros, uno dentro de otro. El de afuera, punteado, es el de todos los lenguajes sobre Σ, con la nota de que fuera de los reconocibles también hay lenguajes, los que ninguna máquina reconoce. Dentro están los reconocibles: los acepta una máquina de Turing, que puede no detenerse; su testigo es A_TM, que no es decidible y se ve en la sesión B. Dentro, los decidibles: una máquina de Turing que se detiene siempre; su testigo es aⁿbⁿcⁿ, que no es libre de contexto, de las semanas 6 y 7. Dentro, los libres de contexto: una gramática o un autómata de pila; su testigo es 0ⁿ1ⁿ, que no es regular, de las semanas 4 y 5. En el centro, los regulares: un autómata finito; su ejemplo es el lenguaje de las cadenas que terminan en 01.Cinco recuadros, uno dentro de otro. El de afuera, punteado, es el de todos los lenguajes sobre Σ, con la nota de que fuera de los reconocibles también hay lenguajes, los que ninguna máquina reconoce. Dentro están los reconocibles: los acepta una máquina de Turing, que puede no detenerse; su testigo es A_TM, que no es decidible y se ve en la sesión B. Dentro, los decidibles: una máquina de Turing que se detiene siempre; su testigo es aⁿbⁿcⁿ, que no es libre de contexto, de las semanas 6 y 7. Dentro, los libres de contexto: una gramática o un autómata de pila; su testigo es 0ⁿ1ⁿ, que no es regular, de las semanas 4 y 5. En el centro, los regulares: un autómata finito; su ejemplo es el lenguaje de las cadenas que terminan en 01.
El mapa del curso hasta hoy. Cada clase contiene a la de adentro, y el lenguaje de su derecha está en ella y no en la de adentro.

Las tres inclusiones son estrictas, y cada una tiene su testigo:

Está en… …y no en… Lenguaje Dónde se demostró
Libres de contexto Regulares { 0n1n:n≥0 }\{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\} Semanas 4 y 5
Decidibles Libres de contexto { anbncn:n≥0 }\{\, \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n : n \geq 0 \,\} Semanas 6 y 7
Reconocibles Decidibles ATMA_{\mathrm{TM}} Hoy, en la sesión B

La última fila es lo que falta. Y fuera de los reconocibles también hay lenguajes: los que ninguna máquina reconoce. Hoy aparece el primero.

Error común. “Decidir” simulando una máquina que podría no detenerse. Todas las máquinas de esta sesión tienen pasos como “simular BB con ww” o “correr TT con ⟨C⟩\langle C \rangle”. Son legítimos porque lo simulado siempre termina: un DFA da un paso por símbolo, y TT es una máquina que decide. Si el paso fuera “simular la máquina de Turing MM con ww”, nada garantizaría que termine, y la máquina que lo contiene ya no decidiría. Antes de escribir “simular” o “correr” en un algoritmo de decisión, pregúntense: ¿quién me asegura que esto se detiene?

La máquina universal

La sesión A terminó con una advertencia. Ahora hacemos la pregunta que la provoca. Es la misma de ADFAA_{\mathrm{DFA}}, un modelo más arriba:

ATM={ ⟨M,w⟩:M es una maˊquina de Turing que acepta w }A_{\mathrm{TM}} = \{\, \langle M, w \rangle : M \text{ es una máquina de Turing que acepta } w \,\}

Copiemos la máquina que decidía ADFAA_{\mathrm{DFA}}, cambiando el modelo.

U = "Con la entrada ⟨M, w⟩, donde M es una máquina de Turing y w una cadena:
  1. Simular M con la entrada w.
  2. Si M entra en su estado de aceptación, aceptar. Si entra en su estado de rechazo, rechazar."

Antes de preguntar qué hace UU, hay que ver que existe: que “simular MM con ww” es un paso que una máquina de Turing puede dar, para cualquier MM que le llegue.

Lo es, y ustedes ya lo programaron en el laboratorio de la semana 7. Simular es mantener una configuración de MM (su estado, su cinta y la posición del cabezal) y repetir un paso mecánico: mirar el estado y el símbolo bajo el cabezal, buscar ese par en la tabla δ\delta que viene escrita en ⟨M⟩\langle M \rangle, y aplicar lo que dice. Como máquina de Turing, UU se describe cómodamente con tres cintas: una guarda ⟨M⟩\langle M \rangle y no cambia, otra guarda la cinta de MM, y la tercera el estado actual de MM. Cada paso de MM le cuesta a UU recorrer la primera cinta buscando la transición. Y una máquina de tres cintas se convierte en una de una cinta, por la semana 7.

Lo notable es que UU es una sola máquina, con una tabla fija, que hace el trabajo de todas las demás. No hay que construir una máquina para cada problema: basta una, y los problemas se le dan como datos. Se llama máquina de Turing universal (universal Turing machine), y Turing la describió en 1936, en el mismo artículo en que definió sus máquinas. Poco más de diez años después se construyeron las primeras computadoras con el programa guardado en la memoria, junto a los datos.

En la práctica. Un intérprete es una máquina universal. El intérprete de Python es un programa fijo que recibe otro programa como texto y hace lo que ese texto dice. El que construyeron al final de Introducción a la Programación también: un programa que recibe programas. Lo mismo vale para un emulador de consola, para la máquina virtual de Java, y para el procesador de su laptop, que es un circuito fijo que ejecuta cualquier programa que le pongan en memoria. Hoy parece obvio que un programa pueda ser la entrada de otro programa. Es exactamente la idea de UU.

El programa universal es UU escrita en C++. Recibe un archivo .tm, que es un ⟨M⟩\langle M \rangle, y una cadena. No tiene nada escrito sobre ninguna máquina en particular. Con el decididor de { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\} de la semana 7:

$ build/universal machines/zeros_ones.tm 0011 --traza
⟨M⟩ = machines/zeros_ones.tm: 6 estados, 11 transiciones, 296 caracteres
w = 0011
   q0 0011
  X q1 011
  X0 q1 11
  X q2 0Y1
   q2 X0Y1
  X q0 0Y1
  XX q1 Y1
  XXY q1 1
  XX q2 YY
  X q2 XYY
  XX q0 YY
  XXY q3 Y
  XXYY q3 _
  XXYY_ q_accept _
M acepta w después de 13 pasos

Cada línea es una configuración u q vu\,q\,v de MM, como en la semana 7. La primera línea de la salida dice cuánto mide la descripción: esta máquina, escrita en el formato del curso, es una cadena de 296 caracteres.

$ build/universal machines/zeros_ones.tm 0010
⟨M⟩ = machines/zeros_ones.tm: 6 estados, 11 transiciones, 296 caracteres
w = 0010
M rechaza w después de 9 pasos

En C++. En tm.h, la máquina es un struct Tm con los siete componentes de la definición, y la función step aplica δ\delta una vez a una configuración. Todo el simulador es llamar a step en un ciclo. Que la máquina sea un valor que se pasa como argumento, igual que la cadena, es el contenido de esta sección.

A_TM es reconocible

Teorema. ATMA_{\mathrm{TM}} es reconocible.

Demostración. Por construcción: la máquina UU lo reconoce. Hay que ver que UU acepta exactamente las cadenas de ATMA_{\mathrm{TM}}.

  • Si ⟨M,w⟩∈ATM\langle M, w \rangle \in A_{\mathrm{TM}}, entonces MM acepta ww, y lo hace después de una cantidad finita de pasos, digamos tt. La simulación de UU llega al paso tt, ve a MM en su estado de aceptación, y UU acepta.
  • Si ⟨M,w⟩∉ATM\langle M, w \rangle \notin A_{\mathrm{TM}}, entonces MM rechaza ww o no se detiene. Si la rechaza, UU lo ve y rechaza. Si MM no se detiene, la simulación tampoco, y UU no se detiene: en particular, no acepta.

En los dos casos UU acepta ⟨M,w⟩\langle M, w \rangle si y solo si MM acepta ww. ∎

La demostración dice “reconocible” y no “decidible”, y la razón está en la última línea del segundo caso: hay entradas con las que UU no se detiene.

Diagrama de la máquina universal. A la izquierda, la entrada ⟨M, w⟩: una máquina y una cadena. En el centro, un recuadro con U por dentro: la cinta 1 guarda ⟨M⟩, la tabla δ, y no cambia; la cinta 2 guarda la cinta de M; la cinta 3, el estado de M. U repite un paso de M: busca en la cinta 1 la transición del estado y el símbolo, y la aplica. Del recuadro salen tres flechas. Si M acepta w, U acepta. Si M rechaza w, U rechaza. Si M no se detiene, U no se detiene: esa flecha y su recuadro están punteados. Debajo, dos frases: si M acepta o rechaza, lo hace después de una cantidad finita de pasos, y U lo ve y responde lo mismo; si M no se detiene, la simulación tampoco, así que U acepta exactamente A_TM, lo reconoce y no lo decide.Diagrama de la máquina universal. A la izquierda, la entrada ⟨M, w⟩: una máquina y una cadena. En el centro, un recuadro con U por dentro: la cinta 1 guarda ⟨M⟩, la tabla δ, y no cambia; la cinta 2 guarda la cinta de M; la cinta 3, el estado de M. U repite un paso de M: busca en la cinta 1 la transición del estado y el símbolo, y la aplica. Del recuadro salen tres flechas. Si M acepta w, U acepta. Si M rechaza w, U rechaza. Si M no se detiene, U no se detiene: esa flecha y su recuadro están punteados. Debajo, dos frases: si M acepta o rechaza, lo hace después de una cantidad finita de pasos, y U lo ve y responde lo mismo; si M no se detiene, la simulación tampoco, así que U acepta exactamente A_TM, lo reconoce y no lo decide.
U termina de tres maneras, como la máquina que simula. Las dos primeras son respuestas; la tercera es la que impide que U decida.

Por qué simular no decide

Para ver el problema de cerca usamos dos máquinas para el mismo lenguaje, el de las cadenas binarias que contienen algún 1\mathtt{1}. La primera, machines/has_one.tm, avanza a la derecha hasta ver un 1\mathtt{1} o el primer blanco:

Estado Lee 0\mathtt{0} Lee 1\mathtt{1} Lee ⊔\sqcup
scan\mathit{scan} scan\mathit{scan}, 0\mathtt{0}, R\mathrm{R} qacceptq_{\text{accept}}, 1\mathtt{1}, R\mathrm{R} qrejectq_{\text{reject}}, ⊔\sqcup, R\mathrm{R}

La segunda, machines/search_one.tm, tiene una sola casilla distinta: al leer un blanco no rechaza, sigue buscando.

Estado Lee 0\mathtt{0} Lee 1\mathtt{1} Lee ⊔\sqcup
scan\mathit{scan} scan\mathit{scan}, 0\mathtt{0}, R\mathrm{R} qacceptq_{\text{accept}}, 1\mathtt{1}, R\mathrm{R} scan\mathit{scan}, ⊔\sqcup, R\mathrm{R}

Las dos aceptan exactamente las cadenas que tienen un 1\mathtt{1}: reconocen el mismo lenguaje. La primera además lo decide. La segunda no: con una cadena sin ningún 1\mathtt{1} se va hacia la derecha por los blancos, para siempre.

$ build/universal machines/has_one.tm 000
⟨M⟩ = machines/has_one.tm: 3 estados, 3 transiciones, 175 caracteres
w = 000
M rechaza w después de 4 pasos
$ build/universal machines/search_one.tm 0001
⟨M⟩ = machines/search_one.tm: 3 estados, 3 transiciones, 171 caracteres
w = 0001
M acepta w después de 4 pasos
$ build/universal machines/search_one.tm 000 8 --traza
⟨M⟩ = machines/search_one.tm: 3 estados, 3 transiciones, 171 caracteres
w = 000
   scan 000
  0 scan 00
  00 scan 0
  000 scan _
  000_ scan _
  000__ scan _
  000___ scan _
  000____ scan _
  000_____ scan _
M no se detuvo en 8 pasos

El tercer argumento de universal es un límite de pasos. Tiene que estar: un programa que simulara sin límite a search_one.tm con 000\mathtt{000} no devolvería nunca el control a la terminal. Con el límite, el programa tiene tres respuestas posibles, y la tercera es de otra clase que las otras dos.

  • M acepta w es un hecho sobre MM y ww. Es definitivo.
  • M rechaza w también.
  • M no se detuvo en N pasos es un hecho sobre MM, ww y NN. No dice qué pasa con más pasos.

Dos arreglos que no funcionan

Subir el límite. Con NN más grande, ¿no se sabría?

$ build/universal machines/search_one.tm 000 100
M no se detuvo en 100 pasos
$ build/universal machines/search_one.tm 000 10000
M no se detuvo en 10000 pasos
$ build/universal machines/search_one.tm 000 1000000
M no se detuvo en 1000000 pasos

(Se omiten las dos primeras líneas de cada salida, que son iguales a las de arriba.) Un millón de pasos sin detenerse sugiere que no se detiene, y no lo demuestra. La misma respuesta la da una máquina que sí termina, si el límite es corto:

$ build/universal machines/zeros_ones.tm 0011 5
⟨M⟩ = machines/zeros_ones.tm: 6 estados, 11 transiciones, 296 caracteres
w = 0011
M no se detuvo en 5 pasos

Esa máquina acepta 0011\mathtt{0011} en 13 pasos. Para cualquier límite NN que uno fije hay máquinas que se detienen justo después: por ejemplo, la que avanza N+1N + 1 celdas y acepta. Un simulador que responda “rechaza” al llegar al límite se equivoca con ellas. Y un límite que dependa de la entrada, como ∣w∣2|w|^2 o 2∣w∣2^{|w|}, tiene el mismo defecto: siempre hay una máquina que tarda más.

Detectar que se repite. Un programa en un ciclo infinito “hace siempre lo mismo”. Si la simulación ve dos veces la misma configuración, con el mismo estado, la misma cinta y el mismo cabezal, entonces MM va a repetir ese tramo para siempre, y se puede responder que no se detiene. Esa parte es correcta. Lo que falla es lo contrario: una máquina puede no detenerse sin repetir nunca una configuración. Miren la traza de arriba. El cabezal de search_one.tm está cada vez en una celda distinta, así que no hay dos configuraciones iguales, y aun así la máquina no para. Con una cinta infinita, hay infinitas configuraciones por las que pasear.

Esto último es justo lo que separa a la máquina de Turing de los modelos anteriores. Un DFA con una entrada ww solo tiene ∣w∣+1|w| + 1 momentos distintos. Por eso todo lo de la sesión A terminaba.

En search_one.tm nosotros sí sabemos que no se detiene con 000\mathtt{000}: leímos su tabla y lo demostramos. Después de tt pasos está en el estado scan\mathit{scan} con el cabezal en la celda tt, y desde la celda 3 solo hay blancos, con los que sigue en scan\mathit{scan}. La pregunta de esta sesión no es si a veces se puede saber. Es si existe un método único que lo resuelva para toda máquina y toda entrada.

Idea clave. Simular es la única manera general de averiguar qué hace una máquina, y simular solo da respuesta cuando la máquina se detiene. Por eso UU reconoce ATMA_{\mathrm{TM}} y no lo decide. Para decidir haría falta saber que MM no va a detenerse sin esperarla, y veremos que eso no se puede hacer en general.

Los dos arreglos fallaron. Podría haber un tercero más ingenioso: no simular, y analizar el texto de ⟨M⟩\langle M \rangle de alguna manera inteligente. Para descartar todos los intentos a la vez no sirve seguir probando ideas. Hace falta una demostración de imposibilidad, y la herramienta es de Matemática Discreta.

Conjuntos numerables y la diagonal de Cantor

Esta sección es un repaso de una página.

¿Cuándo dos conjuntos infinitos tienen “el mismo tamaño”? Contar no sirve. Cantor propuso emparejar: dos conjuntos tienen el mismo tamaño si hay una correspondencia uno a uno entre sus elementos, sin que sobre ninguno de ningún lado.

Definición. Un conjunto es numerable (countable) si es finito o si se puede poner en correspondencia uno a uno con los naturales 1,2,3,…1, 2, 3, \ldots Dicho de otro modo: sus elementos se pueden escribir en una lista a1,a2,a3,…a_1, a_2, a_3, \ldots en la que cada elemento aparece en alguna posición finita. Un conjunto que no es numerable es no numerable (uncountable).

Algunos conjuntos numerables:

  • Los números pares: 2,4,6,…2, 4, 6, \ldots El par 2k2k está en la posición kk. Son “tantos” como los naturales, aunque sean una parte de ellos.
  • Los enteros: 0,1,−1,2,−2,…0, 1, -1, 2, -2, \ldots
  • Los pares de naturales (i,j)(i, j). No se pueden listar fila por fila, porque la primera fila no termina nunca. Se listan por diagonales: primero los que suman 2, después los que suman 3, y así. Cada diagonal es finita, así que todo par aparece. Con eso también son numerables las fracciones positivas.
  • Σ∗\Sigma^*, para cualquier alfabeto Σ\Sigma. Es la lista de la semana 1: primero las cadenas más cortas y, entre las de igual longitud, en el orden del alfabeto. Hay finitas cadenas de cada longitud, así que toda cadena aparece.

Dos hechos que usaremos. Un subconjunto de un conjunto numerable es numerable: se toma la lista y se tachan los elementos que no están. Y si cada elemento de un conjunto numerable se cambia por otra cosa, lo que resulta es numerable: es la misma lista con otros nombres, quizá con repeticiones.

Teorema (Cantor). El conjunto de los números reales no es numerable.

Demostración. Por contradicción, con el argumento de la diagonal. Basta ver que los reales entre 0 y 1 ya no son numerables. Supongamos que lo son: hay una lista r1,r2,r3,…r_1, r_2, r_3, \ldots en la que están todos. Escribimos cada uno con sus infinitos decimales, uno debajo del otro. Por ejemplo:

r1 = 0, [1] 4  1  5  9  …
r2 = 0,  5 [0] 0  0  0  …
r3 = 0,  3  3 [3] 3  3  …
r4 = 0,  7  1  8 [2] 8  …
r5 = 0,  0  4  4  4 [4] …

Construimos un número xx entre 0 y 1 mirando la diagonal, la de los corchetes. El decimal nn de xx se elige distinto del decimal nn de rnr_n: ponemos un 5 si ese decimal es un 4, y un 4 en cualquier otro caso. Con la tabla del ejemplo, la diagonal es 1, 0, 3, 2, 4 y sale x=0,44445…x = 0{,}44445\ldots

Entonces x≠r1x \neq r_1, porque difieren en el primer decimal. Y x≠r2x \neq r_2, porque difieren en el segundo. En general x≠rnx \neq r_n para todo nn, porque difieren en el decimal nn. Pero xx es un real entre 0 y 1, y la lista los tenía a todos. Contradicción. ∎

Un detalle: hay números con dos escrituras decimales, como 0,1999…=0,2000…0{,}1999\ldots = 0{,}2000\ldots, y uno podría temer que xx sea igual a algún rnr_n escrito de otra forma. No pasa, porque xx solo tiene cuatros y cincos, y los números con dos escrituras son los que terminan en nueves o en ceros.

Lo que hay que llevarse es el método, porque el teorema principal de hoy es este mismo argumento con otros objetos:

  1. Se supone una lista de todos los objetos.
  2. Se arma una tabla: la fila nn describe al objeto nn.
  3. Se construye un objeto nuevo que, en la posición nn, hace lo contrario de lo que dice la casilla (n,n)(n, n).
  4. El objeto nuevo difiere de cada objeto de la lista, y no puede estar en ella.

Hay más lenguajes que máquinas

En la semana 1 dimos este argumento sin formalizar, con “programas” y sin saber todavía qué era decidir. Ahora tiene todas sus piezas.

Las máquinas de Turing son numerables. Cada máquina MM tiene una descripción ⟨M⟩\langle M \rangle, que es una cadena sobre un alfabeto fijo: el de los caracteres de un archivo .tm, por ejemplo. El conjunto de todas las cadenas sobre ese alfabeto es numerable. Las descripciones de máquinas son un subconjunto: de la lista de todas las cadenas se tachan las que no son un archivo .tm válido. Queda una lista

M1,M2,M3,…M_1, M_2, M_3, \ldots

en la que está toda máquina de Turing.

Los lenguajes no son numerables. Fijemos Σ={0,1}\Sigma = \{\mathtt{0}, \mathtt{1}\} y la lista de sus cadenas, s1=εs_1 = \varepsilon, s2=0s_2 = \mathtt{0}, s3=1s_3 = \mathtt{1}, s4=00s_4 = \mathtt{00}, … Supongamos que los lenguajes sobre Σ\Sigma se pudieran listar: L1,L2,L3,…L_1, L_2, L_3, \ldots Armamos la tabla que en la fila ii y la columna jj dice si sj∈Lis_j \in L_i, y definimos el lenguaje de la diagonal al revés:

D={ si:si∉Li }D = \{\, s_i : s_i \notin L_i \,\}

Para cada ii, la cadena sis_i está en exactamente uno de DD y LiL_i, así que D≠LiD \neq L_i. El lenguaje DD no está en la lista, que los tenía a todos. Contradicción. Es la demostración de Cantor con “sí” y “no” en lugar de decimales.

Conclusión. Cada máquina de Turing reconoce exactamente un lenguaje, L(M)L(M). Entonces los lenguajes reconocibles son L(M1),L(M2),L(M3),…L(M_1), L(M_2), L(M_3), \ldots: se pueden listar, son numerables. El conjunto de todos los lenguajes no lo es. Luego:

Corolario. Existen lenguajes que no son reconocibles por ninguna máquina de Turing.

De hecho son casi todos: los reconocibles forman una lista, y lo que queda fuera es un conjunto no numerable. Los lenguajes con los que trabajamos todo el semestre, los que tienen una descripción finita y precisa, son la excepción.

Este resultado tiene el mismo defecto que en la semana 1: no señala a ninguno. El lenguaje DD depende de una lista hipotética y no se parece a nada que alguien quiera calcular. Queda abierta la posibilidad de que todos los problemas interesantes sean decidibles. La sección que sigue la cierra.

A_TM es indecidible

Teorema. ATMA_{\mathrm{TM}} es indecidible.

Es decir: no existe ninguna máquina de Turing que, con toda entrada ⟨M,w⟩\langle M, w \rangle, se detenga y responda correctamente si MM acepta ww.

Demostración. Por contradicción, con una diagonalización. Supongamos que ATMA_{\mathrm{TM}} es decidible. Entonces existe una máquina HH que lo decide:

H(⟨M,w⟩)={aceptasi M acepta wrechazasi M no acepta wH(\langle M, w \rangle) = \begin{cases} \text{acepta} & \text{si } M \text{ acepta } w \\ \text{rechaza} & \text{si } M \text{ no acepta } w \end{cases}

“No acepta” incluye los dos casos: que MM rechace ww y que MM no se detenga con ww. Lo que distingue a HH de UU es que HH siempre se detiene, también cuando MM no lo hace.

Con HH como subrutina construimos otra máquina, DD. Su entrada es la descripción de una máquina, y lo que hace es preguntarle a HH qué hace esa máquina cuando recibe su propia descripción, y hacer lo contrario.

D = "Con la entrada ⟨M⟩, donde M es una máquina de Turing:
  1. Correr H con la entrada ⟨M, ⟨M⟩⟩.
  2. Si H acepta, rechazar. Si H rechaza, aceptar."

Dos comprobaciones antes de seguir.

DD es una máquina de Turing legítima. El paso 1 arma la cadena ⟨M,⟨M⟩⟩\langle M, \langle M \rangle \rangle, que es copiar la entrada dos veces con un separador, y llama a HH, que por hipótesis existe. El paso 2 invierte una respuesta.

DD se detiene con toda entrada. Aquí se usa que HH siempre se detiene. El paso 1 termina porque HH decide. Entonces DD llega siempre al paso 2 y da una respuesta: con cada entrada ⟨M⟩\langle M \rangle, o acepta o rechaza. Resumiendo lo que hace:

D(⟨M⟩)={aceptasi M no acepta ⟨M⟩rechazasi M acepta ⟨M⟩D(\langle M \rangle) = \begin{cases} \text{acepta} & \text{si } M \text{ no acepta } \langle M \rangle \\ \text{rechaza} & \text{si } M \text{ acepta } \langle M \rangle \end{cases}

Ahora la pregunta que rompe todo. DD es una máquina de Turing, así que tiene una descripción ⟨D⟩\langle D \rangle, y esa descripción es una entrada válida para DD. ¿Qué hace DD con la entrada ⟨D⟩\langle D \rangle? Basta leer el resumen de arriba con M=DM = D:

D(⟨D⟩)={aceptasi D no acepta ⟨D⟩rechazasi D acepta ⟨D⟩D(\langle D \rangle) = \begin{cases} \text{acepta} & \text{si } D \text{ no acepta } \langle D \rangle \\ \text{rechaza} & \text{si } D \text{ acepta } \langle D \rangle \end{cases}

Las dos líneas son imposibles. Con cuidado, caso por caso:

  • Si DD acepta ⟨D⟩\langle D \rangle. Entonces ⟨D,⟨D⟩⟩∈ATM\langle D, \langle D \rangle \rangle \in A_{\mathrm{TM}}, y HH, que decide ATMA_{\mathrm{TM}}, acepta esa entrada en el paso 1. Por el paso 2, DD rechaza ⟨D⟩\langle D \rangle. Pero habíamos supuesto que la acepta.
  • Si DD no acepta ⟨D⟩\langle D \rangle. Entonces ⟨D,⟨D⟩⟩∉ATM\langle D, \langle D \rangle \rangle \notin A_{\mathrm{TM}}, y HH rechaza esa entrada en el paso 1. Por el paso 2, DD acepta ⟨D⟩\langle D \rangle. Pero habíamos supuesto que no la acepta.

DD acepta ⟨D⟩\langle D \rangle si y solo si DD no acepta ⟨D⟩\langle D \rangle. Eso es una contradicción, y vino de un solo supuesto: que HH existe. Por lo tanto HH no existe, y ATMA_{\mathrm{TM}} es indecidible. ∎

Diagrama de la máquina D. La entrada es ⟨M⟩, la descripción de una máquina. Dentro del recuadro de D hay dos bloques: el primero arma ⟨M, ⟨M⟩⟩ y el segundo es H, que responde si M acepta ⟨M⟩. De H salen dos flechas que invierten la respuesta: si H acepta, D rechaza; si H rechaza, D acepta. Una nota dice que D se detiene siempre, porque H se detiene siempre. Debajo, la pregunta de qué hace D con la entrada ⟨D⟩, que es el mismo diagrama con M igual a D, en dos filas. Primera fila: si D acepta ⟨D⟩, entonces H acepta ⟨D, ⟨D⟩⟩, porque H decide A_TM, y entonces D rechaza ⟨D⟩, por el paso 2 de D. Segunda fila: si D no acepta ⟨D⟩, entonces H rechaza ⟨D, ⟨D⟩⟩, y entonces D acepta ⟨D⟩. En los dos casos se llega a lo contrario de lo supuesto, y lo único supuesto fue que H existe.Diagrama de la máquina D. La entrada es ⟨M⟩, la descripción de una máquina. Dentro del recuadro de D hay dos bloques: el primero arma ⟨M, ⟨M⟩⟩ y el segundo es H, que responde si M acepta ⟨M⟩. De H salen dos flechas que invierten la respuesta: si H acepta, D rechaza; si H rechaza, D acepta. Una nota dice que D se detiene siempre, porque H se detiene siempre. Debajo, la pregunta de qué hace D con la entrada ⟨D⟩, que es el mismo diagrama con M igual a D, en dos filas. Primera fila: si D acepta ⟨D⟩, entonces H acepta ⟨D, ⟨D⟩⟩, porque H decide A_TM, y entonces D rechaza ⟨D⟩, por el paso 2 de D. Segunda fila: si D no acepta ⟨D⟩, entonces H rechaza ⟨D, ⟨D⟩⟩, y entonces D acepta ⟨D⟩. En los dos casos se llega a lo contrario de lo supuesto, y lo único supuesto fue que H existe.
D es H con la entrada duplicada y la respuesta invertida. Con su propia descripción, D tendría que hacer lo contrario de lo que hace.

Dónde está la diagonal

La demostración no menciona ninguna tabla, pero es el argumento de Cantor, y verla así ayuda a recordarla. Tomamos la lista M1,M2,M3,…M_1, M_2, M_3, \ldots de todas las máquinas de Turing, y armamos una tabla. La fila ii es la máquina MiM_i. La columna jj es la entrada ⟨Mj⟩\langle M_j \rangle. La casilla dice si MiM_i acepta ⟨Mj⟩\langle M_j \rangle.

La animación de más abajo la arma paso a paso. Los valores son inventados, para ver la forma. Al principio, una casilla vacía quiere decir que la máquina no acepta: rechaza o no se detiene.

La diagonal son las casillas (i,i)(i, i), que dicen qué hace MiM_i con su propia descripción. Esta tabla existe, sea o no decidible ATMA_{\mathrm{TM}}: cada casilla tiene un valor bien definido. Si HH existiera, podría calcular cualquier casilla. La casilla (i,j)(i, j) es la respuesta de HH con la entrada ⟨Mi,⟨Mj⟩⟩\langle M_i, \langle M_j \rangle \rangle, y en las casillas vacías HH respondería “rechaza”.

La máquina DD recorre la diagonal y hace lo contrario: con la entrada ⟨Mi⟩\langle M_i \rangle mira la casilla (i,i)(i, i) y la invierte. Con los valores del ejemplo, la diagonal dice acepta, acepta, rechaza, rechaza, y la fila de DD es rechaza, rechaza, acepta, acepta.

Animación de la tabla de la diagonal, con valores inventados. Las filas son las máquinas M₁, M₂, M₃, M₄ y siguen; las columnas son las entradas ⟨M₁⟩, ⟨M₂⟩, ⟨M₃⟩, ⟨M₄⟩ y siguen. Primer paso: la casilla (i, j) dice si Mᵢ acepta ⟨Mⱼ⟩, y una casilla vacía quiere decir que no acepta. M₁ acepta ⟨M₁⟩ y ⟨M₃⟩; M₂ acepta las cuatro; M₃ no acepta ninguna; M₄ acepta ⟨M₁⟩ y ⟨M₂⟩. Segundo paso: si H existiera calcularía cualquier casilla, y las vacías se llenan con «rechaza». Tercer paso: se resalta la diagonal, que dice acepta, acepta, rechaza, rechaza. Cuarto paso: debajo aparece la fila de D, casilla por casilla, invirtiendo la diagonal: rechaza, rechaza, acepta, acepta. Quinto paso: el resto de la tabla se apaga y un signo de distinto une cada casilla de D con la casilla de la diagonal de su columna: la fila de D difiere de la de Mᵢ en la columna i, así que D no es ninguna máquina de la lista. Sexto paso: pero D es una máquina de Turing, así que es M_k para algún k; aparece la columna ⟨M_k⟩, que es ⟨D⟩, y la casilla (k, k) queda marcada como imposible, porque ahí la fila tendría que ser distinta de sí misma.Animación de la tabla de la diagonal, con valores inventados. Las filas son las máquinas M₁, M₂, M₃, M₄ y siguen; las columnas son las entradas ⟨M₁⟩, ⟨M₂⟩, ⟨M₃⟩, ⟨M₄⟩ y siguen. Primer paso: la casilla (i, j) dice si Mᵢ acepta ⟨Mⱼ⟩, y una casilla vacía quiere decir que no acepta. M₁ acepta ⟨M₁⟩ y ⟨M₃⟩; M₂ acepta las cuatro; M₃ no acepta ninguna; M₄ acepta ⟨M₁⟩ y ⟨M₂⟩. Segundo paso: si H existiera calcularía cualquier casilla, y las vacías se llenan con «rechaza». Tercer paso: se resalta la diagonal, que dice acepta, acepta, rechaza, rechaza. Cuarto paso: debajo aparece la fila de D, casilla por casilla, invirtiendo la diagonal: rechaza, rechaza, acepta, acepta. Quinto paso: el resto de la tabla se apaga y un signo de distinto une cada casilla de D con la casilla de la diagonal de su columna: la fila de D difiere de la de Mᵢ en la columna i, así que D no es ninguna máquina de la lista. Sexto paso: pero D es una máquina de Turing, así que es M_k para algún k; aparece la columna ⟨M_k⟩, que es ⟨D⟩, y la casilla (k, k) queda marcada como imposible, porque ahí la fila tendría que ser distinta de sí misma.
La fila de D se obtiene invirtiendo la diagonal, y por eso difiere de todas las filas. Como D también tendría que ser una fila, la casilla (k, k) no puede tener ningún valor.

La fila de DD difiere de la fila de M1M_1 en la primera columna, de la de M2M_2 en la segunda, y de la de MiM_i en la columna ii. Así que DD no es ninguna de las máquinas de la lista. Pero DD es una máquina de Turing, y la lista las tenía a todas: DD es MkM_k para algún kk. En la casilla (k,k)(k, k), la fila de DD tendría que ser distinta de sí misma. Esa casilla es ”DD con la entrada ⟨D⟩\langle D \rangle”.

La diferencia con la sección anterior es lo que hace importante al teorema. Allá, el lenguaje diagonal salía de una lista hipotética de lenguajes y no se sabía nada de él. Aquí la diagonal se aplica a la lista de las máquinas, que sí existe, y lo que resulta imposible es un problema concreto: decidir si una máquina dada acepta una entrada dada.

Lo que la demostración usa, y lo que no

El paso que usa “siempre se detiene”. Vale la pena hacer el experimento de quitar esa hipótesis. Pongan, en lugar de HH, la máquina universal UU, que existe y reconoce ATMA_{\mathrm{TM}}:

D' = "Con la entrada ⟨M⟩:
  1. Correr U con la entrada ⟨M, ⟨M⟩⟩.
  2. Si U acepta, rechazar. Si U rechaza, aceptar."

D′D' existe, sin ningún supuesto. ¿Qué hace con ⟨D′⟩\langle D' \rangle? En el paso 1, UU simula a D′D' con la entrada ⟨D′⟩\langle D' \rangle. Esa simulación empieza por el paso 1, en el que UU simula a D′D' con ⟨D′⟩\langle D' \rangle, que empieza por el paso 1… D′D' no se detiene con ⟨D′⟩\langle D' \rangle. Y no hay ninguna contradicción: ”D′D' no acepta ⟨D′⟩\langle D' \rangle” es cierto, y UU efectivamente no acepta ⟨D′,⟨D′⟩⟩\langle D', \langle D' \rangle \rangle, porque se queda corriendo. Todo es coherente. La contradicción aparece solo cuando el paso 1 está obligado a terminar con una respuesta, y eso es exactamente lo que HH prometía y UU no.

Darle a una máquina su propia descripción es legal. ⟨M⟩\langle M \rangle es una cadena como cualquier otra, y MM acepta cadenas. Es lo que pasa cuando un compilador de C++ escrito en C++ se compila a sí mismo, o cuando le pasan a wc su propio archivo fuente. Puede que a MM esa entrada no le signifique nada. No importa: la acepta, la rechaza o no se detiene, y con eso basta.

No depende de detalles. La demostración no usa cuántas cintas tiene HH, ni cuánto tarda, ni cómo está hecha por dentro. Vale para cualquier HH, por ingeniosa que sea. Y por la tesis de Church-Turing, vale para cualquier lenguaje de programación: no hay un programa en C++ que decida si un programa en C++ acepta su entrada.

No es una paradoja. La frase “esta oración es falsa” no es ni verdadera ni falsa, y uno se queda sin saber qué concluir. Aquí sí se concluye algo, porque la contradicción depende de un supuesto. Lo que resulta contradictorio es la existencia de HH, y la conclusión es un teorema: HH no existe.

Idea clave. Si hubiera una máquina HH que decide ATMA_{\mathrm{TM}}, se podría construir una máquina DD que, con la descripción de cualquier máquina, hace lo contrario de lo que esa máquina hace con su propia descripción. Con la entrada ⟨D⟩\langle D \rangle, DD tendría que hacer lo contrario de sí misma.

Error común. Leer el teorema como “nadie ha encontrado todavía el algoritmo”. No es una pregunta abierta: está demostrado que el algoritmo no existe, igual que está demostrado que 2\sqrt{2} no es una fracción. Más memoria, más tiempo o una idea nueva no cambian nada.

El problema de la parada

La forma más conocida del resultado no pregunta si la máquina acepta, sino si termina:

HALTTM={ ⟨M,w⟩:M es una maˊquina de Turing que se detiene con la entrada w }\mathrm{HALT}_{\mathrm{TM}} = \{\, \langle M, w \rangle : M \text{ es una máquina de Turing que se detiene con la entrada } w \,\}

Es el problema de la parada (halting problem): dado un programa y una entrada, ¿termina, o se queda en un ciclo infinito?

Teorema. HALTTM\mathrm{HALT}_{\mathrm{TM}} es indecidible.

Demostración. Por reducción desde ATMA_{\mathrm{TM}} hacia HALTTM\mathrm{HALT}_{\mathrm{TM}}. La dirección es esa porque queremos mostrar que, si HALTTM\mathrm{HALT}_{\mathrm{TM}} fuera decidible, también lo sería ATMA_{\mathrm{TM}}, y ya sabemos que no lo es.

Supongamos que una máquina RR decide HALTTM\mathrm{HALT}_{\mathrm{TM}}. Con RR construimos una máquina SS:

S = "Con la entrada ⟨M, w⟩, donde M es una máquina de Turing y w una cadena:
  1. Correr R con la entrada ⟨M, w⟩.
  2. Si R rechaza, rechazar.
  3. Si R acepta, simular M con la entrada w hasta que se detenga.
  4. Si M aceptó, aceptar. Si M rechazó, rechazar."

SS termina siempre. El paso 1 termina porque RR decide. El paso 3 es una simulación de una máquina de Turing, que en general podría no terminar. Pero solo se llega a él cuando RR aceptó, es decir, cuando MM sí se detiene con ww. Es una simulación con garantía.

SS decide ATMA_{\mathrm{TM}}. Si MM acepta ww, entonces se detiene, RR acepta, la simulación termina en aceptación y SS acepta. Si MM rechaza ww, RR acepta, la simulación termina en rechazo y SS rechaza. Si MM no se detiene con ww, RR rechaza y SS rechaza en el paso 2, correctamente, porque una máquina que no se detiene no acepta.

Entonces SS decide ATMA_{\mathrm{TM}}, que es indecidible. Contradicción: RR no existe. ∎

Esta demostración ya no usa la diagonal. Usa el teorema anterior y un argumento de la forma “si pudiera resolver esto, podría resolver aquello”. Es una reducción, y es el tema de toda la semana 10: casi todos los problemas indecidibles que veremos se demuestran así, a partir de ATMA_{\mathrm{TM}}.

HALTTM\mathrm{HALT}_{\mathrm{TM}} y ATMA_{\mathrm{TM}} son el mismo fenómeno visto desde dos lados. En la demostración se ve bien: lo único que le impedía a UU decidir ATMA_{\mathrm{TM}} era no saber si la simulación iba a terminar. Si alguien responde esa pregunta, lo demás es simular. La dificultad de ATMA_{\mathrm{TM}} es la parada. También vale al revés: con una máquina que decidiera ATMA_{\mathrm{TM}} se decidiría HALTTM\mathrm{HALT}_{\mathrm{TM}}, y es el ejercicio 8.

Como ATMA_{\mathrm{TM}}, el problema de la parada es reconocible: se simula MM con ww y se acepta si la simulación termina, sea como sea.

Reconocible y correconocible

Tenemos lenguajes decidibles y lenguajes reconocibles que no son decidibles. Para encontrar uno que ni siquiera es reconocible hay que mirar los complementos.

Un lenguaje es correconocible (co-recognizable) si su complemento es reconocible. Que LL sea reconocible quiere decir que hay un procedimiento que confirma los “sí”: si w∈Lw \in L, tarde o temprano lo dice. Que sea correconocible quiere decir que hay uno que confirma los “no”.

Teorema. Un lenguaje es decidible si y solo si es reconocible y correconocible.

Con otras palabras: LL es decidible si y solo si LL y L‾\overline{L} son los dos reconocibles.

Demostración. Son dos direcciones.

Si LL es decidible, entonces LL y L‾\overline{L} son reconocibles. Sea MM una máquina que decide LL. En particular MM reconoce LL. Para el complemento, tomamos MM e intercambiamos sus estados de aceptación y de rechazo. La máquina que resulta acepta exactamente las cadenas que MM rechaza, y como MM se detiene siempre, las que rechaza son todas las que no acepta: las de L‾\overline{L}. Así que L‾\overline{L} es decidible, y en particular reconocible.

Si LL y L‾\overline{L} son reconocibles, entonces LL es decidible. Por construcción. Sea M1M_1 una máquina que reconoce LL y M2M_2 una que reconoce L‾\overline{L}. Las corremos a la vez:

M = "Con la entrada w:
  1. Correr M1 y M2 con la entrada w en paralelo: un paso de M1, un paso de M2, un paso de
     M1, y así, alternando.
  2. Si en algún momento M1 acepta, aceptar. Si en algún momento M2 acepta, rechazar."

MM termina siempre. Toda cadena ww está en LL o en L‾\overline{L}. En el primer caso M1M_1 acepta ww después de alguna cantidad finita de pasos tt; en el segundo, M2M_2 lo hace. En cualquiera de los dos, MM se detiene a más tardar cuando las dos simulaciones llevan tt pasos cada una.

MM responde bien. Si w∈Lw \in L, entonces M2M_2 no acepta ww, porque w∉L‾w \notin \overline{L}: MM no puede rechazar, y como se detiene, acepta. Si w∉Lw \notin L, es M1M_1 la que no acepta, y MM rechaza. ∎

El detalle que hace funcionar la construcción es alternar. Correr primero M1M_1 hasta que termine y después M2M_2 no sirve: si w∉Lw \notin L, M1M_1 puede no detenerse, y nunca le tocaría el turno a M2M_2. La misma idea apareció en la semana 7, cuando una máquina determinista recorría por niveles, y no en profundidad, el árbol de una no determinista. Una máquina de una cinta puede alternar dos simulaciones porque puede simular una de dos cintas.

Para verlo correr hacen falta dos máquinas que reconozcan sin decidir. Una es search_one.tm, que reconoce las cadenas con algún 1\mathtt{1}. La otra, machines/search_end.tm, reconoce el complemento: acepta si llega al primer blanco sin haber visto un 1\mathtt{1}, y si ve uno entra a un estado del que no sale y avanza para siempre.

Estado Lee 0\mathtt{0} Lee 1\mathtt{1} Lee ⊔\sqcup
scan\mathit{scan} scan\mathit{scan}, 0\mathtt{0}, R\mathrm{R} lost\mathit{lost}, 1\mathtt{1}, R\mathrm{R} qacceptq_{\text{accept}}, ⊔\sqcup, R\mathrm{R}
lost\mathit{lost} lost\mathit{lost}, 0\mathtt{0}, R\mathrm{R} lost\mathit{lost}, 1\mathtt{1}, R\mathrm{R} lost\mathit{lost}, ⊔\sqcup, R\mathrm{R}

Cada una por separado se queda corriendo con las cadenas de la otra. Alternadas, siempre hay respuesta:

$ build/alternate machines/search_one.tm machines/search_end.tm 0001 000 '' 1
w = 0001: M1 acepta después de 4 rondas; se acepta
w = 000: M2 acepta después de 4 rondas; se rechaza
w = ε: M2 acepta después de 1 ronda; se rechaza
w = 1: M1 acepta después de 1 ronda; se acepta

Un lenguaje que no es reconocible

Corolario. ATM‾\overline{A_{\mathrm{TM}}}, el complemento de ATMA_{\mathrm{TM}}, no es reconocible.

Demostración. Por contradicción. Sabemos que ATMA_{\mathrm{TM}} es reconocible: lo reconoce UU. Si ATM‾\overline{A_{\mathrm{TM}}} también fuera reconocible, por el teorema ATMA_{\mathrm{TM}} sería decidible. No lo es. ∎

Ahí está el lenguaje concreto que el argumento de conteo prometía. ATM‾\overline{A_{\mathrm{TM}}} contiene los pares ⟨M,w⟩\langle M, w \rangle en los que MM no acepta ww (y las cadenas que no describen ningún par). No hay ninguna máquina que acepte exactamente esos pares.

La asimetría tiene sentido. Que MM acepta ww se puede confirmar: se muestra la ejecución, que es finita, y cualquiera la comprueba. Que MM no acepta ww, cuando es porque no se detiene, no tiene ninguna confirmación finita a la vista: esperar no alcanza. ATMA_{\mathrm{TM}} es un problema en el que los “sí” se pueden confirmar y los “no” no.

El mismo razonamiento sirve para HALTTM\mathrm{HALT}_{\mathrm{TM}}: es reconocible e indecidible, así que su complemento, “esta máquina no se detiene con esta entrada”, tampoco es reconocible.

El mapa, completo:

Un recuadro punteado, todos los lenguajes sobre Σ, con dos recuadros adentro que se cruzan. El de la izquierda son los reconocibles, donde se confirman los «sí»; el de la derecha, los correconocibles, donde se confirman los «no». La zona donde se cruzan son los decidibles, las dos cosas a la vez: ahí están los regulares, los libres de contexto, A_DFA, E_DFA, EQ_DFA, A_CFG y E_CFG. En la parte de los reconocibles que queda fuera del cruce están A_TM y HALT_TM. En la parte de los correconocibles que queda fuera del cruce están el complemento de A_TM y el complemento de HALT_TM, que no son reconocibles. Fuera de los dos recuadros, una nota: ni reconocibles ni correconocibles son casi todos los lenguajes, y en la semana 10 aparece EQ_TM.Un recuadro punteado, todos los lenguajes sobre Σ, con dos recuadros adentro que se cruzan. El de la izquierda son los reconocibles, donde se confirman los «sí»; el de la derecha, los correconocibles, donde se confirman los «no». La zona donde se cruzan son los decidibles, las dos cosas a la vez: ahí están los regulares, los libres de contexto, A_DFA, E_DFA, EQ_DFA, A_CFG y E_CFG. En la parte de los reconocibles que queda fuera del cruce están A_TM y HALT_TM. En la parte de los correconocibles que queda fuera del cruce están el complemento de A_TM y el complemento de HALT_TM, que no son reconocibles. Fuera de los dos recuadros, una nota: ni reconocibles ni correconocibles son casi todos los lenguajes, y en la semana 10 aparece EQ_TM.
El mapa completo. Los decidibles son exactamente el cruce de los reconocibles con los correconocibles; A_TM queda de un lado y su complemento, del otro.

Los decidibles son exactamente la zona del medio, donde los dos conjuntos se cruzan: es lo que dice el teorema.

Idea clave. Decidible es reconocible más correconocible. Si un lenguaje es reconocible y no es decidible, su complemento no puede ser reconocible. Así se obtiene, de ATMA_{\mathrm{TM}}, un lenguaje concreto que ninguna máquina reconoce.

Qué significa en la práctica

El teorema, dicho con programas: no existe un programa que reciba cualquier programa, con su entrada, y diga siempre correctamente si termina o entra en un ciclo infinito. Lo mismo para “si imprime 42”, “si llega a esta línea”, “si accede a memoria que no le corresponde”: la semana 10 muestra que casi cualquier pregunta sobre el comportamiento de un programa cae del mismo lado.

Hay que leer la frase con todos sus cuantificadores. Dice que no hay un algoritmo que acierte con todos los programas. No dice nada de un programa en particular.

Error común. Concluir que “no se puede saber nada de ningún programa”. Indecidible quiere decir que ningún algoritmo acierta en todos los casos. De muchísimos programas concretos sí se sabe si terminan: de search_one.tm con 000\mathtt{000} demostramos que no, y de toda máquina de la sesión A demostramos que sí. Lo que no existe es el método general.

Lo que sí se puede hacer, y se hace todos los días:

  • Analizar un programa concreto. Una persona, o una herramienta, puede demostrar que un programa dado termina. Los algoritmos de su curso de Algoritmos vienen con esa demostración.
  • Restringir la clase de programas. Para los DFA, todas las preguntas de hoy son decidibles. Hay lenguajes de programación diseñados para que todo programa termine, a cambio de no poder expresarlo todo. Un programa sin ciclos ni recursión termina siempre.
  • Aceptar tres respuestas. Una herramienta puede responder “termina”, “no termina” o “no sé”, y no equivocarse nunca en las dos primeras. Eso no contradice el teorema. Lo que el teorema impide es eliminar el “no sé”.
  • Equivocarse hacia un lado. Un compilador que avisa “esta variable podría usarse sin inicializar” a veces avisa de más: rechaza programas que estaban bien. Un verificador de tipos también. Es el precio de responder siempre.
  • Poner un límite. El juez del curso corta los programas a los 2 segundos y responde TLE. No decide si el programa termina: decide si termina en 2 segundos, que es otra pregunta, y esa sí es decidible.

El caso del compañero que dice que su programa detecta ciclos infinitos, y que lo probó con mil programas, se responde con precisión así. Puede ser cierto que su programa acierte con esos mil. Lo que el teorema garantiza es que existe al menos un programa con el que falla: o da una respuesta equivocada, o no responde. Y la demostración dice cómo fabricarlo: es DD, construido a partir de su propio detector. Mil casos a favor no pesan contra una demostración de que hay un caso en contra.

En la práctica. Por eso un antivirus no puede decidir si un programa hará algo dañino, un compilador no puede eliminar todo el código que nunca se ejecuta, y ningún entorno de desarrollo puede avisar de todos los ciclos infinitos sin dar falsas alarmas. Todas esas herramientas existen y son útiles: aproximan. La indecidibilidad explica por qué aproximan, y por qué ninguna versión futura dejará de hacerlo.

El código de la semana

code/week-09/
├── dfa.h                 struct Dfa, lectura del formato .dfa, δ*, producto (el de la semana 1)
├── nfa.h                 struct Nfa y la construcción de subconjuntos
├── decide.h              E_DFA y EQ_DFA: alcanzabilidad, diferencia simétrica, pares alcanzables
├── minimize.h            minimización de un DFA, para producir los autómatas del laboratorio
├── cfg.h                 struct Cfg, E_CFG por marcas, A_CFG con 2n − 1 pasos y con CYK
├── tm.h                  struct Tm, un paso, simulación con límite, dos máquinas alternadas
├── a_dfa.cpp             A_DFA: simular
├── a_nfa.cpp             A_NFA: convertir y simular
├── e_dfa.cpp             E_DFA: las marcas, ronda por ronda
├── eq_dfa.cpp            EQ_DFA: con el producto completo o solo con los pares alcanzables
├── a_cfg.cpp             A_CFG: de las dos maneras
├── e_cfg.cpp             E_CFG: las marcas, ronda por ronda
├── universal.cpp         la máquina universal: una máquina de Turing como dato, con límite de pasos
├── alternate.cpp         dos reconocedores alternados
├── make_kth.cpp          escribe los autómatas de lab/dfa_equiv/machines
├── machines/             los autómatas, las gramáticas y las máquinas del capítulo
├── test_dfa.cpp          pruebas de A_DFA, A_NFA, E_DFA y EQ_DFA
├── test_cfg.cpp          pruebas de E_CFG y A_CFG
├── test_tm.cpp           pruebas del simulador, del límite de pasos y de la alternancia
└── lab/dfa_equiv/        el laboratorio

make compila todo, y make test corre las pruebas con ASan y UBSan.

$ make test
test_dfa: ok (A_DFA, A_NFA, E_DFA, EQ_DFA; 400 pares de DFA al azar)
test_cfg: ok (E_CFG, A_CFG; 500 gramáticas al azar)
test_tm: ok (4 máquinas, 2047 cadenas cada una)
Todas las pruebas pasaron.

Las pruebas comprueban con assert lo que este capítulo afirma sobre máquinas concretas.

  • test_dfa revisa las ejecuciones y los conteos copiados arriba: los 7 pares alcanzables de 21, los 8 estados de aceptación del producto, la cadena 0101\mathtt{0101} y que ninguna más corta separa a los dos autómatas. Después compara 400 pares de autómatas al azar de tres maneras: con el producto completo, con los pares alcanzables y probando todas las cadenas de longitud menor que ∣QA∣⋅∣QB∣|Q_A| \cdot |Q_B|. Las tres coinciden, y las cadenas que devuelven tienen la misma longitud.
  • test_cfg revisa las rondas de marcas de las tres gramáticas, compara CYK con las derivaciones de 2n−12n - 1 pasos sobre todas las cadenas de longitud a lo sumo 10, comprueba que con 2n−22n - 2 pasos no se llega, y contrasta el algoritmo de marcas con CYK en 500 gramáticas al azar.
  • test_tm comprueba que zeros_ones.tm y has_one.tm se detienen con las 2047 cadenas binarias de longitud a lo sumo 10, que search_one.tm sigue corriendo con las que no tienen 1\mathtt{1} y por qué (está en scan\mathit{scan} con el cabezal en la celda tt después de tt pasos), y que las dos máquinas alternadas responden siempre, en a lo sumo ∣w∣+1|w| + 1 rondas.

Una prueba no puede comprobar que una máquina “no se detiene nunca”: solo puede correrla una cantidad finita de pasos. Eso también es el tema del capítulo. Lo que test_tm comprueba para search_one.tm es el invariante que usamos para demostrarlo.

Los archivos de machines/ son:

Archivo Qué es Tamaño
ends_01.dfa Termina en 01\mathtt{01}, el de la semana 1 3 estados
ends_01_history.dfa Termina en 01\mathtt{01}, recordando los dos últimos símbolos 7 estados
ends_01_wrong.dfa Un intento equivocado: se separa del correcto con 0101\mathtt{0101} 3 estados
unreachable_accept.dfa Lenguaje vacío con un estado de aceptación 4 estados
even_ones.dfa, contains_101.dfa Dos autómatas de la semana 1, para comparar 2 y 4 estados
third_from_end.nfa El tercer símbolo desde el final es 1\mathtt{1} 4 estados
anbn_chomsky.cfg {anbn}\{\mathtt{a}^n\mathtt{b}^n\} en forma normal de Chomsky 8 reglas
parens.cfg Paréntesis balanceados 2 reglas
no_base_case.cfg Una gramática que no genera nada 7 reglas
zeros_ones.tm Decide {0n1n}\{\mathtt{0}^n\mathtt{1}^n\} 6 estados
has_one.tm Decide “contiene un 1\mathtt{1}” 3 estados
search_one.tm Reconoce “contiene un 1\mathtt{1}” sin decidirlo 3 estados
search_end.tm Reconoce “no contiene ningún 1\mathtt{1}” sin decidirlo 4 estados

En dfa.h y en decide.h los estados son cadenas y δ\delta es un std::map, como en la semana 1: el código se lee como la definición, y no es rápido. Para el laboratorio hace falta otra representación.

El laboratorio

En lab/dfa_equiv está el enunciado, un esqueleto y los casos. La entrada son dos DFA separados por una línea ---, y la salida es equivalentes, o distintos y una cadena de longitud mínima que uno acepta y el otro no (eps si es la vacía).

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

Es el algoritmo de Sin construir el producto. Como suele haber varias cadenas de longitud mínima, el juez usa un verificador que comprueba la longitud y que la cadena de verdad separe a los autómatas. Los casos grandes tienen autómatas de hasta 50 000 estados, con un producto de 2 500 000 000 de pares del que se alcanzan 50 000: quien construya el producto completo, como la máquina FF, recibe TLE.

La carpeta lab/dfa_equiv/machines trae seis autómatas para “el sexto símbolo desde el final es 1\mathtt{1}”, que es la familia con la que midieron la construcción de subconjuntos en la semana 2 y la minimización en la semana 4. Los escribe make_kth:

$ make kth
build/make_kth 6 lab/dfa_equiv/machines
k = 6
archivo               estados  alcanzables
kth6_subsets.dfa           64           64
kth6_all.dfa              128           64
kth6_history.dfa          127          127
kth6_min.dfa               64           64
kth6_wrong.dfa             63           63
minimizar kth6_subsets.dfa da 64 estados
los cuatro primeros son equivalentes
kth6_min.dfa y kth6_wrong.dfa se separan con 1100000

El NFA tiene 7 estados. Su construcción de subconjuntos da 64 estados alcanzables, que es 262^6, y ese autómata ya es mínimo: minimizarlo no le quita ninguno. Las otras dos versiones tienen estados de más por razones distintas. kth6_all.dfa tiene los 27=1282^7 = 128 subconjuntos, y la mitad son inalcanzables. kth6_history.dfa tiene un estado por cada cadena de longitud a lo sumo 6, que son 27−1=1272^7 - 1 = 127, todos alcanzables, y muchos equivalentes entre sí. kth6_wrong.dfa es el mínimo con dos estados fusionados por error.

$ build/eq_dfa lab/dfa_equiv/machines/kth6_all.dfa lab/dfa_equiv/machines/kth6_history.dfa
A = lab/dfa_equiv/machines/kth6_all.dfa, 128 estados
B = lab/dfa_equiv/machines/kth6_history.dfa, 127 estados
pares visitados: 127 de 16256
equivalentes: L(A) = L(B), ⟨A, B⟩ ∈ EQ_DFA
$ build/eq_dfa lab/dfa_equiv/machines/kth6_min.dfa lab/dfa_equiv/machines/kth6_wrong.dfa
A = lab/dfa_equiv/machines/kth6_min.dfa, 64 estados
B = lab/dfa_equiv/machines/kth6_wrong.dfa, 63 estados
pares visitados: 79 de 4032
distintos: ⟨A, B⟩ ∉ EQ_DFA
una cadena más corta que los separa: 1100000 (7 símbolos); A la acepta y B la rechaza

En el laboratorio comprobarán lo mismo con su propio programa, y con los autómatas que ustedes produjeron en las semanas 2 y 4.

Resumen

  • Una máquina, un autómata o una gramática se escribe como una cadena, ⟨M⟩\langle M \rangle. Una pregunta sobre máquinas es un lenguaje de descripciones, y se puede preguntar si es decidible.
  • Para demostrar que un lenguaje es decidible se da un algoritmo y se muestran dos cosas: que termina con toda entrada y que responde bien. Lo delicado es la primera.
  • ADFAA_{\mathrm{DFA}}, ANFAA_{\mathrm{NFA}} y AREXA_{\mathrm{REX}} son decidibles: se convierte al modelo anterior con una construcción ya demostrada, y se simula. Un DFA siempre termina.
  • EDFAE_{\mathrm{DFA}} es decidible: se marcan los estados alcanzables y se mira si alguno es de aceptación. No se prueban cadenas.
  • EQDFA\mathrm{EQ}_{\mathrm{DFA}} es decidible: el producto con FF igual a los pares en los que exactamente uno acepta reconoce la diferencia simétrica, y dos lenguajes son iguales si y solo si esa diferencia es vacía. En un programa se recorren solo los pares alcanzables, en anchura, y el primer par que separa da una cadena de longitud mínima, siempre menor que ∣QA∣⋅∣QB∣|Q_A| \cdot |Q_B|.
  • ACFGA_{\mathrm{CFG}} es decidible: en forma normal de Chomsky, una derivación de una cadena de longitud nn tiene exactamente 2n−12n - 1 pasos, y eso da la cota que faltaba. CYK lo hace en tiempo polinomial.
  • ECFGE_{\mathrm{CFG}} es decidible: se marcan, desde los terminales hacia arriba, las variables que generan alguna cadena.
  • La demostración de EQDFA\mathrm{EQ}_{\mathrm{DFA}} no se puede copiar para EQCFG\mathrm{EQ}_{\mathrm{CFG}}, porque los lenguajes libres de contexto no son cerrados bajo complemento ni intersección. Es indecidible, y se demuestra en la semana 10.
  • Todo lenguaje libre de contexto es decidible. Regulares ⊂\subset libres de contexto ⊂\subset decidibles ⊂\subset reconocibles, y las tres inclusiones son estrictas.
  • La máquina universal UU recibe ⟨M,w⟩\langle M, w \rangle y simula MM con ww. Un intérprete es una máquina universal. UU reconoce ATMA_{\mathrm{TM}} y no lo decide: si MM no se detiene, UU tampoco.
  • Un límite de pasos no arregla eso: “no se detuvo en NN pasos” no dice qué pasa después. Detectar configuraciones repetidas tampoco: una máquina puede no detenerse sin repetir ninguna.
  • Un conjunto es numerable si se puede listar. Las máquinas de Turing son numerables y los lenguajes no, por la diagonal de Cantor: hay lenguajes que ninguna máquina reconoce.
  • ATMA_{\mathrm{TM}} es indecidible. Si HH lo decidiera, la máquina DD que con ⟨M⟩\langle M \rangle hace lo contrario de lo que MM hace con ⟨M⟩\langle M \rangle se contradice con la entrada ⟨D⟩\langle D \rangle. La hipótesis de que HH siempre se detiene se usa para que DD siempre responda.
  • HALTTM\mathrm{HALT}_{\mathrm{TM}} es indecidible, por una reducción desde ATMA_{\mathrm{TM}}: con un decididor de la parada, simular sería seguro.
  • Un lenguaje es decidible si y solo si él y su complemento son reconocibles: se corren los dos reconocedores alternando pasos. Por eso el complemento de ATMA_{\mathrm{TM}} no es reconocible.
  • Indecidible quiere decir que ningún algoritmo acierta con todas las entradas. De programas concretos, y de clases restringidas como los DFA, se puede saber todo.

Ejercicios

  1. Den un algoritmo de alto nivel, en el formato de este capítulo, que decida si un DFA acepta alguna cadena de longitud par. Demuestren que termina y que responde bien. Pista: construyan otro DFA y usen la máquina TT.
  2. Sea ALLDFA={ ⟨A⟩:A es un DFA y L(A)=Σ∗ }\mathrm{ALL}_{\mathrm{DFA}} = \{\, \langle A \rangle : A \text{ es un DFA y } L(A) = \Sigma^* \,\}. Demuestren que es decidible de dos maneras: reduciendo la pregunta a EDFAE_{\mathrm{DFA}}, y diciendo directamente qué hay que mirar en los estados alcanzables. Comprueben su respuesta con build/e_dfa y un autómata de machines/, modificado a mano.
  3. Demuestren que { ⟨A,B⟩:A y B son DFA y L(A)⊆L(B) }\{\, \langle A, B \rangle : A \text{ y } B \text{ son DFA y } L(A) \subseteq L(B) \,\} es decidible. ¿Qué conjunto FF hay que usar en el producto? Den la cadena que su algoritmo encontraría para ends_01_wrong.dfa y ends_01.dfa, en ese orden y en el orden contrario.
  4. En el producto de ends_01.dfa y ends_01_history.dfa se alcanzan 7 pares de 21. Escriban, para cada estado del autómata de 7, con qué estado del de 3 aparece, y expliquen con palabras por qué no puede aparecer con otro. Después den dos DFA de 3 estados cada uno en cuyo producto se alcancen los 9 pares.
  5. La cota de Sin construir el producto dice que dos DFA distintos se separan con una cadena de longitud menor que ∣QA∣⋅∣QB∣|Q_A| \cdot |Q_B|. Se puede mejorar mucho: demuestren que alcanza con longitud a lo sumo ∣QA∣+∣QB∣−2|Q_A| + |Q_B| - 2. Pista: junten los dos autómatas en uno solo, con ∣QA∣+∣QB∣|Q_A| + |Q_B| estados, y piensen en el refinamiento de particiones de la semana 4: cada ronda que separa algo agrega al menos un bloque. Después den dos DFA sobre {0}\{\mathtt{0}\}, con 2 y 3 estados, que se separen recién con una cadena de longitud 3, y comprueben con build/eq_dfa.
  6. Apliquen a mano el algoritmo de marcas de ECFGE_{\mathrm{CFG}} a la gramática S→AB∣CSS \to AB \mid CS, A→aAA \to \mathtt{a}A, B→b∣BBB \to \mathtt{b} \mid BB, C→c∣ACC \to \mathtt{c} \mid AC. Escriban qué se marca en cada ronda y la respuesta. Después agréguenle una regla para que su lenguaje deje de ser vacío, escríbanla como archivo .cfg y comprueben con build/e_cfg.
  7. Demuestren que el lenguaje de las descripciones ⟨G⟩\langle G \rangle de gramáticas libres de contexto que generan ε\varepsilon es decidible. Después, sin convertir a forma normal de Chomsky: adapten el algoritmo de marcas para marcar las variables que generan ε\varepsilon, y demuestren que su adaptación es correcta.
  8. Demuestren que si ATMA_{\mathrm{TM}} fuera decidible, HALTTM\mathrm{HALT}_{\mathrm{TM}} también lo sería. Pista: a partir de MM, construyan la máquina que es igual a MM con los estados de aceptación y de rechazo intercambiados. ¿De qué problema a cuál va esta reducción? Junto con el teorema del capítulo, ¿qué relación queda entre los dos lenguajes?
  9. Escriban la demostración de que ATMA_{\mathrm{TM}} es indecidible sin mirar los apuntes. Marquen el paso en que se usa que HH siempre se detiene, y expliquen qué pasaría con la máquina DD y la entrada ⟨D⟩\langle D \rangle si HH solo reconociera ATMA_{\mathrm{TM}}.
  10. Un lenguaje LL es reconocible y su complemento también. Les dan los archivos .tm de las dos máquinas. Describan el programa que decide LL usando tm.h. Después expliquen qué responde build/alternate si por error le pasan dos veces la misma máquina, y por qué eso no contradice el teorema.
  11. Digan si cada lenguaje es decidible, reconocible pero no decidible, o no reconocible, y justifiquen con los resultados del capítulo. (a) Los pares ⟨M,w⟩\langle M, w \rangle tales que MM acepta ww en a lo sumo 1000 pasos. (b) Los pares ⟨M,w⟩\langle M, w \rangle tales que MM no se detiene con ww. (c) Los pares ⟨A,w⟩\langle A, w \rangle tales que AA es un DFA que rechaza ww. (d) Las descripciones ⟨M⟩\langle M \rangle de máquinas de Turing con a lo sumo 5 estados.
  12. Un compañero dice que su programa detecta ciclos infinitos: recibe un programa y su entrada, y responde “termina” o “no termina”. Lo probó con mil programas y acertó en todos. Escriban una respuesta precisa de media página: qué puede ser cierto de lo que dice, qué no puede ser cierto, y cómo se construye, a partir de su programa, una entrada con la que falla.
  13. Para programar. Agreguen a universal.cpp una opción que detenga la simulación si se repite una configuración completa (estado, cinta y cabezal) y responda no se detiene: repite una configuración. Escriban una máquina con la que esa opción acierte y expliquen por qué con search_one.tm nunca se activa. ¿Su programa decide HALTTM\mathrm{HALT}_{\mathrm{TM}}? ¿Qué decide exactamente?