# Un simulador de máquinas de Turing

Este es el programa con el que van a probar sus máquinas de Turing el resto del semestre: recibe la descripción
de una máquina determinista de una cinta, un límite de pasos y una lista de cadenas, y dice por cada cadena
qué hizo la máquina.

A diferencia de un DFA, una máquina de Turing puede no detenerse. Ningún simulador puede esperar para siempre,
así que la respuesta tiene tres valores: `acepta`, `rechaza` o `no se detuvo en N pasos`. La tercera no dice que
la máquina no se detiene nunca: dice que, después de $N$ pasos, todavía no se había detenido.

## El modelo

Es el de los apuntes de la semana 7 y el de [`code/formats.md`](../../../formats.md):

- La máquina es $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$. Empieza en $q_0$, con
  la cadena de entrada en las primeras celdas de la cinta, el resto de la cinta en blanco y el cabezal en la
  primera celda.
- En cada paso lee el símbolo bajo el cabezal y aplica $\delta(q, a) = (r, b, D)$: pasa al estado $r$, escribe
  $b$ y mueve el cabezal una celda hacia $D$, que es $\mathrm{L}$ o $\mathrm{R}$.
- **La cinta es infinita solo hacia la derecha.** Un movimiento $\mathrm{L}$ en la primera celda deja el cabezal
  donde está. La máquina igual escribe y cambia de estado, y ese paso cuenta.
- **Un par de estado y símbolo sin línea en `delta:` lleva a `reject`.** Cuenta como un paso: es como si la
  línea fuera `q a -> q_reject a R`.
- La máquina se detiene al entrar a `accept` o a `reject`. Si el estado inicial es uno de los dos, se detiene
  después de cero pasos.

## Entrada

La descripción de una máquina en el formato `.tm` de `code/formats.md`, después una línea `limit: N` y al final
el bloque de cadenas del mismo documento:

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

010
00001111
```

- Una línea que empieza con `#` es un comentario. Puede haber comentarios en cualquier línea anterior a
  `strings:`, también entre las transiciones.
- Puede haber líneas vacías antes de `delta:`. Entre `delta:` y `strings:` no hay líneas vacías.
- `states:`, `alphabet:`, `tape:`, `start:`, `accept:`, `reject:` y `delta:` vienen siempre en ese orden.
- Después de `delta:` hay una línea `estado lee -> destino escribe movimiento` por cada transición, en cualquier
  orden y **a lo sumo una** por cada par de estado y símbolo: la máquina es determinista. Puede no haber
  ninguna línea. De `accept` y de `reject` no sale ninguna transición.
- **`limit: N` va justo después de la última transición y justo antes de `strings:`.** Las transiciones
  terminan donde aparece esa línea. $N$ es la cantidad máxima de pasos que se simulan con cada cadena.
- `strings: k` dice cuántas cadenas siguen, una por línea. **Una línea vacía es la cadena vacía
  $\varepsilon$.** Después de `strings:` ya no hay comentarios.

## Salida

Una línea por cada cadena, en el mismo orden:

- `acepta` si la máquina llega a `accept` después de a lo sumo $N$ pasos;
- `rechaza` si llega a `reject` después de a lo sumo $N$ pasos;
- `no se detuvo en N pasos`, con el valor de $N$, si después de $N$ pasos no está en ninguno de los dos.

Una máquina que se detiene exactamente en el paso $N$ se detuvo: la respuesta es `acepta` o `rechaza`.

## Límites

- $2 \leq |Q| \leq 1000$ y $2 \leq |\Gamma| \leq 64$.
- El nombre de un estado tiene entre 1 y 20 caracteres visibles, sin espacios. No empieza con `#` ni termina
  con `:`. Un nombre puede ser prefijo de otro (`q1` y `q10`), y puede ser igual a un símbolo o a un
  movimiento (un estado `0`, un estado `_`, un estado `L`).
- Un símbolo es un solo carácter visible, distinto de `#`. El blanco es `_`: está en `tape:` y no en
  `alphabet:`. Todo símbolo de `alphabet:` está también en `tape:`.
- $1 \leq N \leq 50\,000\,000$ y $1 \leq k \leq 1000$. Las longitudes de las cadenas suman a lo sumo 1 000 000.
- En cada caso, los pasos que hay que simular entre todas las cadenas suman a lo sumo 50 000 000.
- Todas las cadenas están formadas solo por símbolos de `alphabet:`.
- La entrada siempre describe una máquina válida: no tienen que detectar errores en la descripción.

## Ejemplo

Para la entrada de arriba, la salida es:

```text
acepta
acepta
rechaza
no se detuvo en 40 pasos
```

Con `0011` la máquina acepta en 13 pasos, y con la cadena vacía en 1. Con `010` rechaza en 5 pasos: en el
último lee un $\mathtt{0}$ en el estado `q3`, y ese par no tiene línea. Con `00001111` aceptaría en 41 pasos, pero
el límite es 40.

## Tiempo

2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.

Con los límites de arriba hay que dar hasta 50 000 000 de pasos, sobre una cinta que puede tener cientos de
miles de celdas en uso. Cada paso tiene que costar tiempo constante, y hay dos sitios donde es fácil que no
sea así.

