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

Apuntes · Capítulo 10Computabilidad

Reducciones

Reducciones

La semana 9 terminó con un resultado y con un método que no se puede repetir. El resultado: el lenguaje ATM={ ⟨M,w⟩:M acepta w }A_{\mathrm{TM}} = \{\, \langle M, w \rangle : M \text{ acepta } w \,\} es indecidible. El método fue la diagonalización: suponer un decididor HH, construir con él una máquina DD que hace lo contrario de lo que HH predice, y darle a DD su propia descripción. Funciona una vez. Si para cada problema nuevo hubiera que inventar una diagonal a medida, la lista de problemas indecidibles sería corta.

Esta semana la lista crece con una sola herramienta, que ya conocen de Algoritmos: la reducción. Allá servía para mostrar que un problema es NP-difícil. Aquí sirve para mostrar que un problema es indecidible, y el argumento tiene la misma forma: si BB se pudiera decidir, con ese decididor se decidiría ATMA_{\mathrm{TM}}, y eso ya sabemos que es imposible. Ninguna demostración de hoy vuelve a diagonalizar. Todas se apoyan en la de la semana 9.

La sesión A trata de problemas sobre máquinas de Turing: si una máquina se detiene, si su lenguaje es vacío, si es regular, si dos máquinas son equivalentes. Todos caen, y el teorema de Rice explica por qué: cualquier pregunta interesante sobre el lenguaje de una máquina es indecidible. En el camino hay que precisar qué es una reducción, porque con la definición precisa se obtienen también lenguajes que no son ni siquiera reconocibles.

La sesión B sale del mundo de las máquinas. El problema de correspondencia de Post habla de fichas con cadenas, y la pregunta de si una gramática genera todas las cadenas habla de gramáticas. Ninguno menciona una máquina de Turing y los dos son indecidibles. El puente es la historia de cómputo: la ejecución completa de una máquina, escrita como una cadena. Con ella se paga la deuda de la semana 9: decidir si dos gramáticas son equivalentes es imposible.

Ruta de lectura.

Antes de clase (15–20 minutos): la introducción, Reducir: la idea y la dirección y El problema de la parada, por reducción. Antes de la sesión B, Problemas que no hablan de máquinas e Historias de cómputo.

En clase: Sesión A, de Reducir: la idea y la dirección a Lo que Rice no dice. Sesión B, de Problemas que no hablan de máquinas a El contraste con los autómatas finitos.

Después de clase: el Resumen y los Ejercicios. Antes del laboratorio, El problema de correspondencia de Post, PCP es reconocible y El código de la semana. La sección PCP es indecidible es la más larga del capítulo: léanla con el programa tm_to_pcp al lado.

Lectura. Sipser, sec. 5.1 (Undecidable Problems from Language Theory), con su parte sobre computation histories, sec. 5.2 (A Simple Undecidable Problem) y sec. 5.3 (Mapping Reducibility). 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-10. 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/pcp_search.

Reducir: la idea y la dirección

Una reducción (reduction) de un problema AA a un problema BB es una manera de resolver AA usando una solución de BB. En Algoritmos lo hicieron muchas veces sin llamarlo así: para encontrar la mediana se puede ordenar, así que la mediana se reduce al ordenamiento. Y lo hicieron con nombre al final del curso, para mostrar que un problema es NP-difícil.

De una reducción de AA a BB se sacan dos conclusiones, que son la misma leída en los dos sentidos:

  • Si BB se puede resolver, entonces AA se puede resolver. Es el uso de todos los días: tengo una biblioteca que resuelve BB y la aprovecho.
  • Si AA no se puede resolver, entonces BB tampoco. Es el uso de esta semana.

“Resolver” quiere decir hoy decidir: tener una máquina de Turing que se detiene con toda entrada y responde bien. El punto de partida es el problema indecidible del que salen todos los demás, ATMA_{\mathrm{TM}}. Para demostrar que un problema BB es indecidible, el plan es siempre el mismo:

  1. Suponer que existe una máquina RR que decide BB.
  2. Construir, usando RR como subrutina, una máquina SS que decide ATMA_{\mathrm{TM}}.
  3. Como ATMA_{\mathrm{TM}} es indecidible, SS no puede existir. Entonces RR tampoco.

Más adelante el punto de partida podrá ser cualquier otro problema que ya se haya demostrado indecidible.

Idea clave. Para demostrar que BB es indecidible se reduce desde un problema indecidible conocido hacia BB. La reducción dice ”BB es al menos tan difícil como el conocido”. El problema conocido es el que se resuelve; el problema nuevo es el que se usa como subrutina.

La dirección es el error más frecuente del curso, así que vale la pena ver qué pasa cuando se invierte. Tomen un problema fácil: ADFAA_{\mathrm{DFA}}, decidir si un DFA BB acepta una cadena ww. Se reduce a ATMA_{\mathrm{TM}} sin esfuerzo: un DFA se convierte en una máquina de Turing MBM_B que lee la entrada de izquierda a derecha siguiendo las transiciones de BB, y BB acepta ww si y solo si MBM_B acepta ww. Si alguien nos diera un decididor de ATMA_{\mathrm{TM}}, decidiríamos ADFAA_{\mathrm{DFA}} con él. Todo eso es cierto, y no dice nada malo de ADFAA_{\mathrm{DFA}}, que es decidible: lo decidimos la semana pasada simulando.

Error común. Reducir en la dirección contraria. Reducir BB a ATMA_{\mathrm{TM}} solo muestra que BB no es más difícil que ATMA_{\mathrm{TM}}, y eso lo cumplen también los problemas más fáciles del curso. Para comprobar la dirección, pregúntense: ¿qué máquina estoy suponiendo que existe, y qué máquina construyo con ella? La que se supone es la del problema nuevo. La que se construye es la del problema que ya se sabe imposible.

Dos diagramas de bloques, uno sobre otro. Arriba, marcado como correcto: para demostrar que B es indecidible se va desde A_TM, el problema conocido, hacia B, el nuevo. Una entrada ⟨M, w⟩ de A_TM entra a una máquina S que construye con ella una entrada de B, se la pasa a R, un decididor de B dibujado con borde punteado porque solo se supone que existe, e interpreta su respuesta para aceptar o rechazar. S decidiría A_TM, lo cual es imposible, así que R no existe. Abajo, marcado como error: la dirección contraria. Una entrada de B se transforma en una entrada de A_TM y se le pasa a un decididor de A_TM, que ya se sabe que no existe; lo que se construye es un decididor de B, que puede existir, y no hay contradicción.Dos diagramas de bloques, uno sobre otro. Arriba, marcado como correcto: para demostrar que B es indecidible se va desde A_TM, el problema conocido, hacia B, el nuevo. Una entrada ⟨M, w⟩ de A_TM entra a una máquina S que construye con ella una entrada de B, se la pasa a R, un decididor de B dibujado con borde punteado porque solo se supone que existe, e interpreta su respuesta para aceptar o rechazar. S decidiría A_TM, lo cual es imposible, así que R no existe. Abajo, marcado como error: la dirección contraria. Una entrada de B se transforma en una entrada de A_TM y se le pasa a un decididor de A_TM, que ya se sabe que no existe; lo que se construye es un decididor de B, que puede existir, y no hay contradicción.
La máquina que se supone es la del problema nuevo, y la que se construye con ella es la del problema que ya se sabe imposible. Al revés no hay contradicción: así se reduce también un problema decidible como A_DFA.

Tres avisos sobre la forma de estas demostraciones, antes de la primera.

  • Son por contradicción. La máquina RR no existe, y aun así la usamos como si existiera, para llegar al absurdo. No hay que explicar cómo trabaja RR por dentro: solo se usa que se detiene siempre y que responde bien.
  • Las máquinas se describen en alto nivel, con el formato de la semana 9: pasos numerados, entre comillas. La primera línea dice la forma de la entrada, y una entrada que no tiene esa forma se rechaza.
  • Las máquinas construyen máquinas. Varios pasos dirán “construir la máquina M′M'”. Eso es escribir un texto: la descripción de M′M', hecha a partir de la descripción de MM. Es lo que hace un programa que genera código. Construir una máquina no es ejecutarla, y esa diferencia va a ser la clave de casi todo.

El problema de la parada, por reducción

El problema de la parada (halting problem) es el lenguaje

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

“Se detiene” incluye las dos formas: aceptando o rechazando. En la semana 9 lo demostramos como adelanto. Aquí la demostración se repite como primer ejemplo del plan de arriba.

Primero, el intento que no funciona, porque muestra qué es exactamente lo que falta. Para decidir ATMA_{\mathrm{TM}} uno quiere simular MM con ww y responder lo que MM responda. El intento falla en un solo caso: cuando MM no se detiene, la simulación tampoco, y nuestra máquina se queda sin responder. Si alguien nos avisara de antemano que MM no se va a detener, ese caso desaparece: respondemos “rechazar” sin simular. Un decididor de HALTTM\mathrm{HALT}_{\mathrm{TM}} es justo ese aviso.

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

Demostración. Por reducción desde ATMA_{\mathrm{TM}} hacia HALTTM\mathrm{HALT}_{\mathrm{TM}}. Esa es la dirección que sirve porque ATMA_{\mathrm{TM}} es el problema que ya sabemos indecidible: vamos a mostrar que un decididor de HALTTM\mathrm{HALT}_{\mathrm{TM}} permitiría decidirlo.

Supongamos, para llegar a una contradicción, que una máquina RR decide HALTTM\mathrm{HALT}_{\mathrm{TM}}. Construimos 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 se detiene siempre. El paso 1 termina porque RR es un decididor. El paso 3 solo se ejecuta cuando RR aceptó, es decir, cuando MM se detiene con ww: la simulación termina.

SS responde bien, en las dos direcciones. Si MM acepta ww, entonces MM se detiene con ww, RR acepta, la simulación del paso 3 termina con MM aceptando, y SS acepta. Si MM no acepta ww, hay dos casos. Si MM no se detiene con ww, RR rechaza y SS rechaza en el paso 2. Si MM se detiene rechazando, RR acepta, la simulación termina con MM rechazando, y SS rechaza en el paso 4.

Entonces SS decide ATMA_{\mathrm{TM}}, que es indecidible. La contradicción viene de suponer que RR existe. ∎

Hay que mirar dónde está el cuidado. SS simula a MM, y simular es peligroso. Lo hace solo después de que RR garantizó que la simulación termina. Si los pasos 1 y 3 se cambiaran de orden, SS no sería un decididor.

En la práctica. Por eso ningún compilador avisa “este programa nunca termina” con certeza en todos los casos. Las herramientas que buscan ciclos infinitos existen y son útiles, pero responden con tres valores: “termina”, “no termina” y “no sé”. La tercera respuesta no es un defecto de la herramienta que se arregle con más trabajo.

Fijar la entrada dentro de la máquina: E_TM

El segundo problema pregunta por el lenguaje completo de una máquina, y ya no por una sola entrada:

ETM={ ⟨M⟩:M es una maˊquina de Turing y L(M)=∅ }.E_{\mathrm{TM}} = \{\, \langle M \rangle : M \text{ es una máquina de Turing y } L(M) = \emptyset \,\}.

Para los DFA la pregunta era fácil: EDFAE_{\mathrm{DFA}} se decide viendo si algún estado de aceptación es alcanzable en el diagrama. Para las gramáticas también. Para las máquinas de Turing, el diagrama no alcanza: que un estado se pueda alcanzar depende de lo que haya en la cinta, y la cinta no tiene límite.

La reducción tiene que salir de ATMA_{\mathrm{TM}}, y aquí aparece una dificultad nueva. Una instancia de ATMA_{\mathrm{TM}} es un par ⟨M,w⟩\langle M, w \rangle: una máquina y una entrada. Una instancia de ETME_{\mathrm{TM}} es solo una máquina. Hay que meter ww en algún sitio, y el único sitio es dentro de la máquina.

La máquina M_w

Dados MM y ww, se construye una máquina nueva, que llamamos MwM_w:

M_w = "Con la entrada x:
  1. Si x ≠ w, rechazar.
  2. Si x = w, correr M con la entrada w. Si M acepta, aceptar."

La cadena ww no es una entrada de MwM_w: está escrita en su tabla de transiciones, como una constante en un programa. La única cadena que MwM_w puede llegar a aceptar es ww, y la acepta exactamente cuando MM la acepta:

