# Cook-Levin ejecutado: de una máquina a una fórmula

El teorema de Cook-Levin dice que de cualquier máquina de Turing no determinista $N$ de tiempo polinomial y
cualquier entrada $w$ se puede escribir, en tiempo polinomial, una fórmula booleana que es satisfacible
exactamente cuando $N$ acepta $w$. La demostración es una construcción, y una construcción se puede programar.
En este laboratorio escriben esa reducción: su programa recibe una máquina pequeña, una cadena y el lado de un
tableau, y escribe la fórmula. Después `minisat` la resuelve y de la asignación sale, celda por celda, una
ejecución de la máquina.

Su programa **no simula** la máquina. Describe cómo se ve una ejecución que acepta, y deja que otro la busque.

## El tableau

Un **tableau** de lado $t$ es una tabla de $t \times t$ celdas. Cada fila es una configuración de la máquina,
escrita así:

$$
\mathtt{\#}\; u\; q\; v\; \mathtt{\#}
$$

La primera y la última celda de la fila contienen $\mathtt{\#}$. Entre ellas hay $t - 2$ celdas: una contiene
el estado $q$ y las otras $t - 3$ son las primeras $t - 3$ celdas de la cinta. El estado va justo antes de la
celda que lee el cabezal, así que **a la derecha del estado siempre hay al menos una celda de la cinta**: un
estado nunca queda pegado a la $\mathtt{\#}$ derecha.

La fila 1 es la configuración inicial con $w$. Cada fila siguiente sale de la anterior por un paso de la
máquina. Si una fila ya está en $q_{\text{accept}}$, la siguiente es igual: la configuración que acepta se repite
hasta llenar la tabla. Este es el tableau de `casos/01.in`, la máquina que acepta las cadenas con
$\mathtt{11}$, con $w = \mathtt{011}$ y $t = 7$:

```text
#        q0       0        1        1        _        #
#        0        q0       1        1        _        #
#        0        1        q1       1        _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
```

Decimos que una ejecución **cabe** en el tableau de lado $t$ si tiene a lo sumo $t - 1$ pasos y el cabezal no
sale de las primeras $t - 3$ celdas de la cinta. La fórmula que van a escribir es satisfacible si y solo si
alguna ejecución de $N$ que acepta $w$ cabe en el tableau. Con $w = \mathtt{011}$ y $t = 6$ la respuesta es no:
la máquina acepta, pero al aceptar el cabezal está en la cuarta celda, y en una fila de 6 solo hay 3.

## Entrada

Una máquina de Turing en el formato `.tm` de [`code/formats.md`](../../../formats.md), con varias líneas para
un mismo par de estado y símbolo cuando es no determinista. Después, el bloque de cadenas del mismo documento
con una sola cadena, $w$, y una última línea con el lado del tableau:

```text
# Acepta las cadenas binarias que contienen 11.
states: q0 q1 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q0 0 R
q0 1 -> q0 1 R
q0 1 -> q1 1 R
q1 1 -> q_accept 1 R
strings: 1
011
tableau: 7
```

- La línea de $w$ puede estar vacía: es la cadena $\varepsilon$.
- Un par de estado y símbolo sin línea no tiene movimientos: esa rama rechaza. `delta:` puede no tener
  ninguna línea.
- La cinta es infinita solo hacia la derecha, y un movimiento `L` en la primera celda deja el cabezal donde
  está.
- Desde `accept` y desde `reject` no sale ninguna transición.

## Salida

Una fórmula en CNF en formato DIMACS: la línea `p cnf V M`, con la cantidad de variables y de cláusulas, y
después las $M$ cláusulas, cada una terminada en `0`. Es el formato que usaron con `minisat` en Algoritmos.

### Las variables

Sea $C = \Gamma \cup Q \cup \{\mathtt{\#}\}$ el conjunto de lo que puede contener una celda. Sus elementos se
numeran desde 0: primero los símbolos de la cinta, en el orden de la línea `tape:`; después los estados, en el
orden de `states:`; al final $\mathtt{\#}$. En el ejemplo, $|C| = 8$:

| $s$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| contenido | `0` | `1` | `_` | `q0` | `q1` | `q_accept` | `q_reject` | `#` |

La variable $x_{i,j,s}$ dice "la celda de la fila $i$ y la columna $j$ contiene $s$", con $1 \leq i, j \leq t$.
Su número en DIMACS está fijado:

$$
x_{i,j,s} \;\mapsto\; \bigl((i - 1)\,t + (j - 1)\bigr)\,|C| + s + 1
$$

Son las variables $1, 2, \ldots, t^2\,|C|$. La función `cell_var` del esqueleto es esta fórmula. **Esta
numeración es obligatoria**: el verificador la usa para leer su fórmula. Pueden agregar las variables
auxiliares que necesiten, con números mayores que $t^2\,|C|$.

### Los cuatro grupos de cláusulas

**Grupo 1: cada celda tiene exactamente un símbolo.** Ya está escrito en el esqueleto. Por cada celda, una
cláusula que dice "al menos uno" y, por cada par de símbolos, una que dice "no los dos":

$$
\bigwedge_{1 \leq i, j \leq t} \Bigl[\; \bigvee_{s \in C} x_{i,j,s} \;\land \bigwedge_{s \neq s'} \bigl(\lnot x_{i,j,s} \lor \lnot x_{i,j,s'}\bigr) \Bigr]
$$

**Grupo 2: la primera fila es la configuración inicial.** Con $w = w_1 \cdots w_n$, son $t$ cláusulas de un
literal:

$$
x_{1,1,\mathtt{\#}} \land x_{1,2,q_0} \land x_{1,3,w_1} \land \cdots \land x_{1,n+2,w_n} \land x_{1,n+3,\sqcup} \land \cdots \land x_{1,t-1,\sqcup} \land x_{1,t,\mathtt{\#}}
$$

**Grupo 3: cada ventana es legal.** Una **ventana** son seis celdas, tres de una fila y las tres de abajo: las
columnas $j$, $j + 1$, $j + 2$ de las filas $i$ e $i + 1$. Hay $(t - 1)(t - 2)$ posiciones. Una ventana es
**legal** si aparece en algún paso de la máquina; la lista exacta está en la sección siguiente. El grupo dice:

$$
\bigwedge_{\substack{1 \leq i \leq t-1 \\ 1 \leq j \leq t-2}} \;\; \bigvee_{(a_1 a_2 a_3 / b_1 b_2 b_3) \text{ legal}} \bigl( x_{i,j,a_1} \land x_{i,j+1,a_2} \land x_{i,j+2,a_3} \land x_{i+1,j,b_1} \land x_{i+1,j+1,b_2} \land x_{i+1,j+2,b_3} \bigr)
$$

Eso no está en CNF. Para pasarlo sin que crezca, por cada posición $(i, j)$ y cada ventana legal $k$ se crea
una variable nueva $z_{i,j,k}$, "en esta posición está la ventana $k$", con seis cláusulas de dos literales y,
por cada posición, una cláusula larga:

$$
(\lnot z_{i,j,k} \lor x_{i,j,a_1}) \land \cdots \land (\lnot z_{i,j,k} \lor x_{i+1,j+2,b_3}) \qquad\text{y}\qquad \bigvee_{k} z_{i,j,k}
$$

**Grupo 4: alguna celda contiene $q_{\text{accept}}$.** Una sola cláusula con $t^2$ literales:

$$
\bigvee_{1 \leq i, j \leq t} x_{i,j,q_{\text{accept}}}
$$

### Las ventanas legales

En lo que sigue, $(r, b, D) \in \delta(q, a)$ es una línea `q a -> r b D` de la máquina. Una ventana se
escribe con su fila de arriba y su fila de abajo. Hay cuatro formas, según dónde esté el estado en la fila de
arriba, y un caso más para la aceptación.

| Forma | Arriba | Abajo | Cuándo |
|---|---|---|---|
| 1. Estado en el centro | $x\;q\;a$, con $x \in \Gamma \cup \{\mathtt{\#}\}$ | $x\;b\;r$ | $(r, b, \mathrm{R}) \in \delta(q, a)$ |
| | | $r\;x\;b$ | $(r, b, \mathrm{L}) \in \delta(q, a)$ y $x \in \Gamma$ |
| | | $\mathtt{\#}\;r\;b$ | $(r, b, \mathrm{L}) \in \delta(q, a)$ y $x = \mathtt{\#}$ |
| 2. Estado a la izquierda | $q\;a\;y$, con $y \in \Gamma \cup \{\mathtt{\#}\}$ | $b\;r\;y$ | $(r, b, \mathrm{R}) \in \delta(q, a)$ y $y \in \Gamma$ |
| | | $x\;b\;y$, para cada $x \in \Gamma$ | $(r, b, \mathrm{L}) \in \delta(q, a)$ |
| | | $r\;b\;y$ | $(r, b, \mathrm{L}) \in \delta(q, a)$ |
| 3. Estado a la derecha | $z\;x\;q$, con $z \in \Gamma \cup \{\mathtt{\#}\}$ y $x \in \Gamma$ | $z\;x\;b$ | $(r, b, \mathrm{R}) \in \delta(q, a)$ para algún $a$ |
| | | $z\;r\;x$ | $(r, b, \mathrm{L}) \in \delta(q, a)$ para algún $a$ |
| 4. Sin estado | $y_1\;y_2\;y_3$, con $y_2 \in \Gamma$ e $y_1, y_3 \in \Gamma \cup \{\mathtt{\#}\}$, no los dos $\mathtt{\#}$ | $y_1\;y_2\;y_3$ | siempre |
| | | $r\;y_2\;y_3$ | $(r, b, \mathrm{R}) \in \delta(q, y_1)$ para algún $q$ |
| | | $b\;y_2\;y_3$ | $(r, b, \mathrm{L}) \in \delta(q, y_1)$ para algún $q$ |
| | | $y_1\;y_2\;r$ | $y_3 \in \Gamma$ y $(r, b, \mathrm{L}) \in \delta(q, a)$ para algunos $q$, $a$ |
| Aceptación | $x\;q_{\text{accept}}\;a$, $\;q_{\text{accept}}\;a\;x$, $\;x\;a\;q_{\text{accept}}$, con $a \in \Gamma$ y $x \in \Gamma \cup \{\mathtt{\#}\}$ | igual a la de arriba | siempre |

Cómo leerla:

- **Forma 1.** La ventana ve el estado, lo que lee y lo que tiene a su izquierda: todo lo que un paso puede
  cambiar. Con $\mathrm{R}$, el estado avanza una celda. Con $\mathrm{L}$, retrocede una; si a su izquierda
  está la $\mathtt{\#}$, se queda donde está.
- **Forma 2.** La ventana no ve qué hay a la izquierda del estado. Con $\mathrm{L}$, ese símbolo desconocido
  $x$ baja a la primera celda de la ventana; o el estado estaba en la primera celda de la cinta y se queda.
  Con $\mathrm{R}$ hace falta que $y$ sea un símbolo de la cinta: si $y = \mathtt{\#}$, al estado no le
  quedaría celda para leer, y esa ventana **no** es legal.
- **Forma 3.** La ventana no ve qué lee el estado, así que vale cualquier movimiento desde $q$.
- **Forma 4.** Lejos del cabezal nada cambia. Las otras tres líneas son el estado que está justo fuera de la
  ventana: a la izquierda, leyendo $y_1$, o a la derecha, entrando con un movimiento $\mathrm{L}$. En todas,
  la celda del centro se copia.
- Una $\mathtt{\#}$ siempre tiene debajo una $\mathtt{\#}$, y solo ella.

Con la máquina del ejemplo salen 193 ventanas legales, de las $8^6 = 262\,144$ maneras de llenar seis celdas:
28 con el estado en el centro, 24 con el estado a la izquierda, 48 con el estado a la derecha y 93 sin estado
arriba. Úsenlo para comprobar su `legal_windows` antes de seguir. Por ejemplo, para la línea
`q0 1 -> q1 1 R`:

```text
0 q0 1        0 q0 1        q0 1 #
0 1  q1       0 0  q1       1  q1 #
legal         ilegal        ilegal
```

La segunda escribe un $\mathtt{0}$ donde la línea dice $\mathtt{1}$. La tercera deja el estado pegado a la
$\mathtt{\#}$.

## Límites

- $1 \leq |Q| \leq 8$ y $2 \leq |\Gamma| \leq 6$. El símbolo blanco `_` está en `tape:`.
- El nombre de un estado tiene entre 1 y 20 caracteres visibles, no empieza con `#`, no termina con `:` y no
  es igual a ningún símbolo de la cinta. Un nombre puede ser prefijo de otro (`q1` y `q10`).
- $4 \leq t \leq 30$ y $|w| \leq t - 3$, de modo que la configuración inicial siempre cabe en la fila 1.
- `start`, `accept` y `reject` son estados de `states:`, y `accept` es distinto de `reject`. El estado
  inicial puede ser el de aceptación.
- La fórmula descrita arriba tiene, en todos los casos, menos de 1 200 000 cláusulas. El verificador rechaza
  una salida con más de 2 000 000 de variables o más de 4 000 000 de cláusulas.
- La entrada siempre es válida: no tienen que detectar errores.

## Ejemplo

Para la entrada de arriba, la salida de la solución de referencia empieza así:

```text
p cnf 6182 36199
1 2 3 4 5 6 7 8 0
-1 -2 0
```

Las 392 primeras variables son las de las celdas, $7^2 \cdot 8$, y las otras 5790 son las $z$: 30 posiciones
de ventana por 193 ventanas legales. Las cláusulas son 1421 del grupo 1, 7 del grupo 2, 34 770 del grupo 3 y
1 del grupo 4. La primera cláusula dice que la celda $(1, 1)$ contiene alguno de los 8 símbolos, y la segunda,
que no contiene a la vez el de número 0 y el de número 1.

Su salida no tiene que ser igual a esa: pueden escribir las cláusulas en otro orden, numerar las $z$ de otra
manera o pasar el grupo 3 a CNF de otra forma. Lo que se revisa es lo que la fórmula **dice**.

## Cómo se revisa

Una fórmula no es única, así que el juez no compara textos. Usa `verificador.cpp`, que hace cuatro cosas con
su salida:

1. Comprueba que es DIMACS bien formado y que declara al menos las $t^2\,|C|$ variables de las celdas.
2. Corre `minisat` y compara con la primera línea de `casos/NN.out`, que dice `satisfacible` o
   `insatisfacible`.
3. Si el caso es satisfacible, `casos/NN.out` trae varios tableaux. Los marcados con `si` son ejecuciones que
   aceptan: el verificador fija cada celda con la numeración del enunciado y su fórmula debe seguir siendo
   satisfacible. Los marcados con `no` no lo son, y la línea dice por qué: la primera fila es otra, hay una
   ventana ilegal, ninguna fila acepta. Con ellos fijados, su fórmula debe ser insatisfacible.
4. Comprueba que su fórmula no admite una celda con dos símbolos ni una celda vacía.

El paso 3 existe porque una fórmula puede ser satisfacible por la razón equivocada. Si olvidan el grupo 2, la
fórmula del ejemplo sigue siendo satisfacible, pero también admite un tableau cuyas filas son todas
`# q_accept _ _ _ _ #`, que no tiene nada que ver con $w$. Cuando el juez da `WA`, el mensaje dice qué tableau
de `casos/NN.out` falló: ábranlo y miren qué grupo debía rechazarlo.

## Tiempo

2 segundos por caso para escribir la fórmula. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`. El tiempo
de `minisat` no cuenta.

Hay otra manera de pasar el grupo 3 a CNF, sin variables nuevas: por cada posición, una cláusula de seis
literales negados por cada ventana **ilegal**. Es correcta, pero son $|C|^6$ menos las legales: en el ejemplo,
261 951 cláusulas por posición en lugar de 1159. Con $t = 7$ ya serían casi 8 millones de cláusulas, y el
verificador no las acepta.

## Cómo avanzar

```sh
make        # compila solution.cpp y decode.cpp en build/
make test   # corre el juez con todos los casos
```

`solution.cpp` ya lee la entrada, numera las variables y escribe el grupo 1. Tal como está, el juez da `WA`
en todos los casos: una fórmula con solo el grupo 1 la cumple cualquier tabla.

1. **Grupo 2.** Escriban `add_start_clauses`. Cuiden las dos $\mathtt{\#}$ y los blancos después de $w$: si
   faltan, la primera fila puede continuar con cualquier cosa.
2. **Las ventanas.** Escriban `legal_windows` siguiendo la tabla, forma por forma, y cuenten: con
   `casos/01.in` deben salir 193.
3. **Grupo 3.** Escriban `add_move_clauses`. Cada variable nueva sale de `f.fresh()`.
4. **Grupo 4.** Escriban `add_accept_clause` y corran el juez.

### Decodificar el tableau

`decode.cpp` ya está escrito. Lee el caso y el archivo que deja `minisat`, imprime el tableau y lo comprueba
sin usar la fórmula: mira si cada fila sale de la anterior por un paso de la máquina.

```text
$ build/solution < casos/01.in > f.cnf
$ minisat -verb=0 f.cnf f.res
SATISFIABLE
$ build/decode casos/01.in f.res
#        q0       0        1        1        _        #
#        0        q0       1        1        _        #
#        0        1        q1       1        _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
es una ejecución de la máquina: acepta en 3 pasos
```

`minisat` termina con el código 10 si la fórmula es satisfacible y con 20 si no lo es. Mientras les falten
grupos, `decode` es la mejor herramienta para depurar: muestra qué tabla encontró `minisat` y cuál es la
primera fila que no cuadra. Con el esqueleto sin tocar y `casos/02.in`, por ejemplo, sale una tabla sin
sentido y el aviso `la fila 1 no es una configuración # u q v #`.

Lean en el tableau lo que hizo `minisat`: la máquina del ejemplo es no determinista, y en la fila 2 hay que
elegir entre seguir en `q0` o pasar a `q1`. Nadie programó esa elección. La fórmula solo dice que alguna
celda debe contener `q_accept`, y el solucionador encontró la rama.

### Comparar con el simulador

`casos/11.in` y `casos/21.in` usan una máquina determinista: la de $\{\mathtt{0}^n\mathtt{1}^n\}$ de
`code/formats.md`, con $\mathtt{01}$ y con $\mathtt{0011}$. Corran su simulador de la semana 7 con esa
máquina y esas cadenas, con la opción que imprime las configuraciones, y pongan su salida al lado del tableau
decodificado. Deben coincidir fila por fila: la fila $i$ del tableau es la configuración después de $i - 1$
pasos, con la cinta completada con blancos y entre dos $\mathtt{\#}$. Con una máquina determinista hay un solo
tableau posible, y `minisat` no tiene nada que elegir.

Para una máquina no determinista, `build/run_ntm` de `code/week-13` muestra el árbol de ejecuciones por
niveles: el tableau es una de sus ramas.

### Contar

Con la máquina de `casos/01.in`, cambien la última línea de la entrada y anoten el encabezado `p cnf` para
$t = 5$, 10 y 20. Con $t = 5$ deben salir 2516 variables y 14 639 cláusulas. Comprueben los tres pares contra
la cuenta de la demostración, con $|C| = 8$ y $L = 193$ ventanas legales:

$$
V = t^2\,|C| + (t - 1)(t - 2)\,L \qquad M = t^2\Bigl(1 + \tfrac{|C|(|C| - 1)}{2}\Bigr) + t + (t - 1)(t - 2)(6L + 1) + 1
$$

Al duplicar $t$, ¿por cuánto se multiplica $M$? ¿Qué parte de la fórmula depende de la máquina y cuál de la
entrada?

## Qué se practica aquí

Escribir una reducción completa y comprobarla con una herramienta. La parte delicada son las ventanas: cada
línea de la tabla es un caso de la demostración, y cada una que falte o sobre cambia qué tableaux admite la
fórmula. Los casos incluyen la cadena vacía, el tableau más chico ($t = 4$), una máquina sin transiciones, una
que acepta sin dar ningún paso, una que no se detiene, una con ramas que no terminan, movimientos `L` en la
primera celda, una ejecución que acepta justo en la última fila y otra a la que le falta una fila, y fórmulas
de alrededor de un millón de cláusulas.

Mientras desarrollan, compilen con sanitizers, como explica [`labs/README.md`](../../../../labs/README.md).

## Para seguir

Opcional, sin casos en el juez.

- Pasen su fórmula a 3-SAT con la construcción de los apuntes: partan cada cláusula de más de tres literales
  con variables nuevas. ¿Cuántas cláusulas salen de la del grupo 4? Comprueben con `minisat` que la respuesta
  no cambia.
- El grupo 4 puede mirar solo la última fila. ¿Por qué sigue siendo correcto? ¿Qué regla de las ventanas lo
  permite?
- Quiten del grupo 1 las cláusulas de "al menos un símbolo" y corran el juez. ¿Por qué sigue pasando? ¿Qué
  otro grupo ya obliga a que cada celda tenga algo?