- **La cinta.** Guarden las celdas en un `std::vector<char>` o un `std::string` y el cabezal como un índice.
  Cuando el cabezal llega a una celda que todavía no existe, agreguen un blanco al final. Si en cambio guardan
  la configuración como dos cadenas $u$ y $v$ y pasan un símbolo de una a otra con `v.erase(0, 1)` o
  `v.insert(0, 1, c)`, cada paso corre todo $v$ una posición. Lo mismo pasa si copian la cinta en cada paso.
  Con una cinta de 200 000 celdas y 10 000 000 de pasos, el juez da `TLE`.
- **La función de transición.** Guarden cada estado por su número y $\delta$ en una tabla indexada por el
  número del estado y por el símbolo. Buscar en un `std::map` con el nombre del estado en cada paso es varias
  veces más lento, y en los casos grandes queda al borde del límite de tiempo.

La cinta no tiene un tamaño máximo conocido de antemano: en un caso, la máquina avanza 10 000 000 de celdas
hacia la derecha. No reserven un arreglo de tamaño fijo.

## Qué se practica aquí

En `code/week-07/tm.h` ya hay un `struct Tm` y funciones que leen un archivo `.tm` y lo ejecutan: son las que
usan los ejemplos de los apuntes, y pueden leerlas cuanto quieran. Ese código está escrito para que se lea
como la definición, y no para ser rápido. `solution.cpp` se escribe **sin incluir `tm.h`**: el juez compila ese
único archivo.

Los casos traen, entre otros: la cadena vacía (también como última línea de la entrada), movimientos a la
izquierda en la primera celda, transiciones que faltan, una máquina sin ninguna transición, máquinas que no se
detienen de cuatro maneras distintas, una que se detiene justo en el paso del límite, el estado inicial igual
a `accept` o a `reject`, una máquina que escribe blancos en medio de la cinta, y nombres de estados iguales a
símbolos y a movimientos.

## Cómo avanzar

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

Los tres casos grandes no están guardados: `make test` los genera con los programas `casos/gen_NN.cpp`.

1. Lean la descripción, el límite y las cadenas. Empiecen con `casos/01.in`, que es el ejemplo de arriba. Lean
   por líneas, con `std::getline`: `>>` se salta las líneas vacías, y aquí una línea vacía es una cadena.
2. Representen la máquina con los siete componentes de la definición, con los mismos nombres: `states`,
   `alphabet`, `tape`, `delta`, `start`, `accept` y `reject`. El esqueleto trae un `struct Tm` con una
   propuesta de tipos.
3. Simulen con el límite y respondan. Antes de correr el juez, respondan a mano: ¿qué hace una máquina sin
   ninguna transición con la cadena vacía, y en cuántos pasos? ¿Y una cuyo estado inicial es `accept`?
4. Guarden la cinta de modo que crezca hacia la derecha sin límite, y pasen los casos 13, 14 y 15.
5. Agreguen una opción para ver la ejecución: si el programa recibe el argumento `--trace`, antes de cada
   respuesta imprime la secuencia de configuraciones, una por línea, en el formato $u\,q\,v$ de la clase. El
   juez nunca usa esa opción. Con el ejemplo de arriba y solo la cadena `0011`:

   ```text
   $ build/solution --trace < ejemplo.in
   q0 0011
   X q1 011
   X0 q1 11
   X q2 0Y1
   q2 X0Y1
   X q0 0Y1
   XX q1 Y1
   XXY q1 1
   XX q2 YY
   X q2 XYY
   XX q0 YY
   XXY q3 Y
   XXYY q3 _
   XXYY_ q_accept _
   acepta
   ```

   $u$ es lo que está a la izquierda del cabezal, y $v$ va desde la celda del cabezal hasta el último símbolo
   que no es blanco. Si desde el cabezal todo es blanco, $v$ es un solo `_`. Si $u$ es vacía, la línea empieza
   con el estado.
6. Escriban ustedes, sin copiarla, la máquina de $\{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\}$ en el formato
   del curso, y compruébenla con su simulador. A un archivo `.tm` le faltan solo el límite y el bloque de
   cadenas:

   ```sh
   { cat mi_maquina.tm; printf 'limit: 1000\nstrings: 4\n0011\n\n010\n0101\n'; } | build/solution
   ```

   Debe imprimir `acepta`, `acepta`, `rechaza`, `rechaza`. Después prueben igual las otras máquinas de la
   clase, que están en `../../machines/`.

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

## Para seguir

Opcional, sin casos en el juez.

- Hagan que `--trace` reciba un número, `--trace 20`, y muestre solo las primeras 20 configuraciones. Sin eso,
  la ejecución de una máquina que no se detiene llena la terminal.
- Agreguen a la respuesta cuántos pasos dio la máquina, y úsenlo para llenar una tabla: los pasos de la máquina
  de $\{\, \mathtt{0}^n\mathtt{1}^n \,\}$ con $n = 10, 20, 40, 80$. ¿Qué pasa con la cantidad de pasos cuando $n$
  se duplica? Compárenlo con la cuenta de los apuntes.
- Una máquina **no determinista** se escribe en el mismo formato, con varias líneas para el mismo par de estado
  y símbolo. Escriban un segundo programa que la simule recorriendo por niveles el árbol de sus ejecuciones,
  como en los apuntes, y pruébenlo con `../../machines/nondet_branch.tm`. La semana 13 vuelve a usar ese
  formato.