L(Mw)={{w}si M acepta w,∅si M no acepta w.L(M_w) = \begin{cases} \{w\} & \text{si } M \text{ acepta } w, \\ \emptyset & \text{si } M \text{ no acepta } w. \end{cases}

Si MM no se detiene con ww, entonces MwM_w tampoco se detiene con ww. No importa: una cadena con la que la máquina no se detiene no está en su lenguaje, y L(Mw)=∅L(M_w) = \emptyset igual.

La pregunta “¿acepta MM a ww?” quedó convertida en “¿es vacío el lenguaje de MwM_w?”.

Diagrama de la máquina M_w y de su lenguaje. Arriba, M_w por dentro: recibe una entrada x cualquiera y pregunta si x es igual a w; si no lo es, rechaza; si lo es, corre M con la entrada w y acepta cuando M acepta. Una nota dice que si M rechaza o no se detiene, M_w no acepta. Abajo, los dos casos: si M acepta w, el lenguaje de M_w es el conjunto que solo contiene a w, no es vacío y ⟨M_w⟩ no está en E_TM; si M no acepta w, también cuando no se detiene, el lenguaje de M_w es vacío y ⟨M_w⟩ está en E_TM.Diagrama de la máquina M_w y de su lenguaje. Arriba, M_w por dentro: recibe una entrada x cualquiera y pregunta si x es igual a w; si no lo es, rechaza; si lo es, corre M con la entrada w y acepta cuando M acepta. Una nota dice que si M rechaza o no se detiene, M_w no acepta. Abajo, los dos casos: si M acepta w, el lenguaje de M_w es el conjunto que solo contiene a w, no es vacío y ⟨M_w⟩ no está en E_TM; si M no acepta w, también cuando no se detiene, el lenguaje de M_w es vacío y ⟨M_w⟩ está en E_TM.
La cadena w está escrita dentro de M_w, y el lenguaje de M_w es {w} o vacío según M acepte o no a w. La respuesta sale invertida: M acepta w exactamente cuando ⟨M_w⟩ no está en E_TM.

La construcción es un programa

Pasar de ⟨M,w⟩\langle M, w \rangle a ⟨Mw⟩\langle M_w \rangle es un trabajo mecánico sobre texto, y el programa fix_input lo hace con los archivos .tm del curso. La máquina machines/starts_01.tm acepta las cadenas binarias que empiezan con 01\mathtt{01}:

# Acepta las cadenas que empiezan con 01. Mira el segundo símbolo y vuelve al primero,
# para tener un movimiento a la izquierda en una historia corta.
states: q0 q1 q2 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q1 0 R
q1 1 -> q2 1 L
q2 0 -> q_accept 0 R

Con w=01w = \mathtt{01}, esta es MwM_w:

$ build/fix_input machines/starts_01.tm 01
# M_w para M = machines/starts_01.tm y w = 01.
# Con la entrada x: si x no es w, rechaza; si lo es, corre M con w.
states: c0 c1 c2 back m.q0 m.q1 m.q2 m.q_accept m.q_reject
alphabet: 0 1
tape: 0 1 _ @
start: c0
accept: m.q_accept
reject: m.q_reject
delta:
c0 0 -> c1 @ R
c1 1 -> c2 1 R
c2 _ -> back _ L
back 0 -> back 0 L
back 1 -> back 1 L
back @ -> m.q0 0 L
m.q0 0 -> m.q1 0 R
m.q1 1 -> m.q2 1 L
m.q2 0 -> m.q_accept 0 R

Los estados c0, c1, c2 comparan la entrada con 01\mathtt{01} símbolo por símbolo: la cadena ww está en esas tres líneas. El primer símbolo se cambia por la marca @ para poder encontrar después el principio de la cinta. El estado back vuelve hasta la marca, restaura el símbolo y entrega el control al estado inicial de MM, cuyos estados aparecen con el prefijo m.. La última transición de back se mueve a la izquierda desde la primera celda, y por la convención del formato el cabezal se queda ahí. Cualquier diferencia entre xx y ww cae en un par sin transición, que lleva a rechazar.

test_fix_input comprueba la fórmula de L(Mw)L(M_w) con cuatro máquinas y las 31 cadenas ww de longitud a lo sumo 4: corre cada MwM_w con las 63 cadenas xx de longitud a lo sumo 5, y MwM_w rechaza toda x≠wx \neq w y hace con ww lo mismo que MM.

Idea clave. El programa fix_input no ejecuta a MM. Lee su descripción y escribe otra. Termina siempre, también cuando MM es una máquina que no se detiene nunca. Las reducciones de esta semana trabajan así: transforman descripciones de máquinas sin correrlas.

La demostración

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

Demostración. Por reducción desde ATMA_{\mathrm{TM}} hacia ETME_{\mathrm{TM}}: mostramos que un decididor de ETME_{\mathrm{TM}} permitiría decidir ATMA_{\mathrm{TM}}, que es el problema que ya sabemos indecidible.

Supongamos que RR decide ETME_{\mathrm{TM}}. Construimos SS:

S = "Con la entrada ⟨M, w⟩, donde M es una máquina de Turing y w una cadena:
  1. Construir la descripción de la máquina M_w de arriba.
  2. Correr R con la entrada ⟨M_w⟩.
  3. Si R acepta, rechazar. Si R rechaza, aceptar."

SS se detiene siempre. El paso 1 es escribir un texto y termina. El paso 2 termina porque RR es un decididor. SS nunca corre MM ni MwM_w.

SS responde bien. Si MM acepta ww, entonces L(Mw)={w}≠∅L(M_w) = \{w\} \neq \emptyset, así que RR rechaza ⟨Mw⟩\langle M_w \rangle y SS acepta. Si MM no acepta ww, entonces L(Mw)=∅L(M_w) = \emptyset, así que RR acepta ⟨Mw⟩\langle M_w \rangle y SS rechaza.

SS decide ATMA_{\mathrm{TM}}: contradicción. ∎

Noten el paso 3: SS responde lo contrario de RR. No hay problema en eso. Si un lenguaje es decidible, su complemento también, porque basta intercambiar las respuestas. Para hablar de lo decidible, un problema y su complemento valen lo mismo. Para hablar de lo reconocible no, y por eso dentro de tres secciones habrá que mirar esa inversión con más cuidado.

Error común. Escribir en SS el paso “correr MwM_w con todas las cadenas y ver si acepta alguna”. Eso no termina: hay infinitas cadenas, y con alguna MwM_w puede no detenerse. Lo único que SS hace con MwM_w es pasarle su descripción a RR.

REGULAR_TM y EQ_TM

La misma técnica, fijar ww dentro de una máquina construida a medida, resuelve dos problemas más. Lo que cambia es qué hace la máquina nueva con su propia entrada.

¿Es regular el lenguaje de una máquina?

REGULARTM={ ⟨M⟩:M es una maˊquina de Turing y L(M) es regular }.\mathrm{REGULAR}_{\mathrm{TM}} = \{\, \langle M \rangle : M \text{ es una máquina de Turing y } L(M) \text{ es regular} \,\}.

La pregunta tiene sentido práctico: si el lenguaje de un programa es regular, se podría reemplazar el programa por un autómata finito, que usa memoria constante.

Queremos una máquina M2M_2, construida a partir de MM y ww, cuyo lenguaje sea regular exactamente cuando MM acepta ww. La idea es darle a M2M_2 dos lenguajes posibles, uno regular y otro no, y dejar que MM con ww elija cuál. El lenguaje no regular más conocido del curso es { 0n1n:n≥0 }\{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\}, de la semana 4. El regular más simple es Σ∗\Sigma^*.

M_2 = "Con la entrada x:
  1. Si x tiene la forma 0ⁿ1ⁿ, aceptar.
  2. Si no, correr M con la entrada w. Si M acepta, aceptar."

M2M_2 acepta siempre las cadenas de la forma 0n1n\mathtt{0}^n\mathtt{1}^n, sin mirar a MM. Con las demás, hace lo que MM haga con ww, que es lo mismo para todas porque no depende de xx:

L(M2)={Σ∗si M acepta w,{ 0n1n:n≥0 }si M no acepta w.L(M_2) = \begin{cases} \Sigma^* & \text{si } M \text{ acepta } w, \\ \{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\} & \text{si } M \text{ no acepta } w. \end{cases}

Teorema. REGULARTM\mathrm{REGULAR}_{\mathrm{TM}} es indecidible.

Demostración. Por reducción desde ATMA_{\mathrm{TM}} hacia REGULARTM\mathrm{REGULAR}_{\mathrm{TM}}, porque ATMA_{\mathrm{TM}} es el que ya sabemos indecidible. Supongamos que RR decide REGULARTM\mathrm{REGULAR}_{\mathrm{TM}}, y sea SS:

S = "Con la entrada ⟨M, w⟩, donde M es una máquina de Turing y w una cadena:
  1. Construir la descripción de la máquina M_2 de arriba.
  2. Correr R con la entrada ⟨M_2⟩.
  3. Si R acepta, aceptar. Si R rechaza, rechazar."

SS se detiene siempre: escribe una descripción y corre un decididor. Si MM acepta ww, entonces L(M2)=Σ∗L(M_2) = \Sigma^*, que es regular, RR acepta y SS acepta. Si MM no acepta ww, entonces L(M2)={ 0n1n }L(M_2) = \{\, \mathtt{0}^n\mathtt{1}^n \,\}, que no es regular, RR rechaza y SS rechaza. Así SS decide ATMA_{\mathrm{TM}}: contradicción. ∎

Dos detalles de M2M_2 que suelen confundir.

  • M2M_2 sí se detiene en el paso 1: comprobar la forma 0n1n\mathtt{0}^n\mathtt{1}^n es decidible, lo hace la máquina de la semana 7. Pero aunque no se detuviera en algún paso, daría igual: M2M_2 no se ejecuta en ningún momento de la demostración. Solo importa cuál es su lenguaje.
  • El caso en que MM no se detiene con ww está cubierto. Entonces M2M_2 no se detiene con ninguna xx que no tenga la forma 0n1n\mathtt{0}^n\mathtt{1}^n, no las acepta, y su lenguaje es { 0n1n }\{\, \mathtt{0}^n\mathtt{1}^n \,\}.

El mismo esquema, cambiando los dos lenguajes, demuestra que es indecidible si L(M)L(M) es libre de contexto, si es finito, si es decidible. El teorema de Rice, más abajo, los resuelve todos de una vez.

¿Son equivalentes dos máquinas?

EQTM={ ⟨M1,M2⟩:M1 y M2 son maˊquinas de Turing y L(M1)=L(M2) }.\mathrm{EQ}_{\mathrm{TM}} = \{\, \langle M_1, M_2 \rangle : M_1 \text{ y } M_2 \text{ son máquinas de Turing y } L(M_1) = L(M_2) \,\}.

Aquí conviene no partir de ATMA_{\mathrm{TM}}. Ya tenemos otro problema indecidible que se parece mucho más: ETME_{\mathrm{TM}} pregunta si el lenguaje de una máquina es vacío, y eso es preguntar si la máquina es equivalente a una que no acepta nada.

Teorema. EQTM\mathrm{EQ}_{\mathrm{TM}} es indecidible.

Demostración. Por reducción desde ETME_{\mathrm{TM}} hacia EQTM\mathrm{EQ}_{\mathrm{TM}}. La dirección sirve porque ETME_{\mathrm{TM}} ya está demostrado indecidible: un decididor de EQTM\mathrm{EQ}_{\mathrm{TM}} permitiría decidirlo.

Sea M∅M_\emptyset una máquina fija que rechaza toda entrada, de modo que L(M∅)=∅L(M_\emptyset) = \emptyset. Supongamos que RR decide EQTM\mathrm{EQ}_{\mathrm{TM}}, y sea SS:

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

SS se detiene siempre. Si L(M)=∅L(M) = \emptyset, entonces L(M)=L(M∅)L(M) = L(M_\emptyset), RR acepta y SS acepta. Si L(M)≠∅L(M) \neq \emptyset, entonces L(M)≠L(M∅)L(M) \neq L(M_\emptyset), RR rechaza y SS rechaza. SS decide ETME_{\mathrm{TM}}: contradicción. ∎

Las reducciones se encadenan. ATMA_{\mathrm{TM}} se redujo a ETME_{\mathrm{TM}}, y ETME_{\mathrm{TM}} a EQTM\mathrm{EQ}_{\mathrm{TM}}. Cada problema que se demuestra indecidible es un punto de partida nuevo, y se elige el que más se parezca al que se quiere atacar.

En la práctica. EQTM\mathrm{EQ}_{\mathrm{TM}} es el problema de quien refactoriza: ¿el programa nuevo hace lo mismo que el viejo? Ningún algoritmo lo responde para todos los pares de programas. Por eso existen las pruebas, que comparan los dos programas en algunas entradas, y por eso un optimizador de compilador solo aplica transformaciones que se demostraron correctas una por una.

Reducción por función

Hasta aquí “reducir” fue una idea: usar un decididor como subrutina. En las cuatro demostraciones, la subrutina se usó de la manera más simple posible: SS transformó su entrada en otra, llamó a RR una sola vez con ella, y respondió lo mismo que RR o lo contrario. Esa forma tiene nombre y definición, y vale la pena aislarla porque dice más que la idea general.

Definición. Una función f ⁣:Σ∗→Σ∗f \colon \Sigma^* \to \Sigma^* es computable (computable function) si alguna máquina de Turing, con cada entrada ww, se detiene dejando en la cinta exactamente f(w)f(w).

Una función computable es un programa que siempre termina y que transforma texto en texto. Las operaciones aritméticas lo son. Lo que nos interesa: transformar la descripción de una máquina en la de otra es computable. fix_input calcula la función ⟨M,w⟩↦⟨Mw⟩\langle M, w \rangle \mapsto \langle M_w \rangle.

Definición. Un lenguaje AA es reducible por función (mapping reducible) a un lenguaje BB, y se escribe A≤mBA \leq_m B, si existe una función computable ff tal que, para toda cadena ww,

w∈A  ⟺  f(w)∈B.w \in A \iff f(w) \in B.

La función ff es la reducción de AA a BB.

        A                    B
  ┌───────────┐   f    ┌───────────┐
  │   w ∈ A   │ ─────► │ f(w) ∈ B  │
  ├───────────┤        ├───────────┤
  │   w ∉ A   │ ─────► │ f(w) ∉ B  │
  └───────────┘        └───────────┘

Tres observaciones sobre la definición.

  • El “si y solo si” son dos condiciones. Las cadenas de AA van a parar dentro de BB, y las que no están en AA van a parar fuera de BB. Una función que cumple solo la primera no sirve: la función constante que manda todo a una cadena fija de BB la cumple.
  • ff no tiene que ser inyectiva ni sobreyectiva. Puede mandar muchas cadenas a la misma, y puede no tocar casi nada de BB.
  • ff tiene que estar definida para toda cadena, también para las que no son la codificación de nada. Si AA es un lenguaje de pares ⟨M,w⟩\langle M, w \rangle y la entrada no tiene esa forma, la entrada no está en AA, y ff la manda a alguna cadena fija que no esté en BB. En adelante no lo repetimos.

La notación ≤m\leq_m se lee como una comparación de dificultad: A≤mBA \leq_m B dice que AA no es más difícil que BB. Igual que con los números, sirve en los dos sentidos.

Qué conserva

Teorema. Si A≤mBA \leq_m B y BB es decidible, entonces AA es decidible.

Demostración. Por construcción. Sea MM un decididor de BB y ff la reducción. La máquina

N = "Con la entrada w:
  1. Calcular f(w).
  2. Correr M con la entrada f(w). Responder lo mismo que M."

se detiene siempre, porque ff es computable y MM es un decididor. Y acepta ww si y solo si MM acepta f(w)f(w), si y solo si f(w)∈Bf(w) \in B, si y solo si w∈Aw \in A. ∎

Corolario. Si A≤mBA \leq_m B y AA es indecidible, entonces BB es indecidible.

Demostración. Es el contrarrecíproco del teorema: si BB fuera decidible, AA lo sería. ∎

Teorema. Si A≤mBA \leq_m B y BB es reconocible, entonces AA es reconocible.

Demostración. La misma máquina NN, con MM ahora un reconocedor de BB. Si w∈Aw \in A, entonces f(w)∈Bf(w) \in B, MM acepta f(w)f(w) y NN acepta ww. Si w∉Aw \notin A, entonces f(w)∉Bf(w) \notin B y MM no acepta f(w)f(w): rechaza o no se detiene, y NN hace lo mismo. En los dos casos NN acepta exactamente las cadenas de AA. ∎

Corolario. Si A≤mBA \leq_m B y AA no es reconocible, entonces BB no es reconocible.

Demostración. El contrarrecíproco del teorema anterior. ∎

Si A≤mBA \leq_m B y… entonces… Se usa para
BB es decidible AA es decidible resolver AA
AA es indecidible BB es indecidible las demostraciones de esta semana
BB es reconocible AA es reconocible reconocer AA
AA no es reconocible BB no es reconocible la sección siguiente

En la tabla, lo bueno baja de BB hacia AA y lo malo sube de AA hacia BB. Si la conclusión que están escribiendo va en otro sentido, la reducción está al revés.

Dos propiedades más, que se usan todo el tiempo.

Los complementos. A≤mBA \leq_m B si y solo si A‾≤mB‾\overline{A} \leq_m \overline{B}, con la misma función. La condición w∈A  ⟺  f(w)∈Bw \in A \iff f(w) \in B dice lo mismo que w∉A  ⟺  f(w)∉Bw \notin A \iff f(w) \notin B, que es w∈A‾  ⟺  f(w)∈B‾w \in \overline{A} \iff f(w) \in \overline{B}.

La transitividad. Si A≤mBA \leq_m B con ff y B≤mCB \leq_m C con gg, entonces A≤mCA \leq_m C con la composición w↦g(f(w))w \mapsto g(f(w)), que es computable: w∈A  ⟺  f(w)∈B  ⟺  g(f(w))∈Cw \in A \iff f(w) \in B \iff g(f(w)) \in C.

Las reducciones anteriores, vistas como funciones

  • ATM≤mHALTTMA_{\mathrm{TM}} \leq_m \mathrm{HALT}_{\mathrm{TM}}. La función manda ⟨M,w⟩\langle M, w \rangle a ⟨M′,w⟩\langle M', w \rangle, donde M′M' es MM con un cambio: cuando MM rechazaría, M′M' entra en un ciclo sin fin.

    M' = "Con la entrada x:
      1. Correr M con la entrada x.
      2. Si M acepta, aceptar. Si M rechaza, moverse a la derecha para siempre."

    Si MM acepta ww, M′M' se detiene con ww. Si MM no acepta ww, sea porque rechaza o porque no se detiene, M′M' no se detiene con ww. Entonces ⟨M,w⟩∈ATM  ⟺  ⟨M′,w⟩∈HALTTM\langle M, w \rangle \in A_{\mathrm{TM}} \iff \langle M', w \rangle \in \mathrm{HALT}_{\mathrm{TM}}.

  • ATM≤mREGULARTMA_{\mathrm{TM}} \leq_m \mathrm{REGULAR}_{\mathrm{TM}}, con f(⟨M,w⟩)=⟨M2⟩f(\langle M, w \rangle) = \langle M_2 \rangle. La máquina SS de esa demostración respondía lo mismo que RR.

  • ETM≤mEQTME_{\mathrm{TM}} \leq_m \mathrm{EQ}_{\mathrm{TM}}, con f(⟨M⟩)=⟨M,M∅⟩f(\langle M \rangle) = \langle M, M_\emptyset \rangle.

  • ATM≤mETM‾A_{\mathrm{TM}} \leq_m \overline{E_{\mathrm{TM}}}, con f(⟨M,w⟩)=⟨Mw⟩f(\langle M, w \rangle) = \langle M_w \rangle. Aquí está la inversión del paso 3: MM acepta ww si y solo si L(Mw)L(M_w) no es vacío. La función lleva ATMA_{\mathrm{TM}} al complemento de ETME_{\mathrm{TM}}, y no a ETME_{\mathrm{TM}}.

El último caso merece una pausa. ¿Existirá otra función, más ingeniosa, que dé ATM≤mETMA_{\mathrm{TM}} \leq_m E_{\mathrm{TM}}? No existe ninguna, y se puede demostrar.

  • ETM‾\overline{E_{\mathrm{TM}}} es reconocible. Una máquina con la entrada ⟨M⟩\langle M \rangle busca una cadena que MM acepte. No puede probar las cadenas una tras otra, porque MM puede no detenerse con la primera. Las prueba en paralelo: para i=1,2,3,…i = 1, 2, 3, \ldots, corre MM durante ii pasos con cada una de las primeras ii cadenas de Σ∗\Sigma^*, y acepta si alguna de esas ejecuciones acepta. Si L(M)≠∅L(M) \neq \emptyset, alguna cadena se acepta en algún número de pasos, y la búsqueda llega hasta ahí.
  • Si fuera ATM≤mETMA_{\mathrm{TM}} \leq_m E_{\mathrm{TM}}, por la propiedad de los complementos sería ATM‾≤mETM‾\overline{A_{\mathrm{TM}}} \leq_m \overline{E_{\mathrm{TM}}}, y como ETM‾\overline{E_{\mathrm{TM}}} es reconocible, ATM‾\overline{A_{\mathrm{TM}}} lo sería. En la semana 9 vimos que no lo es.

Así que la reducción general, la de “usar un decididor como subrutina”, permite invertir la respuesta, y la reducción por función no. Para demostrar que algo es indecidible, la diferencia no importa. Para demostrar que algo no es reconocible, es todo lo que importa.

De paso salió un resultado nuevo. De ATM≤mETM‾A_{\mathrm{TM}} \leq_m \overline{E_{\mathrm{TM}}} se obtiene ATM‾≤mETM\overline{A_{\mathrm{TM}}} \leq_m E_{\mathrm{TM}}, y como ATM‾\overline{A_{\mathrm{TM}}} no es reconocible:

Corolario. ETME_{\mathrm{TM}} no es reconocible.

Tiene sentido: para convencerse de que una máquina sí acepta algo basta encontrar una cadena, y para convencerse de que no acepta nada no hay una búsqueda finita que alcance.

Error común. Leer A≤mBA \leq_m B como “se puede pasar de AA a BB y de BB a AA”. La reducción no es simétrica. ADFA≤mATMA_{\mathrm{DFA}} \leq_m A_{\mathrm{TM}} es cierto, y ATM≤mADFAA_{\mathrm{TM}} \leq_m A_{\mathrm{DFA}} es falso: si fuera cierto, ATMA_{\mathrm{TM}} sería decidible.

EQ_TM no es reconocible, y su complemento tampoco

En la semana 9 el mapa tenía tres regiones: los lenguajes decidibles; los reconocibles que no son decidibles, como ATMA_{\mathrm{TM}}; y los que no son reconocibles pero tienen complemento reconocible, como ATM‾\overline{A_{\mathrm{TM}}}. Queda una cuarta región: lenguajes en los que ni las respuestas “sí” ni las respuestas “no” se pueden confirmar con una búsqueda. EQTM\mathrm{EQ}_{\mathrm{TM}} está ahí.

La herramienta es el último corolario: si AA no es reconocible y A≤mBA \leq_m B, entonces BB no es reconocible. El lenguaje no reconocible que tenemos es ATM‾\overline{A_{\mathrm{TM}}}. Hay que reducirlo dos veces: una hacia EQTM\mathrm{EQ}_{\mathrm{TM}} y otra hacia EQTM‾\overline{\mathrm{EQ}_{\mathrm{TM}}}.

Teorema. EQTM\mathrm{EQ}_{\mathrm{TM}} no es reconocible, y EQTM‾\overline{\mathrm{EQ}_{\mathrm{TM}}} tampoco.

Demostración. Dos reducciones por función desde ATM‾\overline{A_{\mathrm{TM}}}. Es la dirección que sirve porque ATM‾\overline{A_{\mathrm{TM}}} es el lenguaje que ya sabemos que no es reconocible, y lo no reconocible sube de AA hacia BB.

Las dos usan la misma máquina auxiliar, que ignora su entrada y corre MM con ww:

M_2 = "Con cualquier entrada x:
  1. Correr M con la entrada w. Si M acepta, aceptar."

Su lenguaje es Σ∗\Sigma^* si MM acepta ww, y ∅\emptyset si no.

Primera parte: EQTM\mathrm{EQ}_{\mathrm{TM}} no es reconocible. Queremos ATM‾≤mEQTM\overline{A_{\mathrm{TM}}} \leq_m \mathrm{EQ}_{\mathrm{TM}}. Por la propiedad de los complementos, es lo mismo que ATM≤mEQTM‾A_{\mathrm{TM}} \leq_m \overline{\mathrm{EQ}_{\mathrm{TM}}}, que es más cómodo de escribir: hay que mandar ⟨M,w⟩\langle M, w \rangle a un par de máquinas que sean distintas exactamente cuando MM acepta ww. La función es

f(⟨M,w⟩)=⟨M1,M2⟩,con M1=“Con cualquier entrada: rechazar.”f(\langle M, w \rangle) = \langle M_1, M_2 \rangle, \qquad \text{con } M_1 = \text{“Con cualquier entrada: rechazar.”}

L(M1)=∅L(M_1) = \emptyset siempre. Si MM acepta ww, entonces L(M2)=Σ∗≠∅=L(M1)L(M_2) = \Sigma^* \neq \emptyset = L(M_1), y el par no está en EQTM\mathrm{EQ}_{\mathrm{TM}}. Si MM no acepta ww, entonces L(M2)=∅=L(M1)L(M_2) = \emptyset = L(M_1), y el par está en EQTM\mathrm{EQ}_{\mathrm{TM}}. Es decir,

⟨M,w⟩∈ATM  ⟺  f(⟨M,w⟩)∈EQTM‾,\langle M, w \rangle \in A_{\mathrm{TM}} \iff f(\langle M, w \rangle) \in \overline{\mathrm{EQ}_{\mathrm{TM}}},

que es ATM≤mEQTM‾A_{\mathrm{TM}} \leq_m \overline{\mathrm{EQ}_{\mathrm{TM}}}, y por lo tanto ATM‾≤mEQTM\overline{A_{\mathrm{TM}}} \leq_m \mathrm{EQ}_{\mathrm{TM}}. Como ATM‾\overline{A_{\mathrm{TM}}} no es reconocible, EQTM\mathrm{EQ}_{\mathrm{TM}} no es reconocible.

Segunda parte: EQTM‾\overline{\mathrm{EQ}_{\mathrm{TM}}} no es reconocible. Queremos ATM‾≤mEQTM‾\overline{A_{\mathrm{TM}}} \leq_m \overline{\mathrm{EQ}_{\mathrm{TM}}}, que es lo mismo que ATM≤mEQTMA_{\mathrm{TM}} \leq_m \mathrm{EQ}_{\mathrm{TM}}: ahora las dos máquinas tienen que ser equivalentes exactamente cuando MM acepta ww. Se cambia solo M1M_1:

g(⟨M,w⟩)=⟨M1,M2⟩,con M1=“Con cualquier entrada: aceptar.”g(\langle M, w \rangle) = \langle M_1, M_2 \rangle, \qquad \text{con } M_1 = \text{“Con cualquier entrada: aceptar.”}

Ahora L(M1)=Σ∗L(M_1) = \Sigma^* siempre. Si MM acepta ww, entonces L(M2)=Σ∗=L(M1)L(M_2) = \Sigma^* = L(M_1) y el par está en EQTM\mathrm{EQ}_{\mathrm{TM}}. Si MM no acepta ww, entonces L(M2)=∅≠Σ∗L(M_2) = \emptyset \neq \Sigma^* y el par no está. Es decir,

⟨M,w⟩∈ATM  ⟺  g(⟨M,w⟩)∈EQTM,\langle M, w \rangle \in A_{\mathrm{TM}} \iff g(\langle M, w \rangle) \in \mathrm{EQ}_{\mathrm{TM}},

que es ATM≤mEQTMA_{\mathrm{TM}} \leq_m \mathrm{EQ}_{\mathrm{TM}}, y por lo tanto ATM‾≤mEQTM‾\overline{A_{\mathrm{TM}}} \leq_m \overline{\mathrm{EQ}_{\mathrm{TM}}}. Como ATM‾\overline{A_{\mathrm{TM}}} no es reconocible, EQTM‾\overline{\mathrm{EQ}_{\mathrm{TM}}} no es reconocible. ∎

Para no perderse con las barras, esta tabla resume las dos partes:

Parte M1M_1 Si MM acepta ww Lo que se obtiene Conclusión
Primera rechaza todo las máquinas difieren ATM≤mEQTM‾A_{\mathrm{TM}} \leq_m \overline{\mathrm{EQ}_{\mathrm{TM}}} EQTM\mathrm{EQ}_{\mathrm{TM}} no es reconocible
Segunda acepta todo las máquinas coinciden ATM≤mEQTMA_{\mathrm{TM}} \leq_m \mathrm{EQ}_{\mathrm{TM}} EQTM‾\overline{\mathrm{EQ}_{\mathrm{TM}}} no es reconocible

La regla para leerla: si ATM≤mXA_{\mathrm{TM}} \leq_m X, entonces ATM‾≤mX‾\overline{A_{\mathrm{TM}}} \leq_m \overline{X}, y el lenguaje que queda sin reconocedor es X‾\overline{X}, el complemento del que aparece a la derecha de ATMA_{\mathrm{TM}}.

El mapa de la semana 9, con lo que se agregó hoy:

Región Ejemplos
Decidibles ADFAA_{\mathrm{DFA}}, EDFAE_{\mathrm{DFA}}, EQDFA\mathrm{EQ}_{\mathrm{DFA}}, ACFGA_{\mathrm{CFG}}, ECFGE_{\mathrm{CFG}}
Reconocibles, no decidibles ATMA_{\mathrm{TM}}, HALTTM\mathrm{HALT}_{\mathrm{TM}}, ETM‾\overline{E_{\mathrm{TM}}}
No reconocibles, con complemento reconocible ATM‾\overline{A_{\mathrm{TM}}}, HALTTM‾\overline{\mathrm{HALT}_{\mathrm{TM}}}, ETME_{\mathrm{TM}}
Ni reconocibles ni con complemento reconocible EQTM\mathrm{EQ}_{\mathrm{TM}}, EQTM‾\overline{\mathrm{EQ}_{\mathrm{TM}}}
Mapa de las cuatro regiones dentro del rectángulo de todos los lenguajes sobre Σ. Dos conjuntos se cruzan: a la izquierda los reconocibles y a la derecha los correconocibles; el cruce son los decidibles, con A_DFA, E_DFA, EQ_DFA, A_CFG y E_CFG. En la parte de los reconocibles que no son decidibles están A_TM, HALT_TM y el complemento de E_TM. En la parte de los correconocibles que no son reconocibles están el complemento de A_TM, el complemento de HALT_TM y E_TM. Fuera de los dos conjuntos, ni reconocibles ni con complemento reconocible, están EQ_TM y su complemento. Un anillo marca los cuatro lenguajes que se agregaron esta semana: E_TM, su complemento, EQ_TM y su complemento.Mapa de las cuatro regiones dentro del rectángulo de todos los lenguajes sobre Σ. Dos conjuntos se cruzan: a la izquierda los reconocibles y a la derecha los correconocibles; el cruce son los decidibles, con A_DFA, E_DFA, EQ_DFA, A_CFG y E_CFG. En la parte de los reconocibles que no son decidibles están A_TM, HALT_TM y el complemento de E_TM. En la parte de los correconocibles que no son reconocibles están el complemento de A_TM, el complemento de HALT_TM y E_TM. Fuera de los dos conjuntos, ni reconocibles ni con complemento reconocible, están EQ_TM y su complemento. Un anillo marca los cuatro lenguajes que se agregaron esta semana: E_TM, su complemento, EQ_TM y su complemento.
El mapa con las cuatro regiones. Un lenguaje y su complemento caen en lados opuestos, como E_TM, o los dos adentro del cruce, o los dos afuera, como EQ_TM.

Que HALTTM\mathrm{HALT}_{\mathrm{TM}} es reconocible se ve igual que con ATMA_{\mathrm{TM}}: se simula MM con ww y se acepta cuando la simulación se detiene.

El teorema de Rice

Las demostraciones de ETME_{\mathrm{TM}} y de REGULARTM\mathrm{REGULAR}_{\mathrm{TM}} tienen el mismo esqueleto: se construye una máquina cuyo lenguaje es uno de dos, según MM acepte o no ww, y los dos lenguajes se eligen para que uno tenga la propiedad que se pregunta y el otro no. Nada en ese esqueleto depende de que la propiedad sea “ser vacío” o “ser regular”. El teorema de Rice lo dice de una vez para todas las propiedades.

Hay que precisar qué es una propiedad. Una pregunta de sí o no sobre máquinas de Turing es un lenguaje PP: el conjunto de las descripciones ⟨M⟩\langle M \rangle de las máquinas para las que la respuesta es sí.

Definición. Sea PP un lenguaje formado por descripciones de máquinas de Turing.

  • PP es una propiedad del lenguaje si depende solo del lenguaje que la máquina reconoce: siempre que L(M1)=L(M2)L(M_1) = L(M_2), se tiene ⟨M1⟩∈P\langle M_1 \rangle \in P si y solo si ⟨M2⟩∈P\langle M_2 \rangle \in P.
  • PP es no trivial (nontrivial property) si alguna máquina la tiene y alguna no: existen M1M_1 y M2M_2 con ⟨M1⟩∈P\langle M_1 \rangle \in P y ⟨M2⟩∉P\langle M_2 \rangle \notin P.

Teorema de Rice. Toda propiedad no trivial del lenguaje de una máquina de Turing es indecidible.

La primera condición dice que PP no distingue entre dos máquinas que reconocen lo mismo: no ve los estados, ni la cantidad de pasos, ni cómo está escrita la tabla. La segunda descarta las dos preguntas que se responden sin mirar: la que todas las máquinas cumplen y la que no cumple ninguna.

Demostración. Por reducción desde ATMA_{\mathrm{TM}} hacia PP: mostramos que un decididor de PP permitiría decidir ATMA_{\mathrm{TM}}, que es indecidible.

Sea PP una propiedad no trivial del lenguaje, y supongamos que una máquina RPR_P la decide.

Paso 1: se puede suponer que las máquinas con lenguaje vacío no tienen la propiedad. Sea T∅T_\emptyset una máquina que rechaza toda entrada, con L(T∅)=∅L(T_\emptyset) = \emptyset. Si ⟨T∅⟩∈P\langle T_\emptyset \rangle \in P, cambiamos PP por su complemento P‾\overline{P}, el conjunto de las máquinas que no tienen la propiedad. P‾\overline{P} también es una propiedad del lenguaje y también es no trivial, porque las dos condiciones son simétricas entre “tenerla” y “no tenerla”. Y P‾\overline{P} es decidible si PP lo es: basta invertir las respuestas de RPR_P. Así que, si hace falta, hacemos toda la demostración con P‾\overline{P} y llegamos a la misma contradicción. En adelante, ⟨T∅⟩∉P\langle T_\emptyset \rangle \notin P.

Paso 2: una máquina que sí la tiene. Como PP es no trivial, existe una máquina TT con ⟨T⟩∈P\langle T \rangle \in P. Es una máquina fija, que no depende de la entrada de la reducción.

Paso 3: la construcción. Dados MM y ww, sea

M_w = "Con la entrada x:
  1. Correr M con la entrada w. Si M rechaza, rechazar.
  2. Si M acepta, correr T con la entrada x. Si T acepta, aceptar."

Esta MwM_w hace de filtro. Si MM acepta ww, el paso 1 termina y MwM_w se comporta con xx exactamente como TT: acepta xx si y solo si TT acepta xx. Si MM no acepta ww, sea porque rechaza o porque no se detiene, MwM_w no llega nunca a aceptar. Entonces

L(Mw)={L(T)si M acepta w,∅si M no acepta w.L(M_w) = \begin{cases} L(T) & \text{si } M \text{ acepta } w, \\ \emptyset & \text{si } M \text{ no acepta } w. \end{cases}

Paso 4: la máquina que decide ATMA_{\mathrm{TM}}.

S = "Con la entrada ⟨M, w⟩, donde M es una máquina de Turing y w una cadena:
  1. Construir la descripción de la máquina M_w de arriba.
  2. Correr R_P con la entrada ⟨M_w⟩.
  3. Si R_P acepta, aceptar. Si R_P rechaza, rechazar."

SS se detiene siempre: escribe una descripción y corre un decididor.

Si MM acepta ww, entonces L(Mw)=L(T)L(M_w) = L(T). Como ⟨T⟩∈P\langle T \rangle \in P y PP solo depende del lenguaje, ⟨Mw⟩∈P\langle M_w \rangle \in P. RPR_P acepta y SS acepta.

Si MM no acepta ww, entonces L(Mw)=∅=L(T∅)L(M_w) = \emptyset = L(T_\emptyset). Como ⟨T∅⟩∉P\langle T_\emptyset \rangle \notin P y PP solo depende del lenguaje, ⟨Mw⟩∉P\langle M_w \rangle \notin P. RPR_P rechaza y SS rechaza.

SS decide ATMA_{\mathrm{TM}}, lo cual es imposible. Entonces RPR_P no existe. ∎

Las dos hipótesis se usan en lugares que se pueden señalar. Que PP sea no trivial da las dos máquinas, TT y T∅T_\emptyset, una a cada lado. Que PP sea una propiedad del lenguaje es lo que permite pasar de ”MwM_w reconoce lo mismo que TT” a ”MwM_w tiene la propiedad”: MwM_w y TT son máquinas muy distintas por dentro, y solo coinciden en el lenguaje.

Cómo se usa

Para aplicar el teorema a un lenguaje PP hay que comprobar tres cosas, y escribirlas:

  1. Que PP es una propiedad del lenguaje: su definición se puede escribir mencionando solo L(M)L(M).
  2. Que alguna máquina la tiene. Se da una.
  3. Que alguna máquina no la tiene. Se da una.

Algunos ejemplos, con las tres comprobaciones.

Propiedad PP Solo depende de L(M)L(M) Una máquina que la tiene Una que no
L(M)=∅L(M) = \emptyset sí la que rechaza todo la que acepta todo
L(M)L(M) es regular sí la que acepta todo la que decide {0n1n}\{\mathtt{0}^n\mathtt{1}^n\}
L(M)L(M) es finito sí la que rechaza todo la que acepta todo
ε∈L(M)\varepsilon \in L(M) sí la que acepta todo la que rechaza todo
0∈L(M)\mathtt{0} \in L(M) sí la que acepta todo la que rechaza todo
L(M)=Σ∗L(M) = \Sigma^* sí la que acepta todo la que rechaza todo
L(M)L(M) es libre de contexto sí la que rechaza todo la que decide {anbncn}\{\mathtt{a}^n\mathtt{b}^n\mathtt{c}^n\}

Todas son indecidibles. Las dos primeras filas son ETME_{\mathrm{TM}} y REGULARTM\mathrm{REGULAR}_{\mathrm{TM}}, que ya habíamos demostrado a mano.

La cuarta fila es la pregunta 1 de la guía: el lenguaje { ⟨M⟩:M acepta la cadena vacıˊa }\{\, \langle M \rangle : M \text{ acepta la cadena vacía} \,\}. ”MM acepta ε\varepsilon” parece hablar de lo que hace la máquina, pero es lo mismo que "ε∈L(M)\varepsilon \in L(M)", que solo menciona el lenguaje. Dos máquinas con el mismo lenguaje aceptan ε\varepsilon las dos o ninguna.

En la práctica. El teorema de Rice es la razón por la que las herramientas que analizan programas sin ejecutarlos no pueden ser exactas. “¿Este programa puede dividir entre cero?”, “¿imprime alguna vez una contraseña?”, “¿esta función devuelve siempre un número positivo?”: todas son propiedades no triviales de lo que el programa hace. Un verificador de tipos o un analizador estático responde de forma aproximada: rechaza algunos programas correctos, o deja pasar algunos incorrectos, o a veces dice “no sé”. Cuál de las tres cosas elige es una decisión de diseño. No hay una cuarta opción.

Lo que Rice no dice

El teorema tiene dos hipótesis, y fuera de ellas no afirma nada. No dice que toda pregunta sobre máquinas de Turing sea indecidible.

Propiedades de la máquina, que sí se deciden

”MM tiene 5 estados.” No es una propiedad del lenguaje. Tomen una máquina de 5 estados y agréguenle un estado al que no llega ninguna transición: reconoce el mismo lenguaje y tiene 6. Una está en el conjunto y la otra no. Rice no se aplica. Y la pregunta es decidible: se lee la descripción y se cuenta.

”MM se detiene con la entrada ww en a lo sumo 100 pasos.” Tampoco es una propiedad del lenguaje: dos máquinas pueden reconocer lo mismo, una en 10 pasos y otra en 1000. Y es decidible, por una razón que conviene tener clara: simular con un tope de pasos siempre termina.

D = "Con la entrada ⟨M, w⟩:
  1. Simular M con la entrada w durante 100 pasos, o hasta que se detenga.
  2. Si se detuvo, aceptar. Si no, rechazar."

Es lo que hace la opción --pasos del programa history. La máquina machines/loop_on_0.tm avanza a la derecha para siempre cuando la entrada es 00\mathtt{00}:

$ build/history machines/loop_on_0.tm 00 --pasos 5
C1   q0 0 0
C2   0 q1 0
C3   0 0 q1 _
C4   0 0 _ q1 _
C5   0 0 _ _ q1 _
C6   0 0 _ _ _ q1 _
sin detenerse después de 5 pasos: no hay historia que mostrar

El programa respondió, y la respuesta es exacta: en 5 pasos no se detuvo. Lo que no puede responder ningún programa es si se detendrá alguna vez.

”MM se detiene con toda entrada en a lo sumo 100 pasos.” Parece peor, porque hay infinitas entradas. Pero en 100 pasos el cabezal, que empieza en la primera celda y avanza a lo sumo una por paso, solo alcanza a leer las primeras 100 celdas. Lo que la máquina hace en sus primeros 100 pasos depende solo de los primeros 100 símbolos de la entrada. Basta probar las entradas de longitud a lo sumo 100, que son una cantidad finita, cada una con tope de 100 pasos. Es decidible. Lento, pero decidible.

Idea clave. Antes de usar Rice, pregunten: si dos máquinas reconocen el mismo lenguaje, ¿las dos respuestas son iguales por fuerza? Si se puede cambiar la respuesta sin cambiar el lenguaje, agregando un estado o haciendo la máquina más lenta, la propiedad es de la máquina y el teorema no se aplica.

Que Rice no se aplique no quiere decir que sea decidible

Cuando la propiedad es de la máquina, el teorema calla. La pregunta puede ser decidible, como las tres de arriba, o indecidible por otra razón.

”MM se detiene con la entrada 0\mathtt{0}.” No es una propiedad del lenguaje: una máquina que rechaza 0\mathtt{0} y otra que no se detiene con 0\mathtt{0} pueden reconocer el mismo lenguaje, y solo la primera está en el conjunto. Rice no se aplica. Aun así es indecidible, y se demuestra con una reducción directa desde HALTTM\mathrm{HALT}_{\mathrm{TM}}, fijando la entrada dentro de la máquina. Es el ejercicio 4.

”MM tiene un estado inútil”, es decir, un estado al que no entra con ninguna entrada. Es una propiedad de la tabla de la máquina, y Rice no se aplica. También resulta indecidible, con su propia reducción. El ejercicio 8 demuestra una variante, en la que el estado viene dado.

La pregunta 2 de la guía queda así:

Propiedad ¿Cae bajo Rice? ¿Es decidible?
L(M)L(M) es finito sí: es del lenguaje y no trivial no, por Rice
MM tiene un estado inútil no: es de la máquina no, pero por otra demostración
L(M)L(M) contiene a 0\mathtt{0} sí: es del lenguaje y no trivial no, por Rice
MM se detiene con toda entrada en menos de 10 pasos no: es de la máquina sí: se prueban las entradas cortas con tope

Propiedades triviales

La otra hipótesis también hace falta. ”L(M)L(M) es reconocible” es una propiedad del lenguaje que todas las máquinas tienen, por definición de reconocible. Es trivial, y se decide aceptando siempre. ”L(M)L(M) no es reconocible” no la tiene ninguna, y se decide rechazando siempre.

Error común. Aplicar Rice porque el enunciado menciona una máquina de Turing. El teorema pide escribir la propiedad en términos de L(M)L(M) y dar dos máquinas, una que la tiene y una que no. Si no pueden escribir esas tres líneas, no lo están aplicando.

Error común. Reducir en la dirección contraria, otra vez, ahora que hay muchos problemas con nombre. Para demostrar que PP es indecidible no sirve mostrar P≤mATMP \leq_m A_{\mathrm{TM}}. Eso es cierto de cualquier lenguaje reconocible, también de los decidibles, y solo dice que PP no es más difícil que ATMA_{\mathrm{TM}}. La reducción útil es ATM≤mPA_{\mathrm{TM}} \leq_m P, o desde cualquier otro indecidible hacia PP.

Problemas que no hablan de máquinas

Todos los problemas indecidibles de la sesión A tienen una máquina de Turing en la entrada. Eso deja abierta una salida cómoda: pensar que la indecidibilidad es una rareza de las preguntas sobre programas, y que los problemas “normales”, los de cadenas, grafos o gramáticas, están a salvo.

No lo están. En esta sesión hay tres problemas cuyas entradas no mencionan ninguna máquina:

  • un rompecabezas de fichas con cadenas, el problema de correspondencia de Post;
  • decidir si una gramática libre de contexto genera todas las cadenas;
  • decidir si dos gramáticas generan el mismo lenguaje, la deuda de la semana 9.

Para demostrar que son indecidibles hay que reducir ATMA_{\mathrm{TM}} hacia ellos, como siempre. La dificultad es nueva: con un problema sobre máquinas, la reducción construía otra máquina. Ahora la reducción tiene que construir fichas o una gramática a partir de ⟨M,w⟩\langle M, w \rangle, de modo que la respuesta sobre las fichas o la gramática diga si MM acepta ww. Las fichas y las gramáticas no ejecutan nada. Hace falta un puente entre ”MM acepta ww” y un objeto que se pueda describir con cadenas.

El puente es escribir la ejecución entera como una cadena.

Historias de cómputo

En la semana 7 definimos la configuración de una máquina de Turing: el estado, el contenido de la cinta y la posición del cabezal, escritos como u q vu\,q\,v. La cinta contiene uvuv seguido de blancos, el estado es qq y el cabezal está sobre el primer símbolo de vv. Una configuración CC produce otra C′C' si la máquina pasa de CC a C′C' en un paso.

Definición. Una historia de cómputo de aceptación (accepting computation history) de MM con la entrada ww es una secuencia de configuraciones C1,C2,…,CkC_1, C_2, \ldots, C_k tal que

  1. C1C_1 es la configuración inicial de MM con ww, es decir, q0 wq_0\,w;
  2. cada CiC_i produce Ci+1C_{i+1};
  3. CkC_k es una configuración de aceptación: su estado es qacceptq_{\text{accept}}.

Se escribe como una sola cadena, con las configuraciones separadas por #\mathtt{\#}:

C1#C2#⋯#Ck.C_1 \mathtt{\#} C_2 \mathtt{\#} \cdots \mathtt{\#} C_k.

Una historia es finita: tiene kk configuraciones, y cada una es una cadena finita. Si MM no se detiene con ww, no hay historia. Si MM rechaza ww, hay una secuencia que termina en qrejectq_{\text{reject}}, y no es de aceptación. Así:

M acepta w  ⟺  existe una historia de coˊmputo de aceptacioˊn de M con w.M \text{ acepta } w \iff \text{existe una historia de cómputo de aceptación de } M \text{ con } w.

Como las máquinas del curso son deterministas, cuando la historia existe es una sola: C1C_1 está fijada por ww y cada configuración fija la siguiente. La única libertad es de escritura, si se anotan o no blancos al final de cada configuración.

El programa history la escribe. La máquina machines/zeros_ones.tm es la de code/formats.md, que decide { 0n1n:n≥0 }\{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\} tachando un 0\mathtt{0} con X y un 1\mathtt{1} con Y en cada vuelta:

$ build/history machines/zeros_ones.tm 01
C1   q0 0 1
C2   X q1 1
C3   q2 X Y
C4   X q0 Y
C5   X Y q3 _
C6   X Y _ q_accept _
acepta después de 5 pasos
historia: q0 0 1 # X q1 1 # q2 X Y # X q0 Y # X Y q3 _ # X Y _ q_accept _

Los nombres de los estados tienen varios caracteres, así que el programa separa los símbolos con espacios: q_accept es un símbolo de la historia, igual que X. El estado siempre lleva a su derecha el símbolo que está leyendo; si es un blanco de más allá de lo escrito, se anota como _.

El alfabeto de una historia es entonces Γ∪Q∪{#}\Gamma \cup Q \cup \{\mathtt{\#}\}: los símbolos de la cinta, los estados y el separador. Una historia es una cadena como cualquier otra, y se puede preguntar si una cadena dada es o no una historia.

Comprobar una historia es fácil y es local

Comparen las configuraciones seguidas de esa historia, cada una puesta sobre la que le sigue:

Arriba, la historia de cómputo de zeros_ones.tm con la entrada 01 escrita como una sola cadena de celdas: q0 0 1 # X q1 1 # q2 X Y # X q0 Y # X Y q3 _ # X Y _ q_accept _, con un corchete bajo cada una de las seis configuraciones C1 a C6. Abajo, tres pares de configuraciones seguidas puestas una sobre otra, con un marco alrededor de la ventana del estado. De C2 = X q1 1 a C3 = q2 X Y cambian los tres símbolos, por la transición δ(q1, 1) = (q2, Y, L): el estado salta sobre la X. De C3 = q2 X Y a C4 = X q0 Y la ventana tiene dos símbolos porque el estado está en la primera celda, por δ(q2, X) = (q0, X, R), y la Y de afuera se copia. De C4 = X q0 Y _ a C5 = X Y q3 _ la ventana es X q0 Y, por δ(q0, Y) = (q3, Y, R), y el blanco de afuera se copia.Arriba, la historia de cómputo de zeros_ones.tm con la entrada 01 escrita como una sola cadena de celdas: q0 0 1 # X q1 1 # q2 X Y # X q0 Y # X Y q3 _ # X Y _ q_accept _, con un corchete bajo cada una de las seis configuraciones C1 a C6. Abajo, tres pares de configuraciones seguidas puestas una sobre otra, con un marco alrededor de la ventana del estado. De C2 = X q1 1 a C3 = q2 X Y cambian los tres símbolos, por la transición δ(q1, 1) = (q2, Y, L): el estado salta sobre la X. De C3 = q2 X Y a C4 = X q0 Y la ventana tiene dos símbolos porque el estado está en la primera celda, por δ(q2, X) = (q0, X, R), y la Y de afuera se copia. De C4 = X q0 Y _ a C5 = X Y q3 _ la ventana es X q0 Y, por δ(q0, Y) = (q3, Y, R), y el blanco de afuera se copia.
Dos configuraciones seguidas solo difieren en la ventana del estado: el estado, el símbolo de su derecha y el de su izquierda. Lo demás se copia igual.

En un paso la máquina cambia el estado, escribe una celda y mueve el cabezal una posición. Entonces dos configuraciones seguidas son iguales en casi todas partes. Solo pueden cambiar tres símbolos: el estado, el que está a su derecha (la celda que se lee y se escribe) y el que está a su izquierda (porque el estado, al moverse a la izquierda, se intercambia con él). Si δ(q,a)=(r,b,R)\delta(q, a) = (r, b, \mathrm{R}) o δ(q,a)=(r,b,L)\delta(q, a) = (r, b, \mathrm{L}), el cambio es

⋯ c  q  a ⋯  ⟶  ⋯ c  b  r ⋯o⋯ c  q  a ⋯  ⟶  ⋯ r  c  b ⋯\cdots\, c\; q\; a\, \cdots \;\longrightarrow\; \cdots\, c\; b\; r\, \cdots \qquad\text{o}\qquad \cdots\, c\; q\; a\, \cdots \;\longrightarrow\; \cdots\, r\; c\; b\, \cdots

y todo lo que está fuera de esos tres símbolos se copia igual. En la primera celda no hay nada a la izquierda; ahí el movimiento L\mathrm{L} deja el estado en su sitio, y q aq\,a pasa a ser r br\,b.

Por eso comprobar que CiC_i produce Ci+1C_{i+1} no pide simular nada ni recordar la cinta completa. Se recorren las dos configuraciones a la vez, mirando una ventana de tres símbolos de arriba y los tres de abajo:

  • si en la ventana de arriba no hay ningún estado, el símbolo del centro tiene que estar igual abajo;
  • si el estado está en el centro de la ventana de arriba, los tres símbolos de abajo tienen que ser los que manda δ\delta.

Cada comprobación mira una cantidad fija de símbolos y consulta la tabla de δ\delta. Entre las dos reglas queda determinada cada posición de la configuración de abajo, así que si todas las ventanas pasan, Ci+1C_{i+1} es de verdad la que sigue a CiC_i. Eso es lo que quiere decir que la comprobación es local.

Una historia completa se comprueba con cuatro revisiones, todas de este tipo:

  1. cada tramo entre separadores es una configuración: símbolos de Γ\Gamma y exactamente un estado;
  2. C1C_1 es q0 wq_0\,w;
  3. cada par de configuraciones seguidas pasa la revisión por ventanas;
  4. la última tiene a qacceptq_{\text{accept}}.

El programa check_history hace esas cuatro revisiones. No simula la máquina: la función check_step de tm.h solo compara ventanas.

$ build/check_history machines/zeros_ones.tm 01 "q0 0 1 # X q1 1 # q2 X Y # X q0 Y # X Y q3 _ # X Y _ q_accept _"
es una historia de aceptación

Si se cambia un solo símbolo, por ejemplo la Y de C4C_4 por una X, alguna ventana lo nota:

$ build/check_history machines/zeros_ones.tm 01 "q0 0 1 # X q1 1 # q2 X Y # X q0 X # X Y q3 _ # X Y _ q_accept _"
no es una historia de aceptación
  de C3 a C4: ventana lejos del cabezal en la posición 3: arriba [X Y _], abajo [q0 X _], y el centro debía copiarse

Y si alguien intenta acortar el camino escribiendo una configuración de aceptación antes de tiempo, falla la ventana del cabezal:

$ build/check_history machines/zeros_ones.tm 01 "q0 0 1 # X q1 1 # X q_accept 1"
no es una historia de aceptación
  de C2 a C3: ventana del cabezal en la posición 2: arriba [X q1 1], abajo [X q_accept 1], y δ pide [q2 X Y]

test_history lo comprueba de forma exhaustiva con las cinco cadenas 0n1n\mathtt{0}^n\mathtt{1}^n de longitud a lo sumo 8: toma la historia de cada una y cambia cada símbolo por cada uno de los otros símbolos posibles. Son 8250 cadenas alteradas, y el comprobador las rechaza todas.

Idea clave. ”¿MM acepta ww?” es una pregunta difícil: indecidible. “¿Es esta cadena una historia de aceptación de MM con ww?” es una pregunta fácil: se responde comparando símbolos vecinos. La dificultad de ATMA_{\mathrm{TM}} está toda en encontrar la historia, que puede no existir, y no en revisarla. Los dos resultados que siguen aprovechan eso: se construyen unas fichas, o una gramática, que solo saben comparar símbolos vecinos, y con eso basta para que la pregunta sobre ellas sea tan difícil como ATMA_{\mathrm{TM}}.

La pregunta 5 de la guía se responde con esta sección: comprobar una historia es local porque entre dos configuraciones seguidas solo pueden cambiar el estado y los dos símbolos que lo rodean, y lo demás se copia. La misma idea vuelve en la semana 13, con otro nombre, en la demostración del teorema de Cook-Levin.

El problema de correspondencia de Post

Emil Post propuso en 1946 un rompecabezas que cabe en una línea. Se tiene un conjunto finito de fichas, como las de dominó. Cada ficha tiene una cadena arriba y otra abajo:

[bca],[aab],[caa],[abcc].\left[\frac{\mathtt{b}}{\mathtt{ca}}\right],\quad \left[\frac{\mathtt{a}}{\mathtt{ab}}\right],\quad \left[\frac{\mathtt{ca}}{\mathtt{a}}\right],\quad \left[\frac{\mathtt{abc}}{\mathtt{c}}\right].

Hay que poner fichas en fila, repitiendo las que se quiera, de modo que la cadena que se lee arriba, juntando las de todas las fichas, sea la misma que se lee abajo.

Definición. Una instancia del problema de correspondencia de Post (PCP) es una lista de fichas

P={[t1b1],[t2b2],…,[tkbk]},P = \left\{ \left[\frac{t_1}{b_1}\right], \left[\frac{t_2}{b_2}\right], \ldots, \left[\frac{t_k}{b_k}\right] \right\},

donde tit_i y bib_i son cadenas sobre un alfabeto Σ\Sigma. Una solución es una secuencia de índices i1,i2,…,ini_1, i_2, \ldots, i_n, con n≥1n \geq 1, tal que

ti1ti2⋯tin=bi1bi2⋯bin.t_{i_1} t_{i_2} \cdots t_{i_n} = b_{i_1} b_{i_2} \cdots b_{i_n}.

El lenguaje es PCP={ ⟨P⟩:P tiene una solucioˊn }\mathrm{PCP} = \{\, \langle P \rangle : P \text{ tiene una solución} \,\}.

Las fichas no se pueden voltear ni partir, y las de arriba y las de abajo van en el mismo orden: es una sola fila de fichas. La condición n≥1n \geq 1 descarta la fila vacía, que daría ε\varepsilon arriba y abajo.

Un ejemplo con solución

Las cuatro fichas de arriba están en instances/sipser.pcp, numeradas del 1 al 4 en ese orden:

# Cuatro fichas sobre {a, b, c}. Tiene solución: 2 1 3 2 4.
dominoes: 4
b ca
a ab
ca a
abc c

El programa pcp_check pone una secuencia de fichas y compara:

$ build/pcp_check instances/sipser.pcp 2 1 3 2 4
arriba: a b ca a abc  =  abcaaabc
abajo:  ab ca a ab c  =  abcaaabc
es una solución (5 fichas, 8 símbolos)

Arriba y abajo se lee abcaaabc\mathtt{abcaaabc}, cortada en pedazos distintos. La ficha 2 se usa dos veces.

Vale la pena ver cómo se llega. La primera ficha tiene que tener arriba y abajo cadenas que empiecen igual, y solo la ficha 2 lo cumple: a\mathtt{a} y ab\mathtt{ab}. Después de ponerla, abajo va adelantado: sobra una b\mathtt{b}.

$ build/pcp_check instances/sipser.pcp 2 1 3
arriba: a b ca  =  abca
abajo:  ab ca a  =  abcaa
no es una solución: abajo sobra a

Lo que sobra es lo único que importa para seguir: la próxima ficha tiene que empezar a cubrirlo. Esa cadena que sobra, junto con el lado al que le sobra, se llama aquí el exceso. Vuelve en la sección siguiente.

Una instancia con solución tiene infinitas: 2 1 3 2 4 2 1 3 2 4 también lo es.

Ejemplos sin solución

A veces se ve enseguida que no hay solución.

Ninguna ficha puede ir primera. En instances/no_start.pcp las fichas son

[abcca],[caa],[accba].\left[\frac{\mathtt{abc}}{\mathtt{ca}}\right],\quad \left[\frac{\mathtt{ca}}{\mathtt{a}}\right],\quad \left[\frac{\mathtt{acc}}{\mathtt{ba}}\right].

En las tres, la cadena de arriba y la de abajo empiezan con símbolos distintos. La primera ficha de una solución tendría que empezar igual arriba y abajo.

Arriba siempre es más largo. En instances/longer_top.pcp,

[abcab],[caaa],[acca],\left[\frac{\mathtt{abc}}{\mathtt{ab}}\right],\quad \left[\frac{\mathtt{caa}}{\mathtt{a}}\right],\quad \left[\frac{\mathtt{acc}}{\mathtt{a}}\right],

cada ficha tiene arriba más símbolos que abajo. Cualquier fila de fichas tiene arriba una cadena más larga que la de abajo, y no pueden ser iguales.

Se puede seguir para siempre sin terminar. En instances/cycle.pcp,

[10101],[01111],[101011],\left[\frac{\mathtt{10}}{\mathtt{101}}\right],\quad \left[\frac{\mathtt{011}}{\mathtt{11}}\right],\quad \left[\frac{\mathtt{101}}{\mathtt{011}}\right],

solo la ficha 1 puede ir primera, y deja abajo adelantado con el exceso 1\mathtt{1}. Con ese exceso, la única ficha que se puede poner es la 3: arriba agrega 101\mathtt{101}, que cubre el 1\mathtt{1} que sobraba más los dos primeros símbolos del 011\mathtt{011} de abajo, y abajo vuelve a sobrar 1\mathtt{1}. Se puede poner la ficha 3 cuantas veces se quiera, y el exceso nunca queda vacío. No hay solución.

En los tres casos hubo un argumento, y cada uno fue distinto. Eso es lo esperable en un problema indecidible: no hay un argumento que sirva para todas las instancias.

PCP es reconocible

Antes de demostrar que PCP es indecidible conviene ver qué sí se puede hacer.

Teorema. PCP es reconocible.

Demostración. Por construcción: una máquina que busca.

B = "Con la entrada ⟨P⟩, donde P es una lista de k fichas:
  1. Para n = 1, 2, 3, …:
  2.     Para cada una de las kⁿ secuencias de n fichas:
  3.         Si arriba y abajo se lee la misma cadena, aceptar."

Cada vuelta del paso 1 termina, porque revisa una cantidad finita de secuencias y cada revisión es comparar dos cadenas. Si PP tiene una solución de nn fichas, BB llega a la vuelta nn y acepta. Si PP no tiene solución, BB no acepta nunca. Entonces L(B)=PCPL(B) = \mathrm{PCP}. ∎

Con una instancia sin solución, BB no se detiene. Reconoce y no decide: es la misma situación que la máquina universal con ATMA_{\mathrm{TM}}.

Buscar mejor: el exceso

La máquina BB es correcta y muy lenta: knk^n secuencias de longitud nn. Casi todas son absurdas, porque se estropean en la segunda ficha. La búsqueda razonable construye la fila ficha por ficha y abandona un intento en cuanto arriba y abajo dejan de coincidir.

Mientras coinciden, una de las dos cadenas es prefijo de la otra. La parte común ya no importa. Lo que hay que recordar es:

  • qué lado va adelantado, arriba o abajo;
  • con qué cadena: el exceso.

Poner una ficha lleva de un exceso a otro, o no se puede. Si abajo sobra b\mathtt{b} y se pone la ficha [bca]\left[\frac{\mathtt{b}}{\mathtt{ca}}\right], arriba se cubre la b\mathtt{b} y abajo se agrega ca\mathtt{ca}: ahora abajo sobra ca\mathtt{ca}. Una solución es un camino que sale del exceso vacío y vuelve a él después de al menos una ficha. Para 2 1 3 2 4:

Ficha Arriba se lee Abajo se lee Exceso
2 a\mathtt{a} ab\mathtt{ab} abajo, b\mathtt{b}
1 ab\mathtt{ab} abca\mathtt{abca} abajo, ca\mathtt{ca}
3 abca\mathtt{abca} abcaa\mathtt{abcaa} abajo, a\mathtt{a}
2 abcaa\mathtt{abcaa} abcaaab\mathtt{abcaaab} abajo, ab\mathtt{ab}
4 abcaaabc\mathtt{abcaaabc} abcaaabc\mathtt{abcaaabc} vacío

En el último paso abajo sobra ab\mathtt{ab}. La ficha 4 agrega c\mathtt{c} abajo, y lo pendiente pasa a ser abc\mathtt{abc}; arriba agrega justo abc\mathtt{abc}. No sobra nada.

Animación de la solución 2 1 3 2 4 de sipser.pcp armada ficha por ficha. Arriba están las cuatro fichas de la instancia; al centro, la fila con cinco lugares; abajo, las cadenas de arriba y de abajo alineadas símbolo por símbolo, con un marco sobre el exceso. Paso 1: la ficha 2 pone a arriba y ab abajo; abajo sobra b. Paso 2: la ficha 1 cubre la b arriba y agrega ca abajo; sobra ca. Paso 3: la ficha 3 cubre ca arriba y agrega a abajo; sobra a. Paso 4: la ficha 2 otra vez cubre la a y agrega ab abajo; sobra ab. Paso 5: la ficha 4 agrega c abajo y abc arriba; no sobra nada y las dos cadenas son abcaaabc.Animación de la solución 2 1 3 2 4 de sipser.pcp armada ficha por ficha. Arriba están las cuatro fichas de la instancia; al centro, la fila con cinco lugares; abajo, las cadenas de arriba y de abajo alineadas símbolo por símbolo, con un marco sobre el exceso. Paso 1: la ficha 2 pone a arriba y ab abajo; abajo sobra b. Paso 2: la ficha 1 cubre la b arriba y agrega ca abajo; sobra ca. Paso 3: la ficha 3 cubre ca arriba y agrega a abajo; sobra a. Paso 4: la ficha 2 otra vez cubre la a y agrega ab abajo; sobra ab. Paso 5: la ficha 4 agrega c abajo y abc arriba; no sobra nada y las dos cadenas son abcaaabc.
Cada ficha cubre arriba lo que sobraba abajo y deja un exceso nuevo. La fila es una solución cuando el exceso queda vacío.

Los excesos son los vértices de un grafo, y las fichas, sus aristas. Buscar una solución es buscar un camino en ese grafo, y la herramienta es la búsqueda en anchura de Algoritmos, con dos cuidados:

  • No repetir excesos. Si dos filas distintas dejan el mismo lado adelantado con la misma cadena, lo que se puede hacer después es idéntico. Basta seguir con la primera que llegó.
  • Poner una cota. El grafo puede ser infinito: los excesos pueden crecer sin límite. La búsqueda recibe un número NN y no pasa de NN fichas.

pcp_solve hace eso, y dice cuántos excesos distintos visitó:

$ build/pcp_solve instances/sipser.pcp 10
4 fichas, hasta 10 por solución
solución con 5 fichas: 2 1 3 2 4
cadena: abcaaabc
excesos visitados: 5

Como busca por niveles, la solución que encuentra es una de las más cortas. Con una cota menor que 5 no la encuentra:

$ build/pcp_solve instances/sipser.pcp 4
4 fichas, hasta 4 por solución
sin solución hasta 4
excesos visitados: 4

La respuesta dice hasta 4, y es lo único que el programa sabe. La instancia tiene solución.

Tres finales distintos

Con las instancias sin solución de la sección anterior pasa algo que parece contradecir lo dicho:

$ build/pcp_solve instances/cycle.pcp 1000
3 fichas, hasta 1000 por solución
sin solución: la búsqueda se quedó sin excesos nuevos
excesos visitados: 1

El programa afirma que no hay solución, de ninguna longitud, y tiene razón. El grafo de excesos de esta instancia tiene un solo vértice alcanzable, el exceso 1\mathtt{1} con abajo adelantado, y desde él no se llega al exceso vacío. Cuando el grafo alcanzable es finito, la búsqueda en anchura lo recorre entero y puede responder que no.

Lo que la búsqueda no puede hacer es responder siempre. Hay instancias en las que los excesos crecen sin parar. En instances/hard_75.pcp las fichas son

[1101],[10],[0110],\left[\frac{\mathtt{110}}{\mathtt{1}}\right],\quad \left[\frac{\mathtt{1}}{\mathtt{0}}\right],\quad \left[\frac{\mathtt{0}}{\mathtt{110}}\right],

y esto es lo que pasa:

$ build/pcp_solve instances/hard_75.pcp 45
3 fichas, hasta 45 por solución
sin solución hasta 45
excesos visitados: 70718
$ build/pcp_solve instances/hard_75.pcp 400
3 fichas, hasta 400 por solución
búsqueda abandonada: demasiados excesos distintos
excesos visitados: 2000000

Con cota 45 visitó 70 718 excesos sin encontrar nada. Con cota 400 llegó al tope de dos millones que tiene el programa para no agotar la memoria, y abandonó. Ninguna de las dos respuestas dice si la instancia tiene solución.

La tiene. Una búsqueda más astuta, que avanza a la vez desde el principio y desde el final de la fila y junta las dos mitades, la encuentra:

$ build/pcp_meet instances/hard_75.pcp 40
3 fichas, hasta 40 desde cada extremo
solución con 75 fichas: 1 1 2 1 1 2 1 3 3 1 3 2 2 1 1 2 2 1 1 1 1 2 3 1 1 3 3 1 1 2 3 1 2 3 3 2 2 3 3 1 2 3 1 2 2 3 2 3 1 2 3 3 1 2 3 1 2 2 3 1 2 3 3 3 1 2 2 2 3 1 3 3 2 2 3
comprobada: arriba y abajo se leen 125 símbolos
excesos visitados: 28473

Tres fichas, ninguna cadena de más de tres símbolos, y la solución más corta tiene 75 fichas. Que es la más corta también lo dice una ejecución: pcp_meet con 37 fichas por extremo cubre todas las soluciones de hasta 74 y responde sin solución hasta 74.

Error común. Creer que un problema es decidible porque todas las instancias que uno probó tenían respuesta. Cada instancia de PCP tiene respuesta: o existe una solución o no existe. Y para muchas instancias la respuesta se encuentra, con una búsqueda o con un argumento a medida, como en los tres ejemplos sin solución. Decidible quiere decir otra cosa: que un solo algoritmo responda bien en todas. Que el programa de uno haya respondido en las cien instancias que probó no dice nada sobre la que lo hará abandonar, y después de hard_75.pcp ya vieron una. Cambiar el programa por uno mejor mueve la frontera. No la elimina.

En C++. El estado de la búsqueda cabe en una cadena: un carácter para el lado, T o B, seguido del exceso. Así sirve directamente como clave de un std::unordered_map, que guarda para cada exceso visitado de dónde se llegó y con qué ficha. La función extend de pcp.h calcula el exceso nuevo con dos comparaciones de prefijos, y es el corazón del laboratorio.

PCP es indecidible

Teorema. PCP es indecidible.

La demostración es una reducción desde ATMA_{\mathrm{TM}} hacia PCP, que es la dirección que sirve porque ATMA_{\mathrm{TM}} es el problema que ya sabemos indecidible. Hay que dar una función computable que convierta cada par ⟨M,w⟩\langle M, w \rangle en un conjunto de fichas PP tal que

M acepta w  ⟺  P tiene una solucioˊn.M \text{ acepta } w \iff P \text{ tiene una solución.}

La idea: diseñar las fichas para que la única manera de armar una fila que coincida sea escribir una historia de cómputo de aceptación de MM con ww, arriba y abajo. Las dos cadenas dicen lo mismo, pero abajo va siempre una configuración adelantado. Cada ficha que se pone arriba copia un pedazo de la configuración CiC_i que abajo ya está escrita, y al mismo tiempo escribe abajo el pedazo correspondiente de Ci+1C_{i+1}. Las fichas hacen, con cadenas, la revisión por ventanas de la sección anterior.

Aquí no se construye la demostración para una máquina general con todos sus subíndices. Se muestra la construcción con un ejemplo, se enumeran los tipos de ficha y se explica por qué funciona. El programa tm_to_pcp la hace para cualquier máquina del formato .tm.

Dos simplificaciones

Primera: la solución empieza con una ficha fija. En el PCP modificado la instancia es la misma, una lista de fichas, pero una solución tiene que empezar con la ficha 1. Reducimos ATMA_{\mathrm{TM}} al PCP modificado, y al final se quita la condición con un paso aparte.

Segunda: MM nunca intenta moverse a la izquierda desde la primera celda. No se pierde generalidad. Toda máquina se puede cambiar por otra que acepta las mismas cadenas y lo cumple: la nueva empieza corriendo su entrada una celda a la derecha y dejando una marca en la primera celda, y cada vez que lee la marca vuelve a la derecha sin cambiar de estado. Las máquinas de los ejemplos ya lo cumplen.

Las fichas, con un ejemplo

La máquina es machines/starts_01.tm, la de la sesión A, y la entrada es 01\mathtt{01}. Su historia tiene cuatro configuraciones, con un movimiento a la derecha, uno a la izquierda y otro a la derecha:

$ build/history machines/starts_01.tm 01
C1   q0 0 1
C2   0 q1 1
C3   q2 0 1
C4   0 q_accept 1
acepta después de 3 pasos
historia: q0 0 1 # 0 q1 1 # q2 0 1 # 0 q_accept 1

En una ficha cada símbolo es un carácter, así que el programa le da una letra a cada estado. Estas son todas las fichas:

$ build/tm_to_pcp machines/starts_01.tm 01
estados: A = q0, B = q1, C = q2, D = q_accept, E = q_reject
 n.º  tipo        arriba  abajo
   1  inicio      #       #A01#
   2  derecha     A0      0B
   3  derecha     C0      0D
   4  izquierda   0B1     C01
   5  izquierda   1B1     C11
   6  izquierda   _B1     C_1
   7  copia       0       0
   8  copia       1       1
   9  copia       _       _
  10  separador   #       #
  11  separador   #       _#
  12  comer       0D      D
  13  comer       1D      D
  14  comer       _D      D
  15  comer       D0      D
  16  comer       D1      D
  17  comer       D_      D
  18  final       D##     #

Son siete tipos. Para una máquina M=(Q,Σ,Γ,δ,q0,qaccept,qreject)M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}}) y una entrada w=w1w2⋯wnw = w_1 w_2 \cdots w_n cualesquiera:

1. La ficha de inicio.

[## q0 w1w2⋯wn #]\left[\frac{\mathtt{\#}}{\mathtt{\#}\, q_0\, w_1 w_2 \cdots w_n\, \mathtt{\#}}\right]

Es la ficha 1, la obligatoria. Deja abajo escrita la configuración inicial C1C_1, y arriba solo el separador. Desde aquí abajo va adelantado en una configuración entera. Si w=εw = \varepsilon, se escribe q0⊔q_0 \sqcup, para que el estado tenga a su derecha el blanco que lee.

2. Una ficha por cada transición a la derecha. Si δ(q,a)=(r,b,R)\delta(q, a) = (r, b, \mathrm{R}):

[q ab r]\left[\frac{q\,a}{b\,r}\right]

Arriba lee el estado y el símbolo bajo el cabezal; abajo escribe lo que queda después del paso: el símbolo nuevo y, a su derecha, el estado nuevo. En el ejemplo, la ficha 2 es δ(q0,0)=(q1,0,R)\delta(q_0, \mathtt{0}) = (q_1, \mathtt{0}, \mathrm{R}).

3. Fichas por cada transición a la izquierda. Si δ(q,a)=(r,b,L)\delta(q, a) = (r, b, \mathrm{L}), una ficha por cada símbolo c∈Γc \in \Gamma:

[c q ar c b]\left[\frac{c\,q\,a}{r\,c\,b}\right]

El estado tiene que saltar por encima del símbolo que está a su izquierda, y la ficha no sabe cuál es: por eso hay una por cada cc posible. Las fichas 4, 5 y 6 son δ(q1,1)=(q2,1,L)\delta(q_1, \mathtt{1}) = (q_2, \mathtt{1}, \mathrm{L}), con cc igual a 0\mathtt{0}, 1\mathtt{1} y ⊔\sqcup.

4. Fichas de copia. Para cada a∈Γa \in \Gamma:

[aa]\left[\frac{a}{a}\right]

Copian a la configuración siguiente los símbolos de la cinta que están lejos del cabezal.

5. Las fichas del separador.

[##]y[#⊔ #]\left[\frac{\mathtt{\#}}{\mathtt{\#}}\right] \qquad\text{y}\qquad \left[\frac{\mathtt{\#}}{\sqcup\,\mathtt{\#}}\right]

La primera copia el separador. La segunda, además, agrega un blanco al final de la configuración que se está escribiendo abajo. Hace falta cuando el cabezal avanza más allá de lo escrito: la cinta es infinita y la configuración solo anota una parte, así que hay que poder alargarla.

6. Las fichas que comen. Para cada a∈Γa \in \Gamma:

[a qacceptqaccept]y[qaccept aqaccept]\left[\frac{a\, q_{\text{accept}}}{q_{\text{accept}}}\right] \qquad\text{y}\qquad \left[\frac{q_{\text{accept}}\, a}{q_{\text{accept}}}\right]

Hasta aquí todas las fichas, salvo la de inicio, tienen arriba a lo sumo tantos símbolos como abajo: con ellas arriba nunca alcanza a abajo. Estas son las primeras que acortan. Solo se pueden usar cuando abajo aparece qacceptq_{\text{accept}}, y en cada “configuración” siguiente el estado de aceptación se come un símbolo vecino.

7. La ficha final.

[qaccept # ##]\left[\frac{q_{\text{accept}}\,\mathtt{\#}\,\mathtt{\#}}{\mathtt{\#}}\right]

Cuando abajo solo queda qaccept #q_{\text{accept}}\,\mathtt{\#} por cubrir, esta ficha lo cubre y empareja los dos separadores finales.

No hay fichas para qrejectq_{\text{reject}}, ni para un par (q,a)(q, a) sin transición. Si la máquina llega ahí, no hay ninguna ficha que tenga ese estado arriba, y la fila no se puede continuar.

La cantidad de fichas es finita y se calcula leyendo la tabla de MM. En el ejemplo, con ∣Γ∣=3|\Gamma| = 3: una de inicio, 2 de transiciones a la derecha, 1⋅31 \cdot 3 de la transición a la izquierda, 3 de copia, 2 de separador, 2⋅32 \cdot 3 que comen y una final. Son 18.

La solución del ejemplo

Se guarda la instancia en un archivo y se busca, pidiendo que la solución empiece con la ficha 1:

$ build/tm_to_pcp machines/starts_01.tm 01 --mpcp > build/starts_01.pcp
$ build/pcp_solve build/starts_01.pcp 30 --primera
18 fichas, hasta 30 por solución, empezando con la ficha 1
solución con 15 fichas: 1 2 8 10 4 10 3 8 10 7 16 10 12 10 18
cadena: #A01#0B1#C01#0D1#0D#D##
excesos visitados: 459

La cadena que se lee es la historia de cómputo: # q001 # 0q11 # q201 # 0qaccept1 #\mathtt{\#}\,q_0\mathtt{01}\,\mathtt{\#}\,\mathtt{0}q_1\mathtt{1}\, \mathtt{\#}\,q_2\mathtt{01}\,\mathtt{\#}\,\mathtt{0}q_{\text{accept}}\mathtt{1}\,\mathtt{\#}, seguida de la limpieza. pcp_check muestra cómo la cortan las fichas arriba y abajo:

$ build/pcp_check build/starts_01.pcp 1 2 8 10 4 10 3 8 10 7 16 10 12 10 18
arriba: # A0 1 # 0B1 # C0 1 # 0 D1 # 0D # D##  =  #A01#0B1#C01#0D1#0D#D##
abajo:  #A01# 0B 1 # C01 # 0D 1 # 0 D # D # #  =  #A01#0B1#C01#0D1#0D#D##
es una solución (15 fichas, 23 símbolos)

Por vueltas, con lo que arriba cubre y lo que abajo escribe en cada una:

Vuelta Fichas Arriba cubre Abajo escribe Qué pasó
inicio 1 #\mathtt{\#} # q001 #\mathtt{\#}\,q_0\mathtt{01}\,\mathtt{\#} queda escrita C1C_1
1 2, 8, 10 q00q_0\mathtt{0}, 1\mathtt{1}, #\mathtt{\#} 0q1\mathtt{0}q_1, 1\mathtt{1}, #\mathtt{\#} de C1C_1 sale C2C_2, paso a la derecha
2 4, 10 0q11\mathtt{0}q_1\mathtt{1}, #\mathtt{\#} q201q_2\mathtt{01}, #\mathtt{\#} de C2C_2 sale C3C_3, paso a la izquierda
3 3, 8, 10 q20q_2\mathtt{0}, 1\mathtt{1}, #\mathtt{\#} 0qaccept\mathtt{0}q_{\text{accept}}, 1\mathtt{1}, #\mathtt{\#} de C3C_3 sale C4C_4: acepta
4 7, 16, 10 0\mathtt{0}, qaccept1q_{\text{accept}}\mathtt{1}, #\mathtt{\#} 0\mathtt{0}, qacceptq_{\text{accept}}, #\mathtt{\#} se come el 1\mathtt{1}
5 12, 10 0qaccept\mathtt{0}q_{\text{accept}}, #\mathtt{\#} qacceptq_{\text{accept}}, #\mathtt{\#} se come el 0\mathtt{0}
final 18 qaccept # #q_{\text{accept}}\,\mathtt{\#}\,\mathtt{\#} #\mathtt{\#} arriba alcanza a abajo

En cada vuelta, lo que arriba cubre es exactamente lo que abajo se escribió en la vuelta anterior. En las vueltas 1 a 3 las fichas simulan a MM: una ficha de transición donde está el estado, fichas de copia en lo demás, y el separador. En las vueltas 4 y 5 ya no se simula nada: abajo se escribe la misma configuración con un símbolo menos, hasta que solo queda el estado.

Animación de la solución de las fichas de starts_01.tm con la entrada 01, vuelta por vuelta. Las cadenas de arriba y de abajo se escriben en columnas alineadas, cada pieza con el número de su ficha y el color de su tipo: inicio, transición, copia, separador, comer y final. Inicio: la ficha 1 pone # arriba y #A01# abajo, y abajo queda adelantado en la configuración C1. Vuelta 1: las fichas 2, 8 y 10 cubren arriba A01# y escriben abajo 0B1#, que es C2. Vuelta 2: las fichas 4 y 10 cubren 0B1# y escriben C01#, que es C3. Vuelta 3: las fichas 3, 8 y 10 cubren C01# y escriben 0D1#, que es C4, con el estado de aceptación D. Vuelta 4: las fichas 7, 16 y 10 cubren 0D1# y escriben 0D#, con un símbolo menos. Vuelta 5: las fichas 12 y 10 cubren 0D# y escriben D#. Final: la ficha 18 cubre D## arriba y escribe # abajo; las dos cadenas son #A01#0B1#C01#0D1#0D#D##.Animación de la solución de las fichas de starts_01.tm con la entrada 01, vuelta por vuelta. Las cadenas de arriba y de abajo se escriben en columnas alineadas, cada pieza con el número de su ficha y el color de su tipo: inicio, transición, copia, separador, comer y final. Inicio: la ficha 1 pone # arriba y #A01# abajo, y abajo queda adelantado en la configuración C1. Vuelta 1: las fichas 2, 8 y 10 cubren arriba A01# y escriben abajo 0B1#, que es C2. Vuelta 2: las fichas 4 y 10 cubren 0B1# y escriben C01#, que es C3. Vuelta 3: las fichas 3, 8 y 10 cubren C01# y escriben 0D1#, que es C4, con el estado de aceptación D. Vuelta 4: las fichas 7, 16 y 10 cubren 0D1# y escriben 0D#, con un símbolo menos. Vuelta 5: las fichas 12 y 10 cubren 0D# y escriben D#. Final: la ficha 18 cubre D## arriba y escribe # abajo; las dos cadenas son #A01#0B1#C01#0D1#0D#D##.
Abajo va siempre una configuración adelantado, y lo que arriba cubre en una vuelta es lo que abajo escribió en la anterior. Solo las fichas que comen, que aparecen con el estado de aceptación, dejan que arriba alcance a abajo.

Por qué funciona

Hay que demostrar las dos direcciones, para el PCP modificado: las fichas tienen una solución que empieza con la ficha 1 si y solo si MM acepta ww.

Si MM acepta ww, hay solución. Sea C1,…,CkC_1, \ldots, C_k la historia de aceptación. Se construye la fila como en el ejemplo, manteniendo esta situación al empezar cada vuelta ii:

arriba: #C1#⋯#Ci−1#,abajo: #C1#⋯#Ci−1#Ci#.\text{arriba: } \mathtt{\#} C_1 \mathtt{\#} \cdots \mathtt{\#} C_{i-1} \mathtt{\#}, \qquad \text{abajo: } \mathtt{\#} C_1 \mathtt{\#} \cdots \mathtt{\#} C_{i-1} \mathtt{\#} C_i \mathtt{\#}.

La ficha de inicio la establece para i=1i = 1. En la vuelta ii, con i<ki < k, se cubre Ci#C_i \mathtt{\#} con la ficha de la transición que MM aplica en CiC_i, puesta donde está el estado, fichas de copia para el resto y una ficha de separador. Abajo queda escrita Ci+1#C_{i+1}\mathtt{\#}, porque esas fichas hacen justo lo que dice la revisión por ventanas: copian lo que está lejos del cabezal y cambian los tres símbolos de alrededor según δ\delta. Si en Ci+1C_{i+1} el estado quedó al final, se usa el separador que agrega un blanco. Cuando se llega a CkC_k, que tiene a qacceptq_{\text{accept}}, cada vuelta siguiente usa una ficha que come y copia el resto: abajo se escribe una configuración un símbolo más corta. Cuando abajo queda qaccept #q_{\text{accept}}\,\mathtt{\#}, la ficha final cierra. Arriba y abajo se lee la misma cadena.

Si hay solución, MM acepta ww. Supongamos una solución que empieza con la ficha 1.

  • Tiene que aparecer qacceptq_{\text{accept}}. La ficha de inicio tiene abajo más símbolos que arriba. Las de los tipos 2 a 5 tienen arriba a lo sumo tantos como abajo. Con esas solas, abajo siempre es más largo y no hay coincidencia. La solución usa entonces alguna ficha de los tipos 6 o 7, y todas tienen a qacceptq_{\text{accept}} arriba. Como arriba y abajo se lee lo mismo, qacceptq_{\text{accept}} aparece en la cadena.
  • Todo lo que se escribe antes es simulación. Miren la cadena hasta la primera aparición de qacceptq_{\text{accept}}. Empieza con #C1#\mathtt{\#} C_1 \mathtt{\#}, por la ficha de inicio. Lo que arriba va cubriendo es lo que abajo ya está escrito, y las fichas no dejan elegir: un símbolo de la cinta lejos de un estado solo se cubre con su ficha de copia; un separador, con una ficha de separador (o con la de inicio, que escribe abajo otra copia de C1C_1); y un estado qq que lee aa solo se cubre con la ficha de δ(q,a)\delta(q, a), que es una sola porque MM es determinista. Entonces, cada vez que arriba se termina de cubrir una configuración CC, abajo quedó escrita la configuración que MM produce desde CC, quizá con un blanco más al final. Todas las configuraciones que aparecen en la cadena son, por lo tanto, la inicial o una que MM alcanza desde ella.
  • Conclusión. La primera configuración con qacceptq_{\text{accept}} la escribió abajo una ficha de transición, así que es una configuración que MM alcanza desde C1C_1. MM acepta ww.

Con las dos direcciones, ATMA_{\mathrm{TM}} se reduce al PCP modificado.

El segundo punto es el delicado de la demostración, y aquí está contado y no desarrollado símbolo por símbolo. Lo acompaña una comprobación: test_tm_pcp genera las fichas de 27 pares de máquina y entrada, las resuelve con la búsqueda en anchura, y verifica que hay solución en los 9 pares en que la máquina acepta y que en ellos la cadena de la solución empieza con la historia de aceptación, revisada con check_history. En los otros 18 no aparece ninguna solución de hasta 40 fichas.

Lo que hace la búsqueda cuando MM no acepta es instructivo. Con la entrada 00\mathtt{00}, la máquina starts_01.tm rechaza en el segundo paso, porque no hay transición para (q1,0)(q_1, \mathtt{0}):

$ build/tm_to_pcp machines/starts_01.tm 00 --mpcp > build/starts_00.pcp
$ build/pcp_solve build/starts_00.pcp 30 --primera
18 fichas, hasta 30 por solución, empezando con la ficha 1
sin solución: la búsqueda se quedó sin excesos nuevos
excesos visitados: 9

La fila se atasca donde se atasca la máquina, y la búsqueda termina. En cambio loop_on_0.tm con 00\mathtt{00} no se detiene nunca, y las fichas tampoco:

$ build/tm_to_pcp machines/loop_on_0.tm 00 --mpcp > build/loop_00.pcp
$ build/pcp_solve build/loop_00.pcp 30 --primera
17 fichas, hasta 30 por solución, empezando con la ficha 1
sin solución hasta 30
excesos visitados: 1201
$ build/pcp_solve build/loop_00.pcp 60 --primera
17 fichas, hasta 60 por solución, empezando con la ficha 1
sin solución hasta 60
excesos visitados: 20359

Con cualquier cota la respuesta será la misma, y la búsqueda no tiene cómo saberlo. Buscar una solución de estas fichas es simular a MM con ww, con otro formato. Un algoritmo que decidiera PCP estaría decidiendo si esa simulación llega a aceptar.

Quitar la condición de la primera ficha

Falta pasar del PCP modificado al PCP sin condiciones. Que la condición importa se ve con las mismas fichas:

$ build/pcp_solve build/starts_01.pcp 30
18 fichas, hasta 30 por solución
solución con 1 ficha: 7
cadena: 0
excesos visitados: 1

Sin la obligación de empezar por la ficha 1, cualquier ficha de copia es una solución por sí sola, y la respuesta ya no dice nada sobre MM.

El arreglo es cambiar las fichas para que solo la de inicio pueda ir primera. Se usan dos símbolos nuevos, ∗\ast y ⋄\diamond (en los archivos, * y $). Para una cadena u=u1u2⋯unu = u_1 u_2 \cdots u_n se definen tres versiones con asteriscos intercalados:

∗u=∗u1∗u2⋯∗un,u∗=u1∗u2∗⋯un∗,∗u∗=∗u1∗u2∗⋯∗un∗.{\ast}u = \ast u_1 \ast u_2 \cdots \ast u_n, \qquad u{\ast} = u_1 \ast u_2 \ast \cdots u_n \ast, \qquad {\ast}u{\ast} = \ast u_1 \ast u_2 \ast \cdots \ast u_n \ast.

Si las fichas del PCP modificado son [t1b1],…,[tkbk]\left[\frac{t_1}{b_1}\right], \ldots, \left[\frac{t_k}{b_k}\right], las del PCP son

[∗t1∗b1∗],[∗t1b1∗],  [∗t2b2∗],  …,  [∗tkbk∗],[∗⋄⋄].\left[\frac{{\ast}t_1}{{\ast}b_1{\ast}}\right],\quad \left[\frac{{\ast}t_1}{b_1{\ast}}\right],\; \left[\frac{{\ast}t_2}{b_2{\ast}}\right],\; \ldots,\; \left[\frac{{\ast}t_k}{b_k{\ast}}\right],\quad \left[\frac{\ast\diamond}{\diamond}\right].

Son k+2k + 2 fichas: una copia especial de la primera, todas las originales transformadas (también la primera) y una de cierre.

  • Solo la primera puede empezar. En todas las demás, arriba empieza con ∗\ast y abajo con un símbolo que no es ∗\ast. La copia especial de la ficha 1 es la única que empieza con ∗\ast en los dos lados.
  • Después, los asteriscos se intercalan solos. Arriba cada símbolo lleva su asterisco antes, y abajo después. Tras la primera ficha, que abajo puso un asterisco inicial de más, las dos cadenas tienen asteriscos en las mismas posiciones, y coinciden exactamente cuando coinciden las originales.
  • El cierre. Arriba termina sin asterisco final y abajo con uno. La ficha [∗⋄⋄]\left[\frac{\ast\diamond}{\diamond}\right] pone el que falta arriba, y solo puede ir al final.

Entonces una solución de las fichas nuevas es una solución de las originales que empieza con la ficha 1, con asteriscos y el cierre, y al revés. La transformación es computable. Con el ejemplo:

$ build/tm_to_pcp machines/starts_01.tm 01 --pcp
# Fichas de machines/starts_01.tm con la entrada 01.
# Estados: A = q0, B = q1, C = q2, D = q_accept, E = q_reject.
dominoes: 20
*# *#*A*0*1*#*
*# #*A*0*1*#*
*A*0 0*B*
*C*0 0*D*
*0*B*1 C*0*1*
*1*B*1 C*1*1*
*_*B*1 C*_*1*
*0 0*
*1 1*
*_ _*
*# #*
*# _*#*
*0*D D*
*1*D D*
*_*D D*
*D*0 D*
*D*1 D*
*D*_ D*
*D*#*# #*
*$ $
$ build/tm_to_pcp machines/starts_01.tm 01 --pcp > build/starts_01_free.pcp
$ build/pcp_solve build/starts_01_free.pcp 30
20 fichas, hasta 30 por solución
solución con 16 fichas: 1 3 9 11 5 11 4 9 11 8 17 11 13 11 19 20
cadena: *#*A*0*1*#*0*B*1*#*C*0*1*#*0*D*1*#*0*D*#*D*#*#*$
excesos visitados: 1226

Ahora la búsqueda no recibe ninguna condición, y la solución es la misma de antes, con una ficha más: cada número subió en uno, salvo el primero, y al final está la ficha 20. Quitando los asteriscos y el $ se lee la misma historia.

Demostración del teorema. La composición de las dos transformaciones es una función computable que manda ⟨M,w⟩\langle M, w \rangle a un conjunto de fichas que tiene solución si y solo si MM acepta ww. Es decir, ATM≤mPCPA_{\mathrm{TM}} \leq_m \mathrm{PCP}. Como ATMA_{\mathrm{TM}} es indecidible, PCP es indecidible. ∎

De paso: PCP es reconocible e indecidible, así que su complemento no es reconocible. No hay un procedimiento que, para toda instancia sin solución, termine diciendo “no tiene”.

Idea clave. Las fichas no calculan. Cada una solo dice “si aquí arriba va esto, aquí abajo va esto otro”. Pero como comprobar un paso de una máquina de Turing es local, esas reglas locales alcanzan para obligar a que la fila entera sea una ejecución correcta. Un problema no necesita hablar de máquinas para contenerlas: le basta poder expresar restricciones entre símbolos vecinos.

¿Genera una gramática todas las cadenas?

En la semana 9 se decidieron dos problemas sobre gramáticas libres de contexto: ACFGA_{\mathrm{CFG}}, si una gramática genera una cadena, y ECFGE_{\mathrm{CFG}}, si no genera ninguna. La pregunta opuesta a la segunda es

ALLCFG={ ⟨G⟩:G es una gramaˊtica libre de contexto y L(G)=Σ∗ }.\mathrm{ALL}_{\mathrm{CFG}} = \{\, \langle G \rangle : G \text{ es una gramática libre de contexto y } L(G) = \Sigma^* \,\}.

Para los DFA las dos preguntas son la misma: L(B)=Σ∗L(B) = \Sigma^* si y solo si el complemento de L(B)L(B) es vacío, y el complemento se obtiene intercambiando estados de aceptación. Con las gramáticas ese camino está cerrado, porque los lenguajes libres de contexto no son cerrados bajo complemento. Podría haber otro camino. No lo hay.

Teorema. ALLCFG\mathrm{ALL}_{\mathrm{CFG}} es indecidible.

La reducción sale de ATMA_{\mathrm{TM}}, y usa las historias de cómputo de una manera que al principio parece al revés. De ⟨M,w⟩\langle M, w \rangle se construye una gramática GG que genera todas las cadenas que no son una historia de aceptación de MM con ww. Entonces:

  • si MM acepta ww, existe la historia de aceptación, que es una cadena que GG no genera, y L(G)≠Σ∗L(G) \neq \Sigma^*;
  • si MM no acepta ww, ninguna cadena es una historia de aceptación, GG las genera todas, y L(G)=Σ∗L(G) = \Sigma^*.

Es decir, MM acepta ww si y solo si ⟨G⟩∉ALLCFG\langle G \rangle \notin \mathrm{ALL}_{\mathrm{CFG}}.

Por qué las cadenas que no son historias sí se pueden generar

Una gramática no puede generar las historias de aceptación. Para eso habría que comprobar que todas las configuraciones seguidas encajan, y con una pila no se comparan más de dos cosas. Pero ser una historia es una conjunción de condiciones, y no serlo es una disyunción: basta que falle una. Una cadena xx no es una historia de aceptación de MM con ww si pasa al menos una de estas cosas:

  1. xx no tiene la forma de configuraciones separadas por #\mathtt{\#};
  2. la primera configuración no es q0 wq_0\,w;
  3. la última no tiene a qacceptq_{\text{accept}};
  4. para algún ii, la configuración CiC_i no produce Ci+1C_{i+1}.

Es más cómodo describir un autómata de pila que una gramática, y en la semana 6 vimos que de un autómata de pila se obtiene una gramática equivalente con un algoritmo. El autómata DD es no determinista y empieza adivinando cuál de las cuatro condiciones va a encontrar violada.

  • Las condiciones 1, 2 y 3 no necesitan la pila. La forma es un lenguaje regular; comparar el principio con la cadena fija q0 wq_0\,w lo hace un autómata finito, porque ww está fijada en la construcción; buscar qacceptq_{\text{accept}} después del último separador, también.
  • La condición 4 es la que usa la pila. DD adivina el ii: avanza hasta algún separador, mete CiC_i en la pila símbolo por símbolo, y al llegar al separador siguiente saca de la pila mientras lee Ci+1C_{i+1}, comparando. Como en la revisión por ventanas, las dos deben ser iguales salvo alrededor del estado, donde deben cambiar según δ\delta; eso se controla con una cantidad fija de memoria en los estados de DD. Si encuentra una posición que no encaja, acepta.

El truco de escribir al revés

Hay un problema con la condición 4. La pila devuelve las cosas en el orden contrario: si se mete CiC_i de izquierda a derecha, sale de derecha a izquierda. Pero Ci+1C_{i+1} se lee de izquierda a derecha. DD estaría comparando el final de una con el principio de la otra.

La solución es cambiar la manera de escribir las historias: las configuraciones pares van al revés.

#  C1  #  C2R  #  C3  #  C4R  #  ⋯  #  Ck  #\mathtt{\#}\; C_1 \;\mathtt{\#}\; C_2^R \;\mathtt{\#}\; C_3 \;\mathtt{\#}\; C_4^R \;\mathtt{\#}\; \cdots \;\mathtt{\#}\; C_k \;\mathtt{\#}

(la última va al derecho o al revés según kk sea impar o par). Así, de cada dos configuraciones seguidas una está al derecho y la otra al revés. Lo que sale de la pila es la primera invertida, y la segunda está escrita invertida respecto de la primera: los símbolos se enfrentan posición por posición. Es la misma razón por la que un autómata de pila reconoce { w#wR }\{\, w\mathtt{\#}w^R \,\} sin esfuerzo.

El programa history escribe esta forma con --alterna:

$ build/history machines/zeros_ones.tm 01 --alterna
C1   q0 0 1
C2   X q1 1
C3   q2 X Y
C4   X q0 Y
C5   X Y q3 _
C6   X Y _ q_accept _
acepta después de 5 pasos
historia: q0 0 1 # 1 q1 X # q2 X Y # Y q0 X # X Y q3 _ # _ q_accept _ Y X

C2C_2, C4C_4 y C6C_6 aparecen invertidas. Cambiar la escritura no cambia nada de lo anterior: MM acepta ww si y solo si existe una historia de aceptación escrita así, y sigue siendo única salvo los blancos.

Escribir al revés no es la única manera de resolverlo, pero es la más directa: deja que la pila haga lo que hace bien.

La demostración

Demostración. Por reducción desde ATMA_{\mathrm{TM}}. Supongamos que RR decide ALLCFG\mathrm{ALL}_{\mathrm{CFG}}, y sea SS:

S = "Con la entrada ⟨M, w⟩, donde M es una máquina de Turing y w una cadena:
  1. Construir el autómata de pila D que acepta las cadenas que no son una historia de
     aceptación de M con w, escrita con las configuraciones pares al revés.
  2. Convertir D en una gramática G equivalente.
  3. Correr R con la entrada ⟨G⟩.
  4. Si R acepta, rechazar. Si R rechaza, aceptar."

SS se detiene siempre: los pasos 1 y 2 escriben descripciones a partir de la tabla de MM y de ww, y RR es un decididor. Si MM acepta ww, la historia de aceptación es una cadena que DD no acepta, L(G)≠Σ∗L(G) \neq \Sigma^*, RR rechaza y SS acepta. Si MM no acepta ww, no existe ninguna historia de aceptación, DD acepta todas las cadenas, L(G)=Σ∗L(G) = \Sigma^*, RR acepta y SS rechaza. SS decide ATMA_{\mathrm{TM}}: contradicción. ∎

Como reducción por función, lo que se construyó es ATM≤mALLCFG‾A_{\mathrm{TM}} \leq_m \overline{\mathrm{ALL}_{\mathrm{CFG}}}, por la inversión del paso 4. Con la propiedad de los complementos, ATM‾≤mALLCFG\overline{A_{\mathrm{TM}}} \leq_m \mathrm{ALL}_{\mathrm{CFG}}: el lenguaje ALLCFG\mathrm{ALL}_{\mathrm{CFG}} no es ni siquiera reconocible. Su complemento sí lo es: se prueban las cadenas una por una con el decididor de ACFGA_{\mathrm{CFG}} de la semana 9, que siempre termina, y se acepta al encontrar una que la gramática no genera.

Aquí no hay programa que acompañe: el autómata DD para una máquina concreta es demasiado grande para leerlo y no enseña más que su descripción. Lo que sí está en el código es la otra mitad del argumento: check_history decide el lenguaje de las historias de aceptación, y el lenguaje de DD es su complemento.

Idea clave. Una gramática no puede verificar una ejecución completa, pero sí puede señalar un error en una ejecución mal hecha, porque un error es una sola posición que no encaja. “Generar todo lo que no es una historia válida” está al alcance de una pila. Preguntar si eso es todo Σ∗\Sigma^* es preguntar si existe una historia válida.

Consecuencias: equivalencia y ambigüedad

La deuda de la semana 9

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) \,\}.

En la semana 9 vimos por qué el método de los DFA no se podía copiar, y quedó dicho que eso no demostraba nada. Ahora sí se demuestra.

Teorema. EQCFG\mathrm{EQ}_{\mathrm{CFG}} es indecidible.

Demostración. Por reducción desde ALLCFG\mathrm{ALL}_{\mathrm{CFG}} hacia EQCFG\mathrm{EQ}_{\mathrm{CFG}}. La dirección sirve porque ALLCFG\mathrm{ALL}_{\mathrm{CFG}} ya se demostró indecidible.

Sea GtodoG_{\text{todo}} la gramática con una variable SS y las reglas S→aSS \to aS para cada símbolo a∈Σa \in \Sigma, más S→εS \to \varepsilon. Genera Σ∗\Sigma^*. La función f(⟨G⟩)=⟨G,Gtodo⟩f(\langle G \rangle) = \langle G, G_{\text{todo}} \rangle es computable, y

⟨G⟩∈ALLCFG  ⟺  L(G)=Σ∗=L(Gtodo)  ⟺  ⟨G,Gtodo⟩∈EQCFG.\langle G \rangle \in \mathrm{ALL}_{\mathrm{CFG}} \iff L(G) = \Sigma^* = L(G_{\text{todo}}) \iff \langle G, G_{\text{todo}} \rangle \in \mathrm{EQ}_{\mathrm{CFG}}.

Entonces ALLCFG≤mEQCFG\mathrm{ALL}_{\mathrm{CFG}} \leq_m \mathrm{EQ}_{\mathrm{CFG}}, y como el primero es indecidible, el segundo también. ∎

Es el mismo movimiento que llevó de ETME_{\mathrm{TM}} a EQTM\mathrm{EQ}_{\mathrm{TM}}: preguntar por una propiedad del lenguaje es un caso particular de comparar con una gramática fija que la tiene.

En la práctica. Dos gramáticas para el mismo lenguaje de programación, la del manual y la que se reescribió para el parser, no se pueden comparar con un algoritmo general. Lo que se hace es probar: generar muchos programas con una y analizarlos con la otra. El complemento de EQCFG\mathrm{EQ}_{\mathrm{CFG}} es reconocible, por la misma búsqueda de antes, así que si las gramáticas difieren hay una cadena que lo muestra, y probando por longitud creciente se la encuentra. Lo que no se puede obtener es la confirmación de que son iguales.

Decidir si una gramática es ambigua

En la semana 5 quedó otra promesa: no hay un algoritmo que diga si una gramática es ambigua, es decir, si alguna cadena tiene dos árboles de derivación.

Teorema. El lenguaje { ⟨G⟩:G es una gramaˊtica libre de contexto ambigua }\{\, \langle G \rangle : G \text{ es una gramática libre de contexto ambigua} \,\} es indecidible.

Se enuncia, con la idea de la demostración. Es una reducción desde PCP: de un conjunto de fichas se construye una gramática que es ambigua exactamente cuando las fichas tienen solución.

Sean las fichas [t1b1],…,[tkbk]\left[\frac{t_1}{b_1}\right], \ldots, \left[\frac{t_k}{b_k}\right]. Se agregan kk terminales nuevos, d1,…,dk\mathtt{d}_1, \ldots, \mathtt{d}_k, uno por ficha, que sirven de etiquetas. La gramática es

S→T∣BT→t1 T d1∣⋯∣tk T dk∣t1 d1∣⋯∣tk dkB→b1 B d1∣⋯∣bk B dk∣b1 d1∣⋯∣bk dk\begin{aligned} S &\to T \mid B \\ T &\to t_1\, T\, \mathtt{d}_1 \mid \cdots \mid t_k\, T\, \mathtt{d}_k \mid t_1\, \mathtt{d}_1 \mid \cdots \mid t_k\, \mathtt{d}_k \\ B &\to b_1\, B\, \mathtt{d}_1 \mid \cdots \mid b_k\, B\, \mathtt{d}_k \mid b_1\, \mathtt{d}_1 \mid \cdots \mid b_k\, \mathtt{d}_k \end{aligned}

Desde TT se generan las cadenas ti1ti2⋯tin din⋯di2di1t_{i_1} t_{i_2} \cdots t_{i_n}\, \mathtt{d}_{i_n} \cdots \mathtt{d}_{i_2} \mathtt{d}_{i_1}: lo que se lee arriba en una fila de fichas, seguido de la lista de las fichas usadas, al revés. Desde BB, lo mismo con las cadenas de abajo.

  • Las etiquetas del final dicen qué reglas se usaron y en qué orden. Por eso cada cadena tiene un solo árbol desde TT, y uno solo desde BB.
  • Una cadena tiene dos árboles solo si se genera desde TT y desde BB. Eso pide las mismas etiquetas, o sea la misma fila de fichas, y la misma cadena antes de las etiquetas: lo de arriba igual a lo de abajo. Es una solución de PCP.
  • Al revés, una solución i1,…,ini_1, \ldots, i_n da una cadena con dos árboles, uno que empieza con S⇒TS \Rightarrow T y otro con S⇒BS \Rightarrow B.

Entonces las fichas tienen solución si y solo si la gramática es ambigua, y la reducción es PCP≤m{ ⟨G⟩:G es ambigua }\mathrm{PCP} \leq_m \{\, \langle G \rangle : G \text{ es ambigua} \,\}. Aquí se ve para qué sirve tener un problema indecidible sin máquinas: reducir desde PCP hacia un problema de gramáticas es mucho más corto que reducir desde ATMA_{\mathrm{TM}}.

El contraste con los autómatas finitos

La misma lista de preguntas, hecha a los tres modelos del curso:

Pregunta DFA Gramática libre de contexto Máquina de Turing
¿Acepta (genera) ww? decidible decidible (ACFGA_{\mathrm{CFG}}) indecidible (ATMA_{\mathrm{TM}})
¿El lenguaje es vacío? decidible decidible (ECFGE_{\mathrm{CFG}}) indecidible (ETME_{\mathrm{TM}})
¿El lenguaje es Σ∗\Sigma^*? decidible indecidible (ALLCFG\mathrm{ALL}_{\mathrm{CFG}}) indecidible
¿Dos son equivalentes? decidible indecidible (EQCFG\mathrm{EQ}_{\mathrm{CFG}}) indecidible (EQTM\mathrm{EQ}_{\mathrm{TM}})
¿El lenguaje es regular? siempre sí indecidible (se enuncia) indecidible (REGULARTM\mathrm{REGULAR}_{\mathrm{TM}})

La columna de los DFA es toda decidible, y por una razón común: los lenguajes regulares son cerrados bajo todas las operaciones booleanas, con construcciones explícitas, y un DFA tiene una cantidad finita de configuraciones. Preguntar si L(B)=Σ∗L(B) = \Sigma^* es preguntar si el complemento es vacío. Preguntar si dos son equivalentes es preguntar si la diferencia simétrica es vacía.

En la columna de las gramáticas aparece la frontera. Las preguntas que se responden mirando hacia adentro del lenguaje, si una cadena está o si hay alguna, siguen siendo decidibles. Las que piden mirar hacia afuera, lo que la gramática no genera, dejan de serlo. El motivo es el de esta semana: lo que una gramática no genera puede ser el conjunto de las ejecuciones correctas de una máquina de Turing.

En la columna de las máquinas de Turing no queda nada, y el teorema de Rice dice que no es casualidad.

Hay un precio que se paga por el poder de expresión. Cada modelo más capaz reconoce más lenguajes, y de cada modelo más capaz se puede averiguar menos. Quien diseña un lenguaje de configuración, un formato de reglas o un lenguaje de consultas elige en qué columna quiere estar: si las reglas son expresiones regulares, se puede comprobar automáticamente que dos conjuntos de reglas hacen lo mismo. Si son programas, no.

El código de la semana

code/week-10/
├── tm.h                  struct Tm, lectura del formato .tm, simulación, historias y check_history
├── history.cpp           escribe la historia de cómputo de una máquina con una entrada
├── check_history.cpp     comprueba una historia ventana por ventana
├── fix_input.h           la construcción de M_w: fijar la entrada dentro de la máquina
├── fix_input.cpp         escribe M_w en formato .tm
├── pcp.h                 fichas, comprobación de una solución y las dos búsquedas
├── pcp_check.cpp         ¿es esta secuencia de fichas una solución?
├── pcp_solve.cpp         búsqueda en anchura sobre el exceso, con cota
├── pcp_meet.cpp          búsqueda desde los dos extremos
├── tm_pcp.h              de una máquina y una entrada a un conjunto de fichas
├── tm_to_pcp.cpp         muestra o escribe esas fichas
├── machines/             cuatro máquinas pequeñas, en formato .tm
├── instances/            las instancias de PCP del capítulo
├── errors/               una descripción no determinista, que los programas rechazan
├── test_fix_input.cpp    L(M_w) es {w} o ∅, según M acepte w
├── test_history.cpp      las historias del capítulo y el comprobador
├── test_pcp.cpp          las instancias del capítulo; la búsqueda contra la fuerza bruta
├── test_tm_pcp.cpp       las fichas tienen solución exactamente cuando la máquina acepta
└── lab/pcp_search/       el laboratorio

make compila todo, y make test corre las pruebas con ASan y UBSan. Tarda más que en otras semanas, casi todo en las búsquedas de test_tm_pcp.

$ make test
test_fix_input: ok (124 pares de máquina y w, 63 entradas cada uno)
test_history: ok (5 historias, 8250 cambios de un símbolo, todos detectados)
test_pcp: ok (3000 instancias al azar, 780 con solución)
test_tm_pcp: ok (27 pares de máquina y entrada, 9 con aceptación; sin solución hasta 40 fichas en los demás)
Todas las pruebas pasaron.

Qué comprueba cada una:

  • test_fix_input construye MwM_w para cuatro máquinas y cada ww de longitud a lo sumo 4, y la corre con cada xx de longitud a lo sumo 5, con un tope de pasos. MwM_w rechaza toda x≠wx \neq w, y con ww hace lo que MM: acepta, rechaza o sigue corriendo.
  • test_history comprueba las historias copiadas en este capítulo, que la máquina de zeros_ones.tm acepta exactamente las cadenas 0n1n\mathtt{0}^n\mathtt{1}^n entre las 511 de longitud a lo sumo 8, y que check_history rechaza cualquier historia con un símbolo cambiado.
  • test_pcp comprueba cada instancia de instances/ con lo que el capítulo dice de ella, y compara la búsqueda en anchura y la búsqueda desde los dos extremos con la fuerza bruta, que prueba todas las secuencias, en 3000 instancias pequeñas al azar.
  • test_tm_pcp es la comprobación de la reducción, descrita en Por qué funciona.

Las máquinas de machines/:

Archivo Qué hace Para qué se usa
starts_01.tm acepta las cadenas que empiezan con 01\mathtt{01} MwM_w; las fichas del ejemplo
zeros_ones.tm decide {0n1n}\{\mathtt{0}^n\mathtt{1}^n\} las historias de cómputo
loop_on_0.tm no se detiene si la entrada es 0\mathtt{0} seguido de ceros simular con tope; fichas sin final
empty_ok.tm acepta solo ε\varepsilon el caso w=εw = \varepsilon de las fichas

Dos decisiones del código que conviene conocer antes de leerlo.

  • En tm.h una historia es una lista de símbolos (std::vector<std::string>), porque el nombre de un estado tiene varios caracteres. En tm_pcp.h cada estado se cambia por una letra mayúscula, porque en una ficha cada símbolo tiene que ser un carácter. tm_to_pcp imprime la correspondencia.
  • Un archivo de fichas empieza con dominoes: k y sigue con kk líneas arriba abajo. Después de esa línea no hay comentarios: las fichas de una máquina usan # como símbolo.

tm_to_pcp supone, como la demostración, que la máquina no intenta moverse a la izquierda desde la primera celda. Con una máquina que sí lo hace, las fichas que escribe no corresponden a su ejecución.

El laboratorio

En lab/pcp_search está el enunciado, un esqueleto, el verificador y los casos. La entrada es un conjunto de fichas y una cota NN; la salida, los números de las fichas de una solución de a lo sumo NN fichas, o sin solución hasta N.

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

Una instancia puede tener muchas soluciones, así que el juez no compara texto: usa verificador.cpp, que pone las fichas de la respuesta y compara las dos cadenas. El trabajo es la búsqueda en anchura sobre el exceso, con el conjunto de visitados. Probar todas las secuencias da TLE en cuanto la solución pasa de unas quince fichas, y el caso 09 pide 45. pcp.h trae una búsqueda que pueden leer; la del laboratorio se escribe en un solo archivo, sin incluirla, y tiene que reconstruir la secuencia.

El enunciado termina con tres preguntas para responder por escrito. La primera es la del paso 5 de la guía: por qué el programa, sin la cota, reconoce PCP y no lo decide.

Resumen

  • Una reducción de AA a BB resuelve AA usando una solución de BB. Si AA es indecidible, BB también. Para demostrar que BB es indecidible se reduce desde un indecidible conocido hacia BB. La dirección contraria no demuestra nada.
  • HALTTM\mathrm{HALT}_{\mathrm{TM}} es indecidible: con un decididor suyo, se sabría cuándo es seguro simular, y se decidiría ATMA_{\mathrm{TM}}.
  • Fijar la entrada dentro de la máquina: de ⟨M,w⟩\langle M, w \rangle se construye una máquina cuyo lenguaje es uno de dos según MM acepte o no ww. Con {w}\{w\} y ∅\emptyset sale ETME_{\mathrm{TM}}; con Σ∗\Sigma^* y {0n1n}\{\mathtt{0}^n\mathtt{1}^n\}, REGULARTM\mathrm{REGULAR}_{\mathrm{TM}}. La construcción escribe una descripción y no ejecuta nada.
  • EQTM\mathrm{EQ}_{\mathrm{TM}} es indecidible, reduciendo desde ETME_{\mathrm{TM}}: se compara con una máquina que rechaza todo.
  • Reducción por función: A≤mBA \leq_m B si hay una función computable ff con w∈A  ⟺  f(w)∈Bw \in A \iff f(w) \in B. Lo decidible y lo reconocible bajan de BB a AA; lo indecidible y lo no reconocible suben de AA a BB. A≤mBA \leq_m B equivale a A‾≤mB‾\overline{A} \leq_m \overline{B}.
  • ETME_{\mathrm{TM}} no es reconocible. EQTM\mathrm{EQ}_{\mathrm{TM}} no es reconocible y su complemento tampoco: se reduce ATMA_{\mathrm{TM}} a cada uno de los dos.
  • Teorema de Rice: toda propiedad no trivial del lenguaje de una máquina es indecidible. Hay que comprobar que depende solo de L(M)L(M) y dar una máquina que la tiene y otra que no.
  • Rice no habla de las propiedades de la máquina: la cantidad de estados o detenerse en 100 pasos son decidibles. Otras, como detenerse con una entrada, son indecidibles por una reducción propia.
  • Una historia de cómputo es la secuencia de configuraciones C1#C2#⋯#CkC_1 \mathtt{\#} C_2 \mathtt{\#} \cdots \mathtt{\#} C_k de una ejecución que acepta. Existe si y solo si MM acepta ww. Comprobarla es local: entre dos configuraciones seguidas solo cambian el estado y sus dos vecinos.
  • PCP: fichas con una cadena arriba y otra abajo; ¿alguna fila da la misma cadena en los dos lados? Es reconocible, buscando por longitud creciente, y es indecidible: las fichas se pueden diseñar para que la única fila que coincide sea una historia de aceptación, con abajo una configuración adelantado.
  • La búsqueda solo necesita recordar el exceso. Puede terminar con una solución, con “sin solución” si el grafo de excesos es finito, o no terminar. Por eso responde sin solución hasta N.
  • ALLCFG\mathrm{ALL}_{\mathrm{CFG}} es indecidible: una gramática puede generar todo lo que no es una historia de aceptación, porque para eso basta señalar un error. De ahí, EQCFG\mathrm{EQ}_{\mathrm{CFG}} es indecidible. Decidir si una gramática es ambigua también, reduciendo desde PCP.
  • Con los DFA todas esas preguntas eran decidibles. Más poder de expresión es menos posibilidad de análisis.

Ejercicios

  1. Para cada afirmación, digan qué se puede concluir sobre BB, o si no se puede concluir nada: (a) ATM≤mBA_{\mathrm{TM}} \leq_m B; (b) B≤mATMB \leq_m A_{\mathrm{TM}}; (c) B≤mADFAB \leq_m A_{\mathrm{DFA}}; (d) ATM‾≤mB\overline{A_{\mathrm{TM}}} \leq_m B; (e) ADFA≤mBA_{\mathrm{DFA}} \leq_m B; (f) ATM≤mBA_{\mathrm{TM}} \leq_m B y ATM≤mB‾A_{\mathrm{TM}} \leq_m \overline{B}. Después respondan la pregunta 3 de la guía: si A≤mBA \leq_m B y BB es reconocible, ¿qué se sabe de AA? ¿Y si AA no es reconocible, qué se sabe de BB?
  2. Demuestren que { ⟨M⟩:M acepta la cadena vacıˊa }\{\, \langle M \rangle : M \text{ acepta la cadena vacía} \,\} es indecidible con una reducción desde ATMA_{\mathrm{TM}}, escribiendo la máquina que se construye, la máquina SS y las dos direcciones. Después demuéstrenlo otra vez con el teorema de Rice, comprobando las dos condiciones. ¿Es reconocible ese lenguaje?
  3. Para cada propiedad, digan si el teorema de Rice se aplica. Si se aplica, den las dos máquinas. Si no, digan cuál hipótesis falla y, si pueden, si la propiedad es decidible: (a) L(M)L(M) tiene exactamente 10 cadenas; (b) MM tiene más de 10 transiciones; (c) L(M)=L(M)RL(M) = L(M)^R; (d) MM escribe alguna vez un blanco sobre un símbolo que no lo es, con alguna entrada; (e) L(M)L(M) es decidible; (f) L(M)L(M) es reconocible; (g) MM nunca mueve el cabezal a la izquierda en sus primeros 50 pasos, con ninguna entrada; (h) MM acepta alguna cadena de longitud par.
  4. Demuestren que { ⟨M⟩:M se detiene con la entrada 0 }\{\, \langle M \rangle : M \text{ se detiene con la entrada } \mathtt{0} \,\} es indecidible, reduciendo desde HALTTM\mathrm{HALT}_{\mathrm{TM}}. Expliquen por qué el teorema de Rice no sirve aquí, con dos máquinas que reconozcan el mismo lenguaje y den respuestas distintas.
  5. Demuestren: (a) si A≤mBA \leq_m B y B≤mCB \leq_m C, entonces A≤mCA \leq_m C; (b) si AA es decidible y BB es cualquier lenguaje distinto de ∅\emptyset y de Σ∗\Sigma^*, entonces A≤mBA \leq_m B; (c) si AA es reconocible y A≤mA‾A \leq_m \overline{A}, entonces AA es decidible. ¿Por qué (b) excluye a ∅\emptyset y a Σ∗\Sigma^*?
  6. Sea ALLTM={ ⟨M⟩:L(M)=Σ∗ }\mathrm{ALL}_{\mathrm{TM}} = \{\, \langle M \rangle : L(M) = \Sigma^* \,\}. (a) Demuestren que es indecidible con Rice. (b) Demuestren que ATM≤mALLTMA_{\mathrm{TM}} \leq_m \mathrm{ALL}_{\mathrm{TM}} y concluyan que su complemento no es reconocible. (c) Más difícil: demuestren que ALLTM\mathrm{ALL}_{\mathrm{TM}} tampoco es reconocible, con una reducción ATM‾≤mALLTM\overline{A_{\mathrm{TM}}} \leq_m \mathrm{ALL}_{\mathrm{TM}}. Sugerencia: una máquina que, con la entrada xx, corre MM con ww durante ∣x∣|x| pasos y acepta si en ese tiempo MM no aceptó.
  7. Escriban a mano las primeras seis configuraciones de machines/zeros_ones.tm con la entrada 0011\mathtt{0011} y comprueben con build/history. Marquen, entre cada par de configuraciones seguidas, los tres símbolos que podían cambiar. Después escriban una cadena que pase tres de las cuatro revisiones de check_history y falle la otra, una por cada revisión, y comprueben con el programa qué mensaje da.
  8. Un estado de una máquina es inútil si la máquina no entra en él con ninguna entrada. Demuestren que { ⟨M,q⟩:q es un estado inuˊtil de M }\{\, \langle M, q \rangle : q \text{ es un estado inútil de } M \,\} es indecidible, reduciendo desde ETME_{\mathrm{TM}}. Sugerencia: ¿cuándo es inútil qacceptq_{\text{accept}}? ¿Por qué no se puede resolver buscando caminos en el diagrama de estados, como con un DFA?
  9. Encuentren una solución de cada conjunto de fichas, o argumenten por qué no existe. Háganlo primero a mano, siguiendo el exceso, y comprueben con pcp_check o pcp_solve. (a) [abaa],[abaa],[bbabb]\left[\frac{\mathtt{a}}{\mathtt{baa}}\right], \left[\frac{\mathtt{ab}}{\mathtt{aa}}\right], \left[\frac{\mathtt{bba}}{\mathtt{bb}}\right]; (b) [ababa],[baaaa],[ababaa]\left[\frac{\mathtt{ab}}{\mathtt{aba}}\right], \left[\frac{\mathtt{baa}}{\mathtt{aa}}\right], \left[\frac{\mathtt{aba}}{\mathtt{baa}}\right]; (c) las cuatro fichas de instances/four_66.pcp. Para (c) no lo intenten a mano: ¿cuántas fichas tiene la solución más corta, y cuántos excesos visita la búsqueda?
  10. Demuestren que PCP con un alfabeto de un solo símbolo es decidible. Sugerencia: solo importan las longitudes. ¿Qué pasa si hay una ficha con arriba más largo y otra con abajo más largo? ¿Dónde falla el argumento con dos símbolos?
  11. Escriban a mano las fichas de la demostración para machines/empty_ok.tm con la entrada ε\varepsilon, y una solución que empiece con la ficha de inicio. Comprueben con build/tm_to_pcp machines/empty_ok.tm eps y con pcp_solve --primera. Después expliquen qué fichas habría que agregar para no tener que suponer que la máquina nunca se mueve a la izquierda desde la primera celda, con la convención del curso de que en ese caso el cabezal se queda donde está, y qué dificultad aparece con la ficha de inicio.
  12. Demuestren que son indecidibles: (a) { ⟨G,H⟩:L(G)⊆L(H) }\{\, \langle G, H \rangle : L(G) \subseteq L(H) \,\}, para gramáticas libres de contexto; (b) { ⟨G,r⟩:L(G)=L(r) }\{\, \langle G, r \rangle : L(G) = L(r) \,\}, con GG una gramática y rr una expresión regular. Y demuestren que este sí es decidible: (c) { ⟨G,r⟩:L(G)⊆L(r) }\{\, \langle G, r \rangle : L(G) \subseteq L(r) \,\}. Sugerencia para (c): la intersección de un lenguaje libre de contexto con uno regular es libre de contexto, y la construcción es un algoritmo.
  13. Para programar. Escriban un programa que lea un conjunto de fichas en el formato de instances/ y escriba, en el formato .cfg de code/formats.md, la gramática de la sección Decidir si una gramática es ambigua, usando como etiquetas símbolos que no aparezcan en las fichas. Con las fichas de instances/sipser.pcp, escriban la cadena que corresponde a la solución 2 1 3 2 4 y sus dos derivaciones por la izquierda.
  14. Para programar. Modifiquen pcp_solve.cpp para que imprima cuántos excesos nuevos aparecen en cada nivel de la búsqueda. Córranlo con instances/long.pcp y con instances/hard_75.pcp. ¿En cuál crece la cantidad de un nivel al siguiente, y más o menos por cuánto se multiplica? Estimen cuántos excesos tendría que guardar la búsqueda para llegar al nivel 75.