Apuntes · Capítulo 7Computabilidad
Máquinas de Turing
Máquinas de Turing
Las dos primeras partes del curso terminaron de la misma manera: con un lenguaje que el modelo no alcanza. Un autómata finito tiene una cantidad fija de memoria y no reconoce . Un autómata de pila tiene memoria sin límite, pero solo ve la cima, y no reconoce : lo demostramos la semana pasada con el lema de bombeo para lenguajes libres de contexto. Y sin embargo cualquiera de ustedes escribe en cinco minutos un programa en C++ que decide ese lenguaje. Los modelos que tenemos se quedan cortos frente a lo que una computadora hace.
Esta semana empieza la tercera parte, la de computabilidad, con el modelo que no se queda corto: la máquina de Turing. Es un autómata finito al que se le da una cinta donde puede leer y escribir, yendo y viniendo las veces que quiera. La definición es casi tan simple como la de un DFA. Lo que cambia es lo que se sostiene sobre ella: que todo lo que se puede calcular con un procedimiento mecánico, en cualquier computadora y en cualquier lenguaje de programación, lo puede calcular una de estas máquinas. Esa afirmación es la tesis de Church-Turing. Con ella, “no existe ningún algoritmo para este problema” pasa a ser un enunciado matemático que se puede demostrar, y eso es lo que haremos desde la semana 9.
La semana tiene dos mitades. En la primera se define la máquina, se aprende a seguirla escribiendo sus configuraciones, y se construyen tres, una de ellas para el lenguaje que derrotó a las gramáticas. Aparece además algo que ningún modelo anterior tenía: una máquina puede no detenerse nunca, y de ahí sale la diferencia entre reconocer un lenguaje y decidirlo. En la segunda mitad se le cambian piezas al modelo (más cintas, no determinismo, una impresora) y se demuestra cada vez que no gana poder. Esa resistencia a los cambios es el primer argumento a favor de la tesis.
Ruta de lectura.
Antes de clase (15–20 minutos): la introducción, Lo que les faltaba a los modelos anteriores y La definición formal. Antes de la sesión B, El modelo es robusto. Con eso llegan sabiendo qué es la cinta, qué es el cabezal y cómo se lee una transición.
En clase: Sesión A, de Lo que les faltaba a los modelos anteriores a Los tres niveles de descripción. Sesión B, de El modelo es robusto a Codificar objetos como cadenas.
Después de clase: el Resumen y los Ejercicios, para repasar. Antes del laboratorio, Configuraciones y Aceptar, rechazar o no detenerse otra vez, y El código de la semana. Para ampliar, las lecturas de apoyo del recuadro siguiente.
Lectura. Sipser, sec. 3.1 (Turing Machines), 3.2 (Variants of Turing Machines) y 3.3 (The Definition of Algorithm). Erickson, Models of Computation, nota 6 (Turing machines). Son apoyo: estos apuntes se pueden estudiar solos.
Código. Los programas de este capítulo están en
code/week-07. Dentro del entorno del curso, entren a esa carpeta y corranmakepara compilar los ejemplos ymake testpara comprobarlos. Los comandos de este capítulo se corren desde ahí. El laboratorio está enlab/tm_sim.
Lo que les faltaba a los modelos anteriores
Pongan lado a lado lo que cada modelo puede hacer con su memoria.
| Modelo | Memoria | Cómo la usa | Un lenguaje que no alcanza |
|---|---|---|---|
| DFA, NFA | El estado: una cantidad fija | Lee la entrada una vez, de izquierda a derecha | |
| PDA | El estado y una pila sin límite | Solo ve la cima; para ver lo de abajo tiene que borrar lo de arriba | |
| Máquina de Turing | El estado y una cinta sin límite | Lee y escribe en cualquier celda, y vuelve sobre lo escrito | Los de la semana 9 |
Al autómata finito le falta dónde anotar. Al autómata de pila le falta poder volver sobre lo anotado sin destruirlo: para comparar la cantidad de con la de tiene que vaciar la pila, y cuando llegan las ya no queda nada con qué compararlas. Las dos cosas que faltan son escribir y volver.
Una máquina de Turing tiene las dos, y nada más:
- una cinta (tape), dividida en celdas. Cada celda guarda un símbolo. La cinta empieza en una primera celda y sigue hacia la derecha sin fin;
- un cabezal (head), que está sobre una celda. Puede leer el símbolo de esa celda, cambiarlo por otro y moverse una celda a la izquierda o a la derecha;
- un control con una cantidad finita de estados, como el de un DFA.
Al empezar, la cadena de entrada está escrita en las primeras celdas, una celda por símbolo, y el cabezal está sobre la primera. Todas las demás celdas tienen un símbolo especial, el símbolo blanco (blank symbol), que se escribe y que no es parte del alfabeto de entrada. Así la máquina sabe dónde termina la entrada: en el primer blanco.
En cada paso la máquina mira dos cosas, el estado en el que está y el símbolo bajo el cabezal, y con eso hace tres: escribe un símbolo en esa celda, mueve el cabezal una celda y cambia de estado. No hay nada más. No hay variables, ni contadores, ni manera de saltar a una celda lejana: para llegar a ella hay que caminar.
Con eso ya se puede decidir , y la idea es la que usaría una persona con un lápiz: tachar el primer , ir a buscar el primer y tacharlo, volver, y repetir. Si al final todo quedó tachado, cada cero tuvo su uno.
Hay cuatro diferencias con un autómata finito, y cada una se va a notar:
- La máquina escribe en la cinta, además de leerla.
- El cabezal se mueve en los dos sentidos. La entrada se puede leer cuantas veces haga falta.
- La cinta no se acaba. Después de la entrada hay tantos blancos como la máquina quiera usar.
- Hay un estado para aceptar y otro para rechazar, y tienen efecto de inmediato: al entrar a uno de ellos la máquina se detiene, haya leído toda la entrada o no. Un DFA responde al terminar de leer; una máquina de Turing responde cuando quiere. O no responde.
Esa última posibilidad es la novedad incómoda de la semana, y tiene su propia sección.
Idea clave. Una máquina de Turing es un autómata finito con una cinta en la que puede escribir y sobre la que puede volver. La cantidad de estados sigue siendo fija. Lo que no tiene tope es la cinta.
La definición formal
Definición. Una máquina de Turing (Turing machine) es una séptupla , donde , y son conjuntos finitos y:
- es el conjunto de los estados.
- es el alfabeto de entrada. No contiene el símbolo blanco .
- es el alfabeto de la cinta. Contiene a y a todo : y .
- es la función de transición, donde .
- es el estado inicial.
- es el estado de aceptación.
- es el estado de rechazo, y .
La pieza que hay que aprender a leer es . Una transición
dice: si la máquina está en el estado y el cabezal lee , entonces escribe en esa celda, mueve el cabezal una celda a la derecha y pasa al estado . Con en lugar de , el cabezal va a la izquierda. Las tres cosas pasan en un solo paso, y siempre pasan las tres: la máquina no puede quedarse quieta, ni dejar de escribir. Para “no escribir” se escribe el mismo símbolo que se leyó, .
Vale la pena leer despacio el resto.
- Hay dos alfabetos. La entrada solo usa símbolos de . La cinta puede tener además otros símbolos, que la máquina usa para trabajar: marcas, tachaduras, separadores. El blanco está en y no en , y por eso la entrada no puede tener blancos: el primer blanco de la cinta marca el final de la entrada.
- es una función: para cada estado y cada símbolo de la cinta hay exactamente una acción. La máquina es determinista. En la segunda mitad del capítulo quitaremos esa condición.
- De y de no sale nada. Por eso se define sobre y no sobre : al entrar a uno de esos dos estados la máquina se detiene. Sipser escribe sobre todo ; lo que haya en esas dos filas no se usa nunca, así que es la misma máquina.
- Hay un solo estado de aceptación y uno solo de rechazo. En un DFA hacía falta un conjunto , porque aceptar dependía de dónde quedaba la máquina al acabarse la entrada. Aquí la máquina decide cuándo terminar, y basta un estado para cada respuesta.
- y son finitos. La tabla de tiene casillas: la máquina es un objeto finito, que se puede escribir completo en una hoja. Lo que no tiene tope es la cinta.
El borde izquierdo y las casillas vacías
La definición deja dos detalles abiertos, y este curso los fija igual que Sipser.
La cinta tiene una primera celda. Es infinita solo hacia la derecha. Si el cabezal está en la primera celda y la transición dice , el cabezal se queda donde está. La máquina escribe y cambia de estado como siempre; lo único que no ocurre es el movimiento. No es un error, y la máquina no se entera: si necesita saber dónde empieza la cinta, tiene que dejar una marca en la primera celda.
Una casilla vacía lleva a . Las tablas de este capítulo, y los archivos, casi nunca traen las transiciones. Las que faltan son las de los pares que “no deberían pasar” si la entrada está en el lenguaje. La convención es que un par sin transición escrita tiene esta:
Con eso vuelve a ser una función total, como pide la definición. Es el estado trampa de la semana 1, con la diferencia de que aquí no hace falta dibujarlo: caer en él termina la ejecución.
La máquina de 0ⁿ1ⁿ, como séptupla y como archivo
La máquina que tacha un cero y un uno por vuelta tiene cuatro estados de trabajo. Lo que cada uno hace:
| Estado | Lo que está haciendo |
|---|---|
| Está sobre el primer símbolo sin tachar de la izquierda. Si es un , lo tacha con | |
| Acaba de tachar un : camina a la derecha buscando el primer , y lo tacha con | |
| Acaba de tachar un : camina a la izquierda hasta la última | |
| Ya no quedan ceros: comprueba que a la derecha solo haya hasta el primer blanco |
Como séptupla: , , , y dada por esta tabla, donde cada casilla es (estado, símbolo que escribe, movimiento) y una casilla vacía lleva a :
La misma tabla, como diagrama de estados. Cada flecha lleva lo que la máquina lee, lo que escribe y hacia dónde mueve el cabezal:
En el formato del curso, descrito en code/formats.md, la séptupla es un archivo de texto con un campo por
componente. El blanco se escribe _. Este es machines/zeros_ones.tm:
# Decide { 0^n 1^n : n >= 0 }.
states: q0 q1 q2 q3 q_accept q_reject
alphabet: 0 1
tape: 0 1 X Y _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q1 X R
q0 Y -> q3 Y R
q0 _ -> q_accept _ R
q1 0 -> q1 0 R
q1 Y -> q1 Y R
q1 1 -> q2 Y L
q2 0 -> q2 0 L
q2 Y -> q2 Y L
q2 X -> q0 X R
q3 Y -> q3 Y R
q3 _ -> q_accept _ R
Después de delta: va una línea por cada casilla llena: estado lee -> destino escribe movimiento. El programa
show_tm lee un archivo y lo muestra como séptupla y como tabla, con un punto en las casillas vacías:
$ build/show_tm machines/zeros_ones.tm
Q = {q0, q1, q2, q3, q_accept, q_reject}
Σ = {0, 1}
Γ = {0, 1, X, Y, _}
q0 = q0, q_accept = q_accept, q_reject = q_reject
δ 0 1 X Y _
q0 q1 X R . . q3 Y R q_accept _ R
q1 q1 0 R q2 Y L . q1 Y R .
q2 q2 0 L . q0 X R q2 Y L .
q3 . . . q3 Y R q_accept _ R
transiciones escritas: 11 de 20
De las 20 casillas, 9 están vacías. Cada una es una situación en la que la entrada ya no puede estar en el lenguaje: por ejemplo, leyendo un quiere decir que queda un uno sin su cero.
En C++. El
struct Tmdetm.htiene los siete componentes con los nombres del formato:states,alphabet,tape,delta,start,acceptyreject. La función es unstd::mapcuya clave es el par (estado, símbolo) y cuyo valor es unActioncon los tres resultados:struct Action { std::string state; // r char write = BLANK; // b char move = 'R'; // D: 'L' o 'R' };Un
std::mapguarda un solo valor por clave, así que la estructura ya impide que haya dos acciones para el mismo par.read_tmrechaza un archivo que las trae, uno con una transición que sale deaccepto dereject, y uno que escribe un símbolo que no está entape. Enerrors/hay un ejemplo de cada error.
Configuraciones
Para seguir un DFA bastaba anotar el estado después de cada símbolo. Para seguir una máquina de Turing hay que anotar tres cosas, porque las tres cambian: el estado, el contenido de la cinta y la posición del cabezal. Las tres juntas son una configuración (configuration).
Definición. Una configuración de se escribe
donde es el estado, y son cadenas sobre , el contenido de la cinta es seguido de blancos, y el cabezal está sobre el primer símbolo de .
El estado se escribe justo antes de la celda que el cabezal está leyendo. Así, quiere decir: la cinta tiene y después blancos, el estado es , y el cabezal está sobre el primer , que es la segunda celda. Es el dibujo de la sección anterior, con un cero y un uno menos.
Como después de todo es blanco, y son la misma configuración. Para tener una sola
manera de escribirla, llega hasta el último símbolo que no es blanco; y si desde el cabezal todo es blanco,
es un solo . Los programas del curso la escriben así, con _ en lugar de y con espacios
alrededor del estado.
Una configuración produce la siguiente cuando la máquina da un paso. Para todos los símbolos de y todas las cadenas sobre :
Las tres líneas dicen lo mismo que la sección anterior, ahora sobre cadenas. Con un movimiento a la derecha, el símbolo escrito queda a la izquierda del estado. Con uno a la izquierda, el estado retrocede un símbolo, y , que estaba a su izquierda, pasa a ser lo que el cabezal lee. La tercera línea es el caso en que no hay ningún : el cabezal está en la primera celda y no se mueve. Si es vacía en la primera línea, a la derecha del estado queda un blanco.
Algunas configuraciones tienen nombre:
- la configuración inicial de con la entrada es : el estado inicial, la entrada en la cinta y el cabezal en la primera celda. Con es ;
- una configuración de aceptación es una cuyo estado es , y una de rechazo, una cuyo estado es . Las dos son configuraciones finales: no producen ninguna otra.
La ejecución de con es la secuencia en la que es la configuración
inicial y cada produce . Es única, porque es una función. Termina si llega a una
configuración final, y si no, sigue sin fin. El programa run_tm la imprime, con el número de paso a la
izquierda:
$ build/run_tm machines/zeros_ones.tm 0011
w = 0011
0 q0 0011
1 X q1 011
2 X0 q1 11
3 X q2 0Y1
4 q2 X0Y1
5 X q0 0Y1
6 XX q1 Y1
7 XXY q1 1
8 XX q2 YY
9 X q2 XYY
10 XX q0 YY
11 XXY q3 Y
12 XXYY q3 _
13 XXYY_ q_accept _
acepta en 13 pasos
Síganla con la tabla al lado. En la configuración 0 la máquina está en y lee : la tabla dice , y sale la configuración 1. En la 2 está en y lee : la tabla dice , y en la 3 el estado aparece un símbolo más a la izquierda, con la ya escrita. Entre la 3 y la 5 la máquina vuelve hasta la y da un paso a la derecha: terminó la primera vuelta, con un cero y un uno tachados. La segunda vuelta va de la 5 a la 10. En la 10, ya no encuentra un cero sino una , y pasa a , que recorre las y acepta al llegar al primer blanco.


En C++. Una configuración es un
struct Configcon el estado, las celdas y la posición del cabezal. Un paso es leer la casilla de y aplicarla. La cinta crece solo cuando el cabezal llega a una celda que todavía no existe, y el borde izquierdo es elifdel final:inline void apply(Config& c, const Action& action) { if (c.head >= c.cells.size()) { c.cells.resize(c.head + 1, BLANK); } c.cells[c.head] = action.write; c.state = action.state; if (action.move == 'R') { c.head++; } else if (c.head > 0) { c.head--; // en la primera celda, L no mueve el cabezal } }La cinta infinita se representa con un
std::stringfinito: las celdas que no están encellstienen un blanco. En cualquier momento la máquina ha visitado una cantidad finita de celdas, así que siempre alcanza.
Error común. Escribir el estado después del símbolo que se está leyendo. En el cabezal está sobre el primer símbolo de , a la derecha del estado. La configuración lee un y no la .
Aceptar, rechazar o no detenerse
Definición. acepta si su ejecución con llega a una configuración de aceptación. La rechaza si llega a una de rechazo. El lenguaje de es el conjunto de las cadenas que acepta:
Se dice que reconoce .
Hasta aquí es lo mismo que en las semanas anteriores. La diferencia está en lo que la definición no dice: que la ejecución llegue a alguna de las dos. Con una entrada, una máquina de Turing puede terminar de tres maneras:
- llega a y acepta;
- llega a y rechaza;
- no se detiene nunca: la ejecución es una secuencia infinita de configuraciones.
Un DFA no tenía la tercera, porque lee un símbolo por paso y la entrada se acaba. Aquí nada obliga a la máquina a avanzar hacia un final.
Las dos primeras maneras se ven en ejecuciones cortas de la máquina de la sección anterior:
$ build/run_tm machines/zeros_ones.tm '' 010
w = ε
0 q0 _
1 _ q_accept _
acepta en 1 paso
w = 010
0 q0 010
1 X q1 10
2 q2 XY0
3 X q0 Y0
4 XY q3 0
5 XY0 q_reject _
rechaza en 5 pasos
Con la cadena vacía, lee un blanco y acepta: cero ceros y cero unos. Con , en la configuración 4 la máquina está en y lee un . Esa casilla de la tabla está vacía, y la máquina pasa a .
Para la tercera manera hace falta otra máquina. Esta es machines/has_one_loops.tm: busca un
caminando hacia la derecha, y no deja de buscar cuando la entrada se acaba.
# Reconoce las cadenas binarias que tienen algún 1, y NO decide ese lenguaje:
# con una cadena sin unos sigue buscando hacia la derecha para siempre.
states: q0 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q0 0 R
q0 1 -> q_accept 1 R
q0 _ -> q0 _ R
Un simulador no puede esperar para siempre, así que run_tm da a lo sumo una cantidad de pasos, que se fija con
--limit. La opción --show 6 hace que imprima solo las primeras 6 configuraciones.
$ build/run_tm --limit 1000000 --show 6 machines/has_one_loops.tm 00 001
w = 00
0 q0 00
1 0 q0 0
2 00 q0 _
3 00_ q0 _
4 00__ q0 _
5 00___ q0 _
…
no se detuvo en 1000000 pasos
w = 001
0 q0 001
1 0 q0 01
2 00 q0 1
3 001 q_accept _
acepta en 3 pasos
Con la máquina encuentra el uno y acepta. Con pasa la entrada y sigue caminando sobre blancos.
Hay que tener cuidado con lo que dice la última línea de la primera ejecución. “No se detuvo en 1 000 000 de pasos” es un hecho sobre un millón de pasos. No dice que la máquina no se detenga nunca: podría detenerse en el paso 1 000 001. Que esta máquina no se detiene con no lo muestra el programa. Se demuestra.
Afirmación. Sea . Para todo , la configuración de la máquina después de pasos es .
Demostración. Por inducción sobre . Durante los primeros pasos la máquina está en leyendo ceros, y la transición la lleva una celda a la derecha cada vez sin cambiar nada: después de pasos la configuración es , que es la de la afirmación con . Si después de pasos la configuración es , la máquina lee un blanco en , y la transición produce , que es la de la afirmación con . ∎
Ninguna de esas configuraciones es final, así que la ejecución no termina. Las pruebas de la semana comprueban la afirmación con hasta .
En este ejemplo, además, ninguna configuración se repite: el cabezal está cada vez en una celda distinta.
“No detenerse” no quiere decir dar vueltas por las mismas configuraciones. Puede pasar eso, y entonces es fácil
de detectar. La máquina machines/left_end.tm va hasta el final de la entrada y después se mueve a la
izquierda sin parar:
$ build/run_tm --limit 8 machines/left_end.tm 01
w = 01
0 q0 01
1 0 q0 1
2 01 q0 _
3 0 q1 1
4 q1 01
5 q1 01
6 q1 01
7 q1 01
8 q1 01
no se detuvo en 8 pasos
En la configuración 4 el cabezal llegó a la primera celda. Desde ahí cada paso es un movimiento en el borde izquierdo: el cabezal no se mueve y la configuración es siempre la misma. Una configuración que se repite garantiza que la máquina no se detiene, porque de la misma configuración sale siempre la misma ejecución. Pero la máquina anterior muestra que no detenerse no exige repetir.
Idea clave. Con una entrada, una máquina de Turing acepta, rechaza o no se detiene. Mirar la ejecución no permite distinguir “no se detiene” de “todavía no se detuvo”. Esa es la diferencia con todos los modelos anteriores, y de ella sale la segunda mitad del curso.
En la práctica. El veredicto
TLEdel juez es exactamente la respuesta “no se detuvo en pasos”: el juez no sabe si su programa tiene un ciclo infinito o si solo era lento, y por eso corta a los 2 segundos. Lo mismo hacen el tiempo máximo de una consulta en una base de datos, el de una prueba en un sistema de integración continua y el aviso de “esta página no responde” del navegador. En la semana 9 veremos que no pueden hacer otra cosa.
Tres máquinas, paso a paso
Diseñar una máquina de Turing es programar con un solo puntero y sin variables. Lo que funciona casi siempre es lo mismo que en la primera máquina: marcar en la cinta lo que ya se procesó, y hacer vueltas que procesan un poco cada una. Los estados recuerdan en qué parte de la vuelta está la máquina, y a veces un símbolo que lleva de un lado a otro.
0ⁿ1ⁿ
Ya vimos la máquina y una ejecución. Falta demostrar que hace lo que decimos, y contar cuánto tarda.
Llamemos vuelta al tramo de la ejecución que empieza con la máquina en leyendo un y termina la siguiente vez que entra a . En una vuelta, la máquina tacha ese cero con , camina en hacia la derecha sobre ceros y hasta un , lo tacha con , y vuelve en hasta la que acaba de escribir.
Afirmación (lo que conserva cada vuelta). Sea la entrada. Si la máquina completa vueltas, entonces al terminar la última está en con el cabezal en la celda (contando desde 0) y:
- las celdas tienen , y en tenían ;
- exactamente de las demás celdas tienen , y en tenían ;
- todas las otras celdas están como en .
Demostración. Por inducción sobre . Para la máquina está en la configuración inicial: en , en la celda 0, con la cinta igual a . Supongamos que vale para y que la máquina completa una vuelta más. La vuelta empieza en leyendo un en la celda . Esa celda no tiene ni , así que por (3) también era un en , y la máquina escribe ahí una . Después, avanza sin cambiar nada hasta leer un ; por la misma razón era un de , y la máquina lo cambia por : ahora hay celdas con . Por último, retrocede sobre las celdas que acaba de recorrer, que solo tienen ceros y , hasta la primera que encuentra, que es la de la celda , y da un paso a la derecha: queda en en la celda . Las tres condiciones valen para . ∎
Teorema. La máquina de zeros_ones.tm decide : acepta las
cadenas de esa forma, y rechaza todas las demás.
Demostración. Son tres partes: acepta solo cadenas del lenguaje, acepta todas las del lenguaje, y se detiene siempre.
Si acepta , entonces . La máquina solo entra a leyendo un blanco, desde o desde . Digamos que antes completó vueltas, y sea la longitud de . Como la máquina nunca escribe un blanco sobre la entrada ni un símbolo sobre un blanco, las celdas con algo escrito son siempre las primeras.
- Si acepta desde : está en la celda y lee un blanco, así que y las celdas tienen todas por (1). Por (2) hay además celdas con , y no queda ninguna celda para ellas: . Entonces y .
- Si acepta desde : la máquina leyó una en la celda en el estado , y después solo leyó hasta el primer blanco. Entonces las celdas tienen todas . Por (2) son exactamente celdas, así que ; por (1) las primeras celdas de eran ceros, y por (2) las otras eran unos. Es decir, .
Si , la acepta. Si , acepta en un paso. Si , después de vueltas, con , la configuración es
y la vuelta siguiente se completa: hay un cero bajo el cabezal, pasa sobre ceros e letras y encuentra un uno, y vuelve. Se ve por inducción sobre , siguiendo la tabla. Después de vueltas la configuración es : la máquina pasa a , recorre las y acepta en el primer blanco.
Se detiene con toda entrada. Sea . Cada vuelta tacha dos celdas que no estaban tachadas, y una celda tachada no se vuelve a cambiar: hay a lo sumo vueltas. Una vuelta que empieza en la celda y tacha el uno de la celda da pasos hasta escribir la , otros para volver, y uno más sobre la : son pasos. Cuando la máquina entra a y ya no completa otra vuelta, a partir de ahí solo se mueve a la derecha, en , o , y se detiene a más tardar al leer el primer blanco, en la celda : son a lo sumo pasos. En total da a lo sumo
pasos. Como se detiene siempre y solo acepta las cadenas del lenguaje, rechaza todas las demás. ∎
La cota no es exagerada. Con se puede contar exacto: en la vuelta número , la máquina tacha el cero (1 paso), avanza sobre ceros e letras ( pasos), tacha el uno (1 paso), retrocede sobre lo mismo ( pasos) y pasa sobre la (1 paso). Son pasos por vuelta, y hay vueltas. Al final, lee una (1 paso), recorre las otras y lee el blanco. En total:
$ build/run_tm --quiet machines/zeros_ones.tm 01 0011 000111 00001111
w = 01
acepta en 5 pasos
w = 0011
acepta en 13 pasos
w = 000111
acepta en 25 pasos
w = 00001111
acepta en 41 pasos
Para la fórmula da 5, 13, 25 y 41. La entrada tiene longitud , así que la máquina tarda un tiempo cuadrático en la longitud de la entrada: va y viene una vez por cada par. Un programa en C++ hace lo mismo con una sola pasada. Esa diferencia no importa esta semana, en la que solo preguntamos qué se puede calcular, y va a importar desde la semana 12.
w#w
Lenguaje. : dos copias de la misma cadena, con un separador en medio. Sin el separador, es uno de los lenguajes que no eran libres de contexto la semana pasada. Con el separador tampoco lo es, y una máquina de Turing lo decide sin dificultad.
Una nota sobre el separador antes de seguir. En la teoría se escribe , como en Sipser. En los
archivos del curso ese carácter empieza un comentario y no puede ser un símbolo, así que en el archivo y en
lo que imprimen los programas el separador es =. La máquina es la misma.
La idea. Comparar el primer símbolo de la izquierda con el primero de la derecha, después el segundo con el segundo, y así. Como la máquina no puede recordar posiciones, tacha lo que ya comparó. Y como no puede recordar una cadena, lleva un símbolo por viaje, guardado en el estado: hay un estado para “llevo un ” y otro para “llevo un ”.
| Estado | Lo que está haciendo |
|---|---|
| Está sobre el primer símbolo sin tachar de la izquierda. Lo tacha y recuerda cuál era | |
| , | Lleva un () o un (): camina a la derecha hasta el separador |
| , | Ya pasó el separador llevando un () o un (): salta las y compara. Si coincide, lo tacha |
| Vuelve hacia la izquierda sobre las , hasta el separador | |
| Sigue volviendo sobre los símbolos sin tachar, hasta la última de la izquierda | |
| La izquierda se acabó: comprueba que a la derecha del separador solo haya |
$ build/show_tm machines/w_sep_w.tm
Q = {q0, q1, q2, q3, q4, q5, q6, q7, q_accept, q_reject}
Σ = {0, 1, =}
Γ = {0, 1, =, X, _}
q0 = q0, q_accept = q_accept, q_reject = q_reject
δ 0 1 = X _
q0 q1 X R q2 X R q7 = R . .
q1 q1 0 R q1 1 R q3 = R . .
q2 q2 0 R q2 1 R q4 = R . .
q3 q5 X L . . q3 X R .
q4 . q5 X L . q4 X R .
q5 . . q6 = L q5 X L .
q6 q6 0 L q6 1 L . q0 X R .
q7 . . . q7 X R q_accept _ R
transiciones escritas: 20 de 40
Las casillas vacías hacen buena parte del trabajo. La de con es la comparación que falla: la máquina lleva un cero y encuentra un uno. Las de con el separador y con el blanco rechazan una entrada en la que, donde tenía que estar el símbolo por comparar, hay otro separador o ya no hay nada. La de con el blanco rechaza la cadena vacía, que no tiene separador.
$ build/run_tm machines/w_sep_w.tm 01=01
w = 01=01
0 q0 01=01
1 X q1 1=01
2 X1 q1 =01
3 X1= q3 01
4 X1 q5 =X1
5 X q6 1=X1
6 q6 X1=X1
7 X q0 1=X1
8 XX q2 =X1
9 XX= q4 X1
10 XX=X q4 1
11 XX= q5 XX
12 XX q5 =XX
13 X q6 X=XX
14 XX q0 =XX
15 XX= q7 XX
16 XX=X q7 X
17 XX=XX q7 _
18 XX=XX_ q_accept _
acepta en 18 pasos
La primera vuelta va de la configuración 0 a la 7: la máquina tacha el , lo lleva en hasta el separador, lo compara en con el primer símbolo de la derecha, lo tacha, y vuelve. La segunda, de la 7 a la 14, hace lo mismo con el , en y ; en la configuración 9 se ve a saltando la de la vuelta anterior. En la 14, encuentra el separador: la izquierda está toda tachada, y comprueba que la derecha también.
Una ejecución que rechaza, y el caso más pequeño que acepta:
$ build/run_tm machines/w_sep_w.tm 01=00 =
w = 01=00
0 q0 01=00
1 X q1 1=00
2 X1 q1 =00
3 X1= q3 00
4 X1 q5 =X0
5 X q6 1=X0
6 q6 X1=X0
7 X q0 1=X0
8 XX q2 =X0
9 XX= q4 X0
10 XX=X q4 0
11 XX=X0 q_reject _
rechaza en 11 pasos
w = =
0 q0 =
1 = q7 _
2 =_ q_accept _
acepta en 2 pasos
En la configuración 10 la máquina lleva un y lee un . La entrada que es solo el separador está en el lenguaje, con .
La máquina se detiene siempre, por el mismo argumento de antes: cada vuelta tacha al menos dos celdas, primero camina solo a la derecha y después solo a la izquierda, y lo que queda al final es un tramo hacia la derecha. La cota vale igual. Con y son exactamente pasos, y la cuenta queda como ejercicio; las pruebas la comprueban hasta . La demostración de que acepta exactamente el lenguaje sigue el esquema de la anterior, con una afirmación sobre lo que conserva cada vuelta, y es el ejercicio 5.
aⁿbⁿcⁿ
Lenguaje. , el que no era libre de contexto.
La idea. La de la primera máquina, con un símbolo más: en cada vuelta se tacha una , una y una . Lo que al autómata de pila le resultaba imposible aquí no cuesta nada, porque tachar no destruye: las marcas de las siguen en la cinta cuando llega el turno de las .
| Estado | Lo que está haciendo |
|---|---|
| Está sobre el primer símbolo sin tachar de la izquierda. Si es una , la tacha con | |
| Busca la primera , pasando sobre e . La tacha con | |
| Busca la primera , pasando sobre y . La tacha con | |
| Vuelve a la izquierda hasta la última | |
| , | Ya no quedan : comprueba que lo que sigue son solo () y después solo () |
$ build/show_tm machines/anbncn.tm
Q = {q0, q1, q2, q3, q4, q5, q_accept, q_reject}
Σ = {a, b, c}
Γ = {a, b, c, X, Y, Z, _}
q0 = q0, q_accept = q_accept, q_reject = q_reject
δ a b c X Y Z _
q0 q1 X R . . . q4 Y R . q_accept _ R
q1 q1 a R q2 Y R . . q1 Y R . .
q2 . q2 b R q3 Z L . . q2 Z R .
q3 q3 a L q3 b L . q0 X R q3 Y L q3 Z L .
q4 . . . . q4 Y R q5 Z R .
q5 . . . . . q5 Z R q_accept _ R
transiciones escritas: 18 de 42
El orden de los símbolos lo vigilan las casillas vacías. solo acepta pasar sobre e antes de la , y solo sobre y antes de la : si la entrada tiene una después de una , la máquina cae en una casilla vacía, en alguna vuelta o en la comprobación final. Las cantidades las vigila el final: cuando ya no encuentra una , y exigen que no quede ninguna ni ninguna sin tachar.
$ build/run_tm machines/anbncn.tm aabbcc
w = aabbcc
0 q0 aabbcc
1 X q1 abbcc
2 Xa q1 bbcc
3 XaY q2 bcc
4 XaYb q2 cc
5 XaY q3 bZc
6 Xa q3 YbZc
7 X q3 aYbZc
8 q3 XaYbZc
9 X q0 aYbZc
10 XX q1 YbZc
11 XXY q1 bZc
12 XXYY q2 Zc
13 XXYYZ q2 c
14 XXYY q3 ZZ
15 XXY q3 YZZ
16 XX q3 YYZZ
17 X q3 XYYZZ
18 XX q0 YYZZ
19 XXY q4 YZZ
20 XXYY q4 ZZ
21 XXYYZ q5 Z
22 XXYYZZ q5 _
23 XXYYZZ_ q_accept _
acepta en 23 pasos
Dos vueltas, de la 0 a la 9 y de la 9 a la 18, y la comprobación final. Con la máquina da pasos (para , los 23 de arriba), y con cualquier entrada de longitud , a lo sumo , por el argumento de las vueltas.
Las pruebas de la semana comparan cada una de las tres máquinas con una función de C++ que decide el mismo lenguaje mirando la cadena completa: sobre las 16 383 cadenas binarias de longitud a lo sumo 13 para la primera, y sobre las 29 524 cadenas de longitud a lo sumo 9 de cada alfabeto de tres símbolos para las otras dos. En ninguna se pasa de la cota de pasos.
Idea clave. El lenguaje que separaba a las gramáticas de “lo que una computadora puede hacer” cae con la misma técnica que : marcar y volver. Lo que el autómata de pila no tenía era la posibilidad de volver sobre lo escrito sin borrarlo.
Reconocer y decidir
Las tres máquinas de la sección anterior se detienen con toda entrada. La de has_one_loops.tm no. Esa
diferencia tiene nombre.
Definición. Una máquina de Turing es un decididor (decider) si se detiene con toda entrada: con cada cadena de , acepta o rechaza. Un decididor decide el lenguaje .
Definición. Un lenguaje es reconocible (Turing-recognizable) si alguna máquina de Turing lo reconoce. Es decidible (decidable) si alguna máquina de Turing lo decide.
Dicho con las tres maneras de terminar:
| Con | Con | |
|---|---|---|
| reconoce | acepta | rechaza o no se detiene |
| decide | acepta | rechaza |
Una máquina que decide da siempre una respuesta. Una que solo lo reconoce da el sí cuando corresponde, y cuando la respuesta es no puede quedarse callada para siempre. Quien la usa y lleva una hora esperando no sabe si la respuesta es no o si todavía no llegó el sí.
Todo decididor reconoce su lenguaje, así que todo lenguaje decidible es reconocible. La pregunta interesante es la otra dirección, y es el tema de la semana 9: hay lenguajes reconocibles que no son decidibles, y hay lenguajes que ni siquiera son reconocibles. En otros libros los lenguajes decidibles se llaman recursivos y los reconocibles, recursivamente enumerables; el segundo nombre se explica más abajo, con los enumeradores.
Ahora, con cuidado. La máquina has_one_loops.tm reconoce el lenguaje
y no lo decide, porque no
se detiene con . ¿Es indecidible? No. Basta cambiarle una transición para que al llegar al
primer blanco rechace. Esa máquina es machines/has_one.tm:
$ build/run_tm --quiet machines/has_one.tm 000 0010
w = 000
rechaza en 4 pasos
w = 0010
acepta en 3 pasos
Las dos máquinas reconocen el mismo lenguaje. Una lo decide y la otra no. Y es decidible, porque para eso basta que exista un decididor.
Error común. Decir que una máquina “decide” un lenguaje cuando hay entradas con las que no se detiene. Decidir es una afirmación sobre todas las entradas: con cada una, la máquina se detiene. Si con una sola cadena no se detiene, la máquina reconoce su lenguaje y no lo decide. Y al revés: que una máquina concreta no decida no dice que sea indecidible. Decidible es una propiedad del lenguaje, y para negarla hay que demostrar que ninguna máquina lo decide.
Para afirmar que una máquina decide hay que demostrar dos cosas, y la segunda es nueva: que acepta exactamente las cadenas del lenguaje, y que se detiene con toda entrada. En la máquina de fue la tercera parte de la demostración, con la cota de pasos. Una cota de pasos en función de la longitud de la entrada es la manera más directa de demostrar que una máquina se detiene.
Dos consecuencias inmediatas de las definiciones, que usaremos después.
Todo lenguaje regular es decidible. Sea un DFA. La máquina de Turing que
lo imita tiene los estados de más y , nunca cambia la cinta y solo se
mueve a la derecha: para cada símbolo de . Al leer
el primer blanco ya leyó toda la entrada, y pasa a si y a si
no. Con una entrada de longitud se detiene en pasos, y acepta exactamente cuando acepta.
has_one.tm es una máquina de este tipo, que además se adelanta y acepta apenas ve el uno.
Los lenguajes decidibles son cerrados bajo complemento. Si decide , la máquina que resulta de intercambiar y decide el complemento de : se detiene con las mismas entradas, que son todas, y responde lo contrario. Con una máquina que solo reconoce, el mismo cambio no sirve: las entradas con las que no se detiene siguen sin respuesta, y deberían ser aceptadas. Es el mismo fenómeno que el complemento de un DFA sin estado trampa, en la semana 1: para dar vuelta las respuestas, la máquina tiene que responder siempre. En la semana 9 veremos que no es un defecto de la construcción: los lenguajes reconocibles no son cerrados bajo complemento, y que si un lenguaje y su complemento son los dos reconocibles, entonces es decidible.
Los tres niveles de descripción
Escribir la tabla de una máquina de Turing es lento, y leerla es peor. Para la máquina de hicieron falta 20 transiciones, y la idea se dice en una frase. Por eso una máquina se describe en uno de tres niveles, según para qué se la quiera, y el texto siempre dice cuál usa. Los tres, para esa misma máquina.
Nivel formal. La séptupla completa: los estados, los alfabetos y la tabla de , o el archivo .tm.
Es la salida de show_tm machines/w_sep_w.tm de la sección anterior. No deja nada a la interpretación: se
puede ejecutar a mano o darle el archivo a un simulador. Es el nivel de esta semana y el del laboratorio.
Nivel de implementación. Se dice en prosa qué hace el cabezal: por dónde se mueve, qué marca, qué recuerda en el estado. No se nombran los estados ni se escribe .
M = "Con la entrada w:
1. Si la celda bajo el cabezal tiene el separador, ir al paso 5. Si tiene un blanco, rechazar.
Si no, recordar su símbolo y tacharlo.
2. Avanzar hasta el separador. Si antes aparece un blanco, rechazar.
3. Avanzar sobre los símbolos tachados hasta el primero sin tachar. Si es igual al símbolo
recordado, tacharlo. Si no, rechazar.
4. Retroceder hasta el símbolo tachado que está más a la derecha entre los que quedan a la
izquierda del separador, avanzar una celda y volver al paso 1.
5. Avanzar sobre los símbolos tachados que siguen al separador. Si después de ellos viene
un blanco, aceptar. Si no, rechazar."
Quien lea esto puede escribir la tabla sin tener que inventar nada, y puede contar los pasos. Es el nivel adecuado para convencerse de que algo cabe en una máquina de Turing: de que se puede hacer solo con un cabezal, marcas y una cantidad fija de estados.
Nivel alto. Un algoritmo en pasos numerados, sin mencionar la cinta ni el cabezal.
M = "Con la entrada w:
1. Comprobar que w tiene exactamente un separador. Si no, rechazar.
2. Comparar la parte de w que está antes del separador con la que está después.
Si son iguales, aceptar. Si no, rechazar."
Es como se escribe un algoritmo en cualquier curso. Lo que una descripción de alto nivel tiene que cumplir es que cada paso sea claramente realizable por una máquina, con una cantidad finita de trabajo, y que quede claro cuándo acepta y cuándo rechaza. Si se afirma que la máquina decide, además tiene que verse que termina.
| Nivel | Qué se escribe | Para qué sirve |
|---|---|---|
| Formal | La séptupla: la tabla de o el archivo | Ejecutarla, programarla, demostrar algo sobre una máquina concreta |
| De implementación | Los movimientos del cabezal y las marcas, en prosa | Mostrar que una idea cabe en el modelo; contar pasos |
| Alto | Un algoritmo en pasos numerados | Todo lo demás, desde la semana 9 |
¿Con qué derecho se pasa del primer nivel al tercero? Cada vez que escribamos “comparar las dos partes” sin decir cómo, estaremos afirmando que existe una tabla que lo hace. Para los pasos de esta semana, esa tabla está a la vista. En general, lo que justifica el salto es la segunda mitad de este capítulo: el modelo aguanta cualquier comodidad que se le agregue, y todo lo que se sabe calcular con un procedimiento mecánico se puede calcular con una máquina de Turing. Después de esta semana casi no volveremos a escribir una tabla.
En la práctica. Los tres niveles son los de cualquier software. El nivel formal es el código de máquina: lo único que de verdad se ejecuta, y casi nadie lo lee. El de implementación es el código fuente, con sus punteros y sus ciclos. El alto es el pseudocódigo de un libro de algoritmos, o la descripción de una función en su documentación. Se confía en el nivel alto porque se sabe que hay un compilador que lo baja hasta el primero.
El modelo es robusto
La definición de la sesión anterior tiene decisiones que parecen arbitrarias. ¿Por qué una sola cinta? ¿Por qué infinita solo hacia la derecha? ¿Por qué el cabezal no puede quedarse quieto? Si alguna de esas decisiones cambiara lo que la máquina puede calcular, el modelo sería frágil, y sería difícil sostener que captura algo tan general como “lo calculable”.
No lo cambian. Un modelo es robusto cuando sus variantes razonables reconocen exactamente los mismos lenguajes, y la máquina de Turing lo es en un grado que ningún modelo anterior tenía.
La manera de demostrarlo es siempre la misma, y conviene tenerla clara antes de ver los casos.
Idea clave. Para mostrar que dos modelos tienen el mismo poder, se muestra que cada uno puede simular al otro: dada una máquina cualquiera de un modelo, se construye una del otro que reconoce el mismo lenguaje. Una dirección suele ser trivial, porque un modelo es un caso particular del otro. El trabajo está en la otra.
Un calentamiento. Supongan que se permite un tercer movimiento, , que deja el cabezal donde está. Toda máquina sin es también una máquina con que no lo usa: esa dirección no pide nada. Al revés, dada una máquina que usa , cada transición se cambia por dos: una que escribe , va a la derecha y pasa a un estado nuevo , y otra que desde , lea lo que lea, lo deja igual, va a la izquierda y pasa a . Después de un paso a la derecha el cabezal nunca está en la primera celda, así que el paso a la izquierda lo devuelve a donde estaba. La máquina nueva reconoce el mismo lenguaje, con el doble de pasos como mucho. Quedarse quieto es una comodidad y no agrega poder.
Las tres variantes que siguen son menos triviales, y cada una enseña una técnica que volverá: más cintas, no determinismo, y una máquina que en lugar de responder imprime.
Máquinas de varias cintas
Una máquina de Turing de cintas (multitape Turing machine) tiene cintas, cada una con su propio cabezal. Al empezar, la entrada está en la primera cinta y las demás están en blanco. En cada paso la máquina lee los símbolos que están bajo los cabezales, y con eso y el estado decide qué escribir en cada cinta y cómo mover cada cabezal:
Con varias cintas es natural permitir : a menudo un cabezal espera mientras otro trabaja.
Con dos cintas, se decide sin ir y venir. La máquina copia los ceros a la segunda cinta, y después retrocede en ella un cero por cada uno que lee en la primera.
| Estado | Lee (cinta 1, cinta 2) | Escribe | Mueve | Pasa a | Para qué |
|---|---|---|---|---|---|
| , | , | S, S | La entrada vacía | ||
| , | , $ |
S, R | Marca el inicio de la cinta 2 | ||
| , | , | R, R | Copia un cero | ||
| , | , | S, L | Primer uno: la cinta 2 vuelve al último cero | ||
| , | , | R, L | Un uno por cada cero | ||
, $ |
, $ |
S, S | Se acabaron a la vez |
Cualquier otra combinación lleva a . La marca $ en la primera celda de la segunda
cinta es la manera de saber dónde empieza, como dijimos al hablar del borde izquierdo. El formato .tm del
curso describe máquinas de una cinta, así que esta máquina está escrita en C++, en la función
two_tape_zeros_ones de multitape.h. En la salida, el símbolo bajo cada cabezal va entre corchetes:
$ build/multitape_demo run 0011
w = 0011
0 q0 cinta 1: [0]011 cinta 2: [_]
1 q1 cinta 1: [0]011 cinta 2: $[_]
2 q1 cinta 1: 0[0]11 cinta 2: $0[_]
3 q1 cinta 1: 00[1]1 cinta 2: $00[_]
4 q2 cinta 1: 00[1]1 cinta 2: $0[0]
5 q2 cinta 1: 001[1] cinta 2: $[0]0
6 q2 cinta 1: 0011[_] cinta 2: [$]00
7 q_accept cinta 1: 0011[_] cinta 2: [$]00
acepta en 7 pasos
Con y son pasos: uno para la marca, para copiar, uno para dar la vuelta, para comparar y uno para aceptar. La máquina de una cinta necesitaba . Dos cintas son, claramente, más cómodas y más rápidas. Lo que afirma el teorema siguiente es que no son más poderosas.
Teorema. Para toda máquina de Turing de varias cintas hay una máquina de Turing de una cinta que reconoce el mismo lenguaje.
Demostración. Por construcción. Sea una máquina de cintas. Construimos una máquina de una cinta que simula a paso a paso, y después mostramos que reconoce el mismo lenguaje.
Qué se construye: la cinta de . guarda en su única cinta el contenido de las cintas de , una después de otra, con un separador antes de la primera, entre cada dos y después de la última. De cada cinta de guarda solo un tramo inicial: las celdas que ya usó. Para saber dónde está cada cabezal de , el símbolo que está bajo él lleva una marca. Formalmente, el alfabeto de la cinta de tiene, por cada símbolo de , dos símbolos: y con marca. Aquí la marca se escribe con corchetes. Si las cintas de son las de la configuración 2 del ejemplo, la cinta de es
#0[0]11#$0[_]#
Cada tramo tiene exactamente una marca.
Qué se construye: cómo trabaja .
S = "Con la entrada w = w1 w2 … wn:
1. Preparar la cinta: correr w una celda a la derecha y dejar #[w1]w2…wn#[_]#[_]#…#,
con k tramos. Volver a la primera celda.
2. Para simular un paso de M:
a. Recorrer la cinta de la primera celda al último separador, anotando el símbolo
marcado de cada tramo. Volver a la primera celda.
b. Con el estado de M y los k símbolos anotados, buscar en δ lo que M hace: los k
símbolos que escribe, los k movimientos y el estado nuevo. Si δ no tiene esa
transición, rechazar.
c. Recorrer la cinta otra vez. En cada tramo, cambiar el símbolo marcado por el que
M escribe ahí y mover la marca una celda según el movimiento de ese cabezal.
Si la marca tendría que pasar a la izquierda del separador que abre el tramo, se
queda donde está: el cabezal de M estaba en su primera celda.
Si la marca tendría que caer sobre el separador que cierra el tramo, el cabezal
de M llega a una celda que el tramo todavía no tiene: escribir ahí un blanco con
marca y correr todo lo que sigue, hasta el último separador, una celda a la
derecha.
d. Volver a la primera celda. Si el estado nuevo de M es q_accept, aceptar. Si es
q_reject, rechazar. Si no, repetir desde 2."
Esta es una descripción de implementación, y lo que hay que revisar es que cabe en una máquina de una cinta con una cantidad fija de estados. Lo que recuerda fuera de la cinta es: el estado de , los símbolos anotados, lo que dice que hay que hacer con cada tramo, el símbolo que lleva en la mano mientras corre la cinta, y cuántos separadores ha pasado. Cada uno de esos datos tiene una cantidad finita de valores posibles, que depende de y no de la entrada. Todas las combinaciones son una cantidad finita, y cada una es un estado de . Contar separadores le sirve a para saber en qué tramo está y para reconocer el primero y el último, que son el número 1 y el número .
Por qué reconoce el mismo lenguaje. Se demuestra por inducción sobre que, después de simular pasos, la cinta de representa la configuración de después de pasos: el tramo tiene el contenido de la cinta de , salvo blancos al final, la marca del tramo está en la posición del cabezal , y recuerda el estado de . Para es lo que deja el paso 1. Si vale para , en el paso 2a anota exactamente los símbolos que lee, en 2b obtiene la misma acción que , y en 2c aplica a cada tramo el cambio que aplica a cada cinta, incluidos los dos casos del borde: vale para . Entonces llega a aceptar si y solo si llega a , y lo mismo con rechazar. Si no se detiene, tampoco. Luego , y es un decididor exactamente cuando lo es. ∎
El programa multitape_demo sim ejecuta esa simulación. La cinta de se toca solo como la tocaría un
cabezal, con una operación que lee la celda actual, escribe en ella y se mueve una celda, y cada operación se
cuenta como un paso de :
$ build/multitape_demo sim 01
w = 01
pasos de M estado de M cinta de S pasos de S
0 q0 #[0]1#[_]# 12
1 q1 #[0]1#$[_]# 36
2 q1 #0[1]#$0[_]# 64
3 q2 #0[1]#$[0]_# 94
4 q2 #01[_]#[$]0_# 136
5 q_accept #01[_]#[$]0_# 168
acepta: 5 pasos de M, 168 pasos de S (12 para preparar la cinta)
En la primera fila la cinta está recién preparada. De la fila 0 a la 1, el segundo cabezal de escribe
$ y va a la derecha, a una celda que su tramo no tenía: el tramo crece y el último separador se
corre. De la 3 a la 4 crece el primer tramo, y se corre todo el segundo. Simular 5 pasos de costó 168 pasos
de .


Hay que ser precisos sobre qué es este programa. No construye la tabla de de : es la descripción de implementación de arriba escrita en C++, con la disciplina de tocar la cinta solo a través del cabezal. Las pruebas comprueban la afirmación de la inducción después de cada paso, comparando la cinta de con la configuración de , para la máquina de dos cintas con las 4095 cadenas binarias de longitud a lo sumo 11 y para 180 máquinas de una, dos y tres cintas con transiciones al azar.
Cuánto cuesta la simulación
Esta semana solo importa que la simulación existe. En la semana 12 va a importar cuánto cuesta, así que dejamos hecha la cuenta.
Teorema. Sea una máquina de cintas que con la entrada , de longitud , se detiene en pasos. Entonces la máquina de la construcción se detiene con en a lo sumo
pasos. En particular, si , son pasos, con una constante que depende solo de .
Demostración. Se cuenta por partes. Llamemos a la cantidad de celdas que tiene en uso, de la primera al último separador.
El largo de la cinta. Recién preparada, la cinta tiene celdas en uso si : un separador, los símbolos de la entrada, otro separador, y un blanco con marca y un separador por cada una de las otras cintas. Si tiene . En los dos casos, a lo sumo . Al simular un paso de , cada tramo crece a lo sumo una celda, porque cada cabezal de avanza a lo sumo una. Entonces, después de simular pasos,
Preparar la cinta. escribe las celdas de izquierda a derecha, una por paso, y vuelve a la primera: a lo sumo pasos.
Simular un paso de . Sea el largo de la cinta al terminar de simularlo.
| Parte | Pasos de , a lo sumo |
|---|---|
| 2a: ir hasta el último separador y volver | |
| 2c: avanzar de la primera celda al último separador | |
| 2c: en cada tramo, mover la marca una celda a la izquierda y regresar | por tramo: |
| 2c: en cada tramo que crece, correr el resto de la cinta y regresar | por tramo: |
| 2d: volver a la primera celda |
La suma es , y como , es a lo sumo .
El total. Durante toda la simulación , y se simulan pasos. Sumando la preparación sale la cota del enunciado. Si , el factor es a lo sumo , y la cota es un polinomio de grado 2 en cuyos coeficientes dependen solo de . ∎
La razón del cuadrado está en la tabla: simular un paso de obliga a a recorrer toda su cinta, y esa cinta puede medir tanto como pasos lleva . Son pasos, cada uno de costo proporcional a .
multitape_demo table mide las tres maneras de decidir que tenemos, con la
entrada :
$ build/multitape_demo table
Entrada 0^n 1^n, de longitud 2n. Pasos hasta aceptar:
n una cinta (zeros_ones.tm) dos cintas dos cintas simuladas en una
5 61 13 992
10 221 23 3012
20 841 43 10352
40 3281 83 38232
80 12961 163 146792
160 51521 323 575112
320 205441 643 2276552
La columna de dos cintas es : al duplicar , se duplica. La última columna se multiplica por un número cada vez más cercano a 4 cuando se duplica ( y ), que es lo que hace una función cuadrática. La primera columna también es cuadrática, con una constante unas once veces menor: una máquina pensada para una cinta le gana a la simulación genérica, pero las dos están en el mismo orden. Son cantidades de pasos, exactas, y no tiempos: no dependen de la computadora donde se corra el programa.
Idea clave. Varias cintas no agregan poder: una cinta las simula guardándolas una después de otra, con una marca en el lugar de cada cabezal. Sí agregan velocidad, pero poca: lo que una máquina de varias cintas hace en pasos, una de una cinta lo hace en .
En C++. En
multitape.h, la cinta de es unstruct OneTapecon una sola operación que la modifica,write_move(c, direction), que escribe en la celda del cabezal, lo mueve una celda y suma uno asteps. El resto de la simulación está escrito encima de esa operación, sin índices: para llegar a una celda hay que caminar hasta ella. Así el contador de pasos es el de una máquina de Turing de verdad.
Máquinas no deterministas
La segunda variante cambia la función de transición. En una máquina de Turing no determinista (nondeterministic Turing machine), no es una acción sino un conjunto de acciones posibles:
Es el mismo cambio que llevó del DFA al NFA en la semana 2. Desde una configuración puede haber varias configuraciones siguientes, una por cada acción. Las ejecuciones posibles con una entrada ya no forman una secuencia sino un árbol: la raíz es la configuración inicial, y los hijos de cada configuración son las que produce en un paso. Cada camino que baja desde la raíz es una rama: una ejecución posible.
Definición. Una máquina no determinista acepta si alguna rama del árbol llega a una configuración de aceptación. No importa cuántas ramas rechacen, ni cuántas no se detengan.
En el formato del curso, una máquina no determinista se escribe igual que una determinista, con varias líneas
para el mismo par. Esta es machines/nondet_branch.tm, hecha para que una de sus opciones sea una trampa:
# No determinista: con un 0 en q0 hay dos opciones. La primera se va por una rama que no se
# detiene nunca; la segunda sigue buscando un 1. Acepta las cadenas que tienen algún 1.
states: q0 q1 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q1 0 R
q0 0 -> q0 0 R
q0 1 -> q_accept 1 R
q1 0 -> q1 0 R
q1 1 -> q1 1 R
q1 _ -> q1 _ R
En , con un , la máquina puede pasar a o seguir en . El estado avanza hacia
la derecha para siempre, lea lo que lea. El programa ntm_demo imprime el árbol nivel por nivel: en el nivel
están las configuraciones a las que se llega con pasos.
$ build/ntm_demo machines/nondet_branch.tm 001
w = 001
nivel 0: q0 001
nivel 1: 0 q1 01 0 q0 01
nivel 2: 00 q1 1 00 q1 1 00 q0 1
nivel 3: 001 q1 _ 001 q1 _ 001 q_accept _
por niveles: acepta en el nivel 3, después de revisar 9 configuraciones
siempre la primera opción: no se detuvo en 1000000 pasos
En el nivel 2 la configuración aparece dos veces: se llega a ella por dos ramas distintas, y el árbol las cuenta por separado. En el nivel 3 una rama acepta, y con eso la máquina acepta , aunque las otras dos ramas sigan sin fin.
Un NFA no ganaba poder con el no determinismo: la construcción de subconjuntos lo volvía determinista. Un autómata de pila sí ganaba, como vimos la semana pasada con los palíndromos. Con las máquinas de Turing se vuelve al primer caso.
Teorema. Para toda máquina de Turing no determinista hay una máquina de Turing determinista que reconoce el mismo lenguaje.
La idea, y el intento que falla. La máquina determinista tiene que buscar en el árbol de una configuración de aceptación. Hay dos maneras conocidas de recorrer un árbol. La primera que se le ocurre a cualquiera que haya programado un backtracking es el recorrido en profundidad: seguir una rama hasta el final, y si no acepta, volver atrás y probar la siguiente. Con un árbol finito funciona. Aquí no, porque una rama puede no tener final. En el ejemplo, la primera opción en lleva a , y esa rama no termina nunca: el recorrido en profundidad entra en ella y no vuelve, aunque la aceptación estaba a tres pasos de la raíz por otra rama. Es la última línea de la salida de arriba. Cambiar el orden de las opciones no lo arregla: para cualquier orden fijo hay una máquina cuya rama infinita está primero.
El recorrido que sirve es por niveles (breadth-first): primero todas las configuraciones a un paso de la raíz, después todas las que están a dos, y así. Una rama infinita ya no estorba, porque el recorrido avanza un paso en todas las ramas antes de dar el segundo en ninguna.
Demostración. Por construcción.
Qué se construye. guarda una cola de configuraciones de .
D = "Con la entrada w:
1. Poner en la cola la configuración inicial de N con w.
2. Mientras la cola no esté vacía:
a. Sacar la configuración C que está al frente de la cola.
b. Si C es de aceptación, aceptar.
c. Por cada acción de δ que N puede aplicar en C, agregar al final de la cola la
configuración que resulta. (Si C es de rechazo, no se agrega nada.)
3. Rechazar."
es una máquina de Turing: se puede armar con varias cintas, que ya sabemos reducir a una. Una configuración de es una cadena finita, . La cola es una cinta con las configuraciones escritas una después de otra y separadas por , y una marca en la que está al frente. Sacar del frente es avanzar la marca. Agregar al final es copiar al final de la cinta, cambiando solo lo que cambia en un paso: el estado, un símbolo y la posición del estado. Las acciones posibles en son una cantidad finita, y están en la tabla de , que lleva en sus estados.
Por qué reconoce el mismo lenguaje: si acepta , acepta . Toda configuración que entra a la cola es la inicial o se produjo en un paso de a partir de una que estaba en la cola. Por inducción, toda configuración de la cola está en el árbol de con . Si acepta, sacó de la cola una configuración de aceptación, que es entonces el final de una rama de .
Si acepta , acepta . Sea la mayor cantidad de acciones que tiene una casilla de la tabla de . Es un número finito, y cada configuración tiene a lo sumo hijos, así que el nivel del árbol tiene a lo sumo configuraciones. La cola respeta los niveles: las configuraciones salen en el orden en que entraron, y los hijos de una configuración del nivel entran después de todas las del nivel . Por inducción, saca todas las del nivel antes que cualquiera del nivel . Si acepta , hay una configuración de aceptación en algún nivel . Antes de llegar a ella, procesa a lo sumo
configuraciones, que es una cantidad finita, y procesar cada una toma una cantidad finita de pasos. Entonces llega a esa configuración, o a otra de aceptación que estaba antes en la cola, y acepta. ∎
Hay un detalle en el paso 3 que vale la pena. Si todas las ramas de se detienen, el árbol es finito: un árbol en el que cada nodo tiene una cantidad finita de hijos y ninguna rama es infinita tiene una cantidad finita de nodos (es el lema de König). En ese caso la cola se vacía y rechaza. Así que si se detiene en todas sus ramas con toda entrada, es un decididor. Como una máquina determinista es un caso particular de una no determinista, un lenguaje es decidible si y solo si lo reconoce alguna máquina no determinista que se detiene en todas sus ramas.
Si alguna rama no se detiene y ninguna acepta, tampoco se detiene, y está bien: no aceptaba esa entrada, y solo tiene que reconocer el mismo lenguaje.
$ build/ntm_demo machines/nondet_branch.tm 00 5
w = 00
nivel 0: q0 00
nivel 1: 0 q1 0 0 q0 0
nivel 2: 00 q1 _ 00 q1 _ 00 q0 _
nivel 3: 00_ q1 _ 00_ q1 _ 00_ q_reject _
nivel 4: 00__ q1 _ 00__ q1 _
nivel 5: 00___ q1 _ 00___ q1 _
por niveles: ninguna rama aceptó hasta el nivel 5
siempre la primera opción: no se detuvo en 1000000 pasos
Una rama rechaza en el nivel 3 y desaparece. Las otras dos siguen para siempre, y el recorrido con ellas.
En C++.
breadth_firstenntm.hes la máquina . Guarda la cola nivel por nivel, en dosstd::vector<Config>, que es el mismo orden: todas las configuraciones de un nivel antes que las del siguiente. Los hijos de una configuración los calculasuccessors, que aplica cada acción posible a una copia.
El costo. La simulación es correcta y es carísima. Si la rama que acepta tiene pasos, puede tener que procesar del orden de configuraciones antes de llegar a ella: un tiempo exponencial en . No se conoce ninguna simulación determinista que evite ese salto. Varias cintas costaban un cuadrado; el no determinismo, hasta donde se sabe, cuesta una exponencial. Esta semana no importa, porque solo preguntamos qué se puede calcular. En la semana 12, esa diferencia entre un cuadrado y una exponencial es la pregunta de si P es igual a NP.
Error común. Pensar que una máquina no determinista “prueba todas las ramas” y que eso es un algoritmo. La máquina no determinista no recorre nada: la definición solo dice que acepta si existe una rama que acepta. Quien recorre el árbol es la máquina determinista que la simula, y paga por cada configuración.
Enumeradores
La tercera variante cambia lo que la máquina hace con un lenguaje. Las máquinas de hasta ahora reciben una cadena y responden. Un enumerador (enumerator) no recibe nada: es una máquina de Turing con una impresora, que empieza con la cinta en blanco y, mientras trabaja, va imprimiendo cadenas. El lenguaje que enumera es el conjunto de todas las cadenas que imprime en algún momento.
No se le pide ningún orden, puede imprimir la misma cadena muchas veces, y puede no detenerse nunca. De hecho, si el lenguaje es infinito, no se detiene. Formalmente la impresora es una segunda cinta, de solo escritura, y “imprimir” es pasar por un estado especial que da por terminada la cadena escrita ahí. No necesitaremos más detalle que ese.
Reconocer y enumerar parecen tareas distintas: una responde preguntas sobre cadenas sueltas, la otra produce la lista. Son la misma.
Teorema. Un lenguaje es reconocible si y solo si algún enumerador lo enumera.
Demostración. Por construcción, en las dos direcciones.
De un enumerador a una máquina que reconoce. Sea un enumerador de . La máquina es:
M = "Con la entrada w:
1. Ejecutar E. Cada vez que E imprime una cadena, compararla con w.
2. Si alguna vez son iguales, aceptar. Si E se detiene sin haber impreso w, rechazar."
acepta exactamente cuando imprime en algún momento, es decir, cuando . Con una cadena que no está en , espera para siempre si no se detiene. No importa: solo tiene que reconocer.
De una máquina que reconoce a un enumerador: el intento que falla. Sea una máquina que reconoce . Lo
natural sería tomar las cadenas de en el orden de siempre, (primero las más
cortas, como en la semana 1), y hacer: ejecutar con , y si acepta, imprimirla; después con ; y
así. Falla en cuanto no se detiene con alguna cadena: el enumerador se queda ahí para siempre y nunca
llega a las que siguen. Con has_one_loops.tm falla en el primer intento, porque no tiene
unos.
El arreglo es el mismo que con el no determinismo: no terminar una cosa antes de empezar la siguiente.
E = "Sin mirar la entrada:
1. Para i = 1, 2, 3, …:
2. Ejecutar M durante i pasos con cada una de las cadenas s1, s2, …, si.
3. Imprimir cada cadena que M haya aceptado en esos i pasos."
Por qué funciona. Cada ronda termina: son ejecuciones de a lo sumo pasos. Así que llega a todas las rondas.
- solo imprime cadenas de : imprime únicamente si la aceptó.
- imprime todas las cadenas de : si , entonces para algún , y la acepta en alguna cantidad de pasos . En la ronda , la cadena está entre las primeras y tiene pasos suficientes: la imprime. La imprime también en todas las rondas siguientes, y un enumerador puede repetir. ∎
El programa enumerate hace eso con una máquina del curso. Con la que no se detiene:
$ build/enumerate machines/has_one_loops.tm 8
ronda 1:
ronda 2:
ronda 3: 1
ronda 4: 1
ronda 5: 1 01
ronda 6: 1 01 10
ronda 7: 1 01 10 11
ronda 8: 1 01 10 11
cadenas distintas impresas en 8 rondas (4): 1 01 10 11
Las cadenas en orden son , , , , , , , … La cadena es y la máquina la acepta en un paso: sale por primera vez en la ronda . La cadena es y se acepta en dos pasos: sale en la ronda 5. Con , y la máquina no se detiene, y el enumerador las vuelve a intentar en cada ronda con un paso más, sin quedarse atascado en ninguna.
Esta técnica, repartir el trabajo entre infinitas tareas dándole a cada una un poco más cada vez, se llama en inglés dovetailing. La volveremos a usar.
El teorema explica el otro nombre de los lenguajes reconocibles: recursivamente enumerables. Son los lenguajes cuyos elementos se pueden listar con un procedimiento mecánico.
En la práctica. Un sistema operativo hace lo mismo que el enumerador con los procesos que corre: no espera a que uno termine para atender al siguiente, porque alguno puede no terminar nunca. Le da a cada uno un rato de procesador y pasa al que sigue. Es la misma solución al mismo problema: no se puede saber de antemano cuál de las tareas va a terminar.
Otros modelos equivalentes
Las tres variantes de este capítulo son máquinas de Turing con algo cambiado. Más convincente es lo que pasó con modelos que no se parecen en nada a una máquina de Turing y que se propusieron por separado, en los mismos años, para responder la misma pregunta: qué quiere decir “calculable”.
- El cálculo , de Alonzo Church (década de 1930). No tiene máquina ni memoria: solo funciones que se aplican a funciones, y una regla para reemplazar un parámetro por su argumento. Es el antepasado de los lenguajes funcionales.
- Las funciones recursivas, de Gödel, Herbrand y Kleene. Son funciones sobre los números naturales que se arman a partir de unas pocas funciones básicas, con composición, recursión y búsqueda del menor número que cumple una condición.
- Las máquinas de Turing (1936), pensadas por Alan Turing a partir de lo que hace una persona que calcula con lápiz y papel.
- La máquina con memoria de acceso directo (RAM), el modelo de los cursos de algoritmos: registros que guardan números, y un programa con instrucciones para sumar, leer y escribir en la celda cuyo número está en un registro, y saltar. Es una idealización de una computadora real.
- Cualquier lenguaje de programación de uso general: C++, Python, o el ensamblador de un procesador, con memoria sin límite.
Para cada par de modelos de la lista se demostró que uno simula al otro. Todos calculan exactamente lo mismo que una máquina de Turing. Esos resultados sí son teoremas, cada uno con su construcción.
Una de esas simulaciones la tienen a la vista. tm.h es un programa en C++ que ejecuta cualquier máquina de
Turing: C++ puede hacer todo lo que hace una máquina de Turing. En la otra dirección, la cadena es más larga
pero cada eslabón es conocido: un programa en C++ se compila a instrucciones de máquina; esas instrucciones
operan sobre registros y sobre celdas de memoria numeradas; y una máquina de Turing de varias cintas simula
eso guardando la memoria en una cinta, como una lista de pares de dirección y contenido, y cada registro en
otra. Leer una celda de memoria le cuesta a la máquina recorrer la lista, en lugar de un solo paso. Es más
lento. No es menos.
Error común. Creer que una computadora real calcula más que una máquina de Turing porque es más rápida. La velocidad no es poder de cómputo. La pregunta de esta parte del curso es qué problemas tienen solución, y una máquina más rápida resuelve los mismos problemas en menos tiempo: ni uno más. Si se compara con cuidado, la que pierde es la computadora real, porque su memoria es finita: en rigor es un autómata finito con una cantidad enorme de estados. La máquina de Turing es el modelo de una computadora a la que nunca se le acaba la memoria.
La tesis de Church-Turing
Todo lo anterior apunta en una dirección, y la afirmación a la que apunta tiene nombre.
Tesis de Church-Turing. Lo que se puede calcular con un procedimiento mecánico es exactamente lo que se puede calcular con una máquina de Turing.
Un “procedimiento mecánico” es lo que siempre se entendió por algoritmo: una receta finita, de instrucciones precisas, que una persona puede seguir con lápiz y papel sin necesidad de ingenio ni de suerte, y que no usa más que una cantidad finita de trabajo en cada paso.
Una de las dos direcciones no tiene nada de discutible: lo que una máquina de Turing calcula, lo calcula un procedimiento mecánico, porque seguir una tabla de transiciones es uno. Lo que la tesis afirma es la otra: que no hay ningún procedimiento mecánico que quede fuera.
Por qué no es un teorema
Un teorema relaciona objetos matemáticos, y se demuestra a partir de sus definiciones. La tesis relaciona un objeto matemático, la máquina de Turing, con una noción que no tiene definición matemática: la idea intuitiva de procedimiento mecánico, que existía siglos antes que las máquinas. No se puede demostrar que una definición captura una intuición. Lo que se puede hacer es dar razones para creerlo, y estar atentos a un contraejemplo.
La tesis es entonces una afirmación sobre el mundo: dice algo sobre lo que las personas y los aparatos pueden llegar a calcular. Se parece más a una ley de la física que a un teorema. Y como una ley de la física, se podría refutar: bastaría mostrar un procedimiento que todos reconozcan como mecánico y que ninguna máquina de Turing pueda seguir. Lo que la sostiene es evidencia.
La evidencia
Son cuatro tipos de evidencia, y conviene distinguirlos.
- Todos los modelos coinciden. El cálculo , las funciones recursivas, las máquinas de Turing, las máquinas RAM y todos los lenguajes de programación se propusieron con ideas muy distintas, y se demostró que calculan lo mismo. Si “calculable” fuera una noción vaga, cada formalización habría trazado la frontera en un lugar diferente.
- El modelo es robusto. Darle a la máquina más cintas, una cinta infinita hacia los dos lados, no determinismo o un movimiento más no cambia lo que puede calcular. Es lo que se demostró en este capítulo. La definición no depende de sus detalles.
- El análisis de Turing. Turing no propuso su máquina al azar. Partió de una persona que calcula sobre papel y argumentó que solo puede distinguir una cantidad finita de símbolos de un vistazo, que solo puede estar en una cantidad finita de “estados mentales” distintos, y que en cada momento mira una parte acotada del papel y cambia una parte acotada. Una máquina con esas tres limitaciones es una máquina de Turing. Es un argumento de que la definición no deja nada fuera, y es el que convenció a sus contemporáneos.
- No hay contraejemplo. En casi noventa años, cada algoritmo que alguien ha inventado, en cualquier área, se ha podido programar. Y cada modelo nuevo de cómputo que se ha propuesto, incluidas las computadoras cuánticas, calcula las mismas funciones: una máquina de Turing puede simular una computadora cuántica. Lo que una computadora cuántica podría cambiar es cuánto se tarda, que es otra pregunta.
Ninguno de los cuatro es una demostración. Juntos son la razón por la que la tesis se acepta sin reservas en la práctica.
Error común. Citar la tesis de Church-Turing como si fuera un teorema: “por el teorema de Church-Turing, este algoritmo se puede hacer con una máquina de Turing”. Que una máquina de varias cintas tiene una equivalente de una cinta es un teorema, y tiene demostración. Que todo algoritmo se puede escribir como máquina de Turing es la tesis, y lo que tiene es evidencia.
Qué permite
La tesis le da al curso dos cosas.
Una definición. Desde ahora, algoritmo quiere decir máquina de Turing, y más precisamente, máquina de Turing que se detiene con toda entrada. Parece poca cosa, y es lo que hace posible la semana 9. Para mostrar que un problema tiene algoritmo nunca hizo falta una definición: basta escribir uno, y todos lo reconocen. Para demostrar que un problema no tiene ningún algoritmo hay que razonar sobre todos los algoritmos posibles a la vez, y eso solo se puede hacer si “algoritmo” es un objeto matemático. Con la tesis, “ningún algoritmo decide ” se convierte en “ninguna máquina de Turing decide ”, que es un enunciado que se puede demostrar.
Hay un caso famoso. En 1900, David Hilbert pidió “un proceso” que, dado un polinomio con coeficientes enteros y varias variables, determinara “en una cantidad finita de operaciones” si tiene una raíz entera. Hilbert daba por hecho que ese proceso existía y que faltaba encontrarlo. En 1970, Yuri Matiyasevich, completando el trabajo de Martin Davis, Hilary Putnam y Julia Robinson, demostró que no existe. Esa demostración no se podía ni empezar en 1900: hacía falta saber qué era exactamente un “proceso” para poder mostrar que ninguno servía.
Un permiso. Si todo procedimiento mecánico tiene su máquina de Turing, no hace falta escribir la tabla cada vez. Desde la semana 9 las máquinas se describen en el nivel alto, como algoritmos en pasos numerados, y cuando haga falta se usa cualquier comodidad: varias cintas, variables, estructuras de datos. Cada vez que lo hagamos estaremos afirmando que existe una tabla que hace eso, y la tesis, con los teoremas de este capítulo detrás, es lo que respalda esa afirmación.
Con el problema de Hilbert se ve cómo se usa el nivel alto, y vuelve la diferencia entre reconocer y decidir. Tomemos el caso de una sola variable:
Una máquina que reconoce prueba todos los enteros, uno por uno:
M1 = "Con la entrada ⟨p⟩, donde p es un polinomio en x con coeficientes enteros:
1. Evaluar p en x = 0, 1, −1, 2, −2, 3, −3, …, en ese orden.
2. Si alguna vez el resultado es 0, aceptar."
Si tiene una raíz entera, la encuentra y acepta. Si no la tiene, no se detiene nunca. Reconoce y no decide. Para decidir hace falta saber cuándo dejar de buscar, y aquí un poco de álgebra lo da. Sea . Si es una raíz entera distinta de 0, entonces , y por lo tanto divide a . Si además , se sigue que .
M2 = "Con la entrada ⟨p⟩, donde p es un polinomio en x con coeficientes enteros:
1. Si el término independiente a0 es 0, aceptar: x = 0 es una raíz.
2. Evaluar p en cada entero x con 1 ≤ |x| ≤ |a0|.
3. Si algún resultado es 0, aceptar. Si no, rechazar."
prueba una cantidad finita de valores y se detiene siempre: es decidible. Con varias variables, la máquina que prueba todas las combinaciones de enteros sigue reconociendo el lenguaje, pero lo que Matiyasevich demostró es que ese lenguaje no es decidible: ningún cálculo da una cota que juegue el papel de y diga cuándo dejar de buscar. No lo demostraremos, pero en la semana 9 veremos el primer lenguaje reconocible y no decidible, con su demostración completa.
Codificar objetos como cadenas
Las dos máquinas anteriores reciben “un polinomio”. Pero una máquina de Turing recibe una cadena. Lo que permite hablar de máquinas que trabajan con polinomios, grafos, autómatas o gramáticas es que cualquier objeto finito se puede escribir como una cadena.
Notación. Si es un objeto, es una codificación (encoding) de como cadena. Si son varios, es una sola cadena que los codifica a todos.
Ya lo hicieron muchas veces. Un grafo no dirigido con nodos 1, 2, 3, 4 y aristas entre 1 y 2, entre 2 y 3, entre 3 y 1, y entre 1 y 4 se puede escribir como la lista de sus nodos seguida de la lista de sus aristas:
(1,2,3,4)((1,2),(2,3),(3,1),(1,4))
Eso es una cadena sobre el alfabeto de los dígitos, los paréntesis y la coma, y es un posible. La matriz de adyacencia escrita fila por fila sería otro. Con las codificaciones, un problema sobre grafos es un lenguaje, como vimos en la semana 1:
Y una máquina que lo decide se describe en el nivel alto, hablando del grafo y no de la cadena:
M = "Con la entrada ⟨G⟩, la codificación de un grafo no dirigido G con al menos un nodo:
1. Marcar el primer nodo de G.
2. Repetir hasta que no se marque ningún nodo nuevo:
3. Por cada nodo de G, marcarlo si tiene una arista hacia un nodo ya marcado.
4. Si todos los nodos de G quedaron marcados, aceptar. Si no, rechazar."
Es un decididor: cada repetición del paso 2 marca al menos un nodo nuevo o es la última, así que hay a lo sumo tantas repeticiones como nodos, más una.
Tres acuerdos sobre las codificaciones, que valen desde ahora.
- La primera línea dice qué se espera. “Con la entrada , la codificación de un grafo” incluye un paso que no se escribe: la máquina comprueba primero que la cadena recibida codifica de verdad un grafo, y si no, rechaza. Una cadena mal formada no está en el lenguaje, como dijimos en la semana 1.
- Para la computabilidad, los detalles de la codificación no importan. Una máquina de Turing puede convertir una lista de aristas en una matriz de adyacencia, y al revés. Así que si un lenguaje es decidible con una codificación razonable, lo es con cualquier otra. Por eso se escribe sin decir cuál.
- Para el costo sí van a importar. Un número escrito en binario ocupa muchísimo menos que el mismo número escrito con palitos, y un algoritmo que parece rápido medido contra la segunda escritura puede ser lento medido contra la primera. Es un tema de la semana 12.
Entre los objetos finitos que se pueden codificar hay uno especial: una máquina de Turing. Una máquina es
una séptupla de conjuntos finitos y una tabla finita. Se puede escribir completa, y ya lo hemos hecho: el
archivo machines/zeros_ones.tm es una cadena de 327 caracteres que describe a la máquina sin ambigüedad. Ese
archivo es un .
$ wc -c machines/zeros_ones.tm
327 machines/zeros_ones.tm
Entonces una máquina de Turing puede recibir como entrada otra máquina de Turing. La entrada del laboratorio de esta semana es exactamente eso: una máquina y unas cadenas, , y el programa que van a escribir hace con ellas lo que haría con . Que una máquina pueda recibir máquinas, ejecutarlas y hacerse preguntas sobre ellas es el punto de partida de la semana 9. Ahí la pregunta será qué se puede averiguar sobre una máquina leyendo su descripción, y la primera respuesta ya la conocen: ejecutarla y esperar no alcanza, porque puede no detenerse.
En la práctica. Un programa que recibe programas es lo más común que hay: un compilador, un intérprete, un depurador, un antivirus, el juez del curso. El código fuente es . Que los programas sean datos es la idea que hizo posible la computadora de propósito general: una sola máquina que ejecuta cualquier programa que se le entregue, en lugar de una máquina distinta para cada tarea.
El código de la semana
code/week-07/
├── tm.h struct Tm, lectura del formato .tm, configuraciones, un paso, ejecutar con límite
├── show_tm.cpp muestra un .tm como séptupla y como tabla
├── run_tm.cpp la ejecución de una máquina, configuración por configuración
├── multitape.h máquinas de k cintas y su simulación con una sola cinta
├── multitape_demo.cpp la máquina de dos cintas, la simulación y la tabla de pasos
├── ntm.h máquinas no deterministas y el recorrido por niveles
├── ntm_demo.cpp el árbol de ejecuciones, nivel por nivel
├── enumerate.cpp de una máquina que reconoce a un enumerador
├── machines/ las máquinas del capítulo, en formato .tm
├── errors/ cuatro descripciones que no son una máquina determinista válida
├── test_tm.cpp cada máquina contra un predicado; las cuentas de pasos; la que no se detiene
├── test_multitape.cpp la simulación coincide paso a paso y respeta la cota cuadrática
├── test_variants.cpp el recorrido por niveles y el enumerador
└── lab/tm_sim/ el laboratorio
make compila todo, y make test corre las pruebas con ASan y UBSan. Las pruebas comprueban con assert lo
que este capítulo afirma.
test_tmcompara cada decididor demachines/con una función de C++ que decide el mismo lenguaje, sobre todas las cadenas hasta cierta longitud, con un límite de 100 000 pasos, y comprueba que el límite no se alcanza nunca y que ninguna ejecución pasa de pasos. Comprueba las fórmulas exactas de pasos de las tres máquinas, las ejecuciones copiadas en estos apuntes, quehas_one_loops.tmpasa de 1 000 000 de pasos con en la configuración que dice la afirmación, el borde izquierdo y que los archivos deerrors/no se cargan.test_multitapecomprueba que la máquina de dos cintas decide en a lo sumo pasos con entradas de longitud , que la cinta de la simulación representa la configuración de la máquina simulada después de cada paso, las tres cotas de la cuenta de costo, y los números de la tabla.test_variantscomprueba que el recorrido por niveles acepta las cadenas con algún en el nivel esperado, que seguir siempre la primera opción no termina con las cadenas que empiezan con , que una máquina determinista vista como no determinista responde lo mismo, y que el enumerador imprime cada cadena en la ronda .
$ make test
test_tm:
zeros_ones: 16383 cadenas, a lo sumo 98 pasos
w_sep_w: 29524 cadenas, a lo sumo 50 pasos
anbncn: 29524 cadenas, a lo sumo 46 pasos
has_one: 16383 cadenas, a lo sumo 14 pasos
test_tm: ok
test_multitape:
dos cintas: 4095 cadenas, la simulación coincide paso a paso
180 máquinas al azar de 1, 2 y 3 cintas: la simulación coincide paso a paso
test_multitape: ok
test_variants: ok
Todas las pruebas pasaron.
Los archivos de machines/ son:
| Archivo | Qué hace | Estados |
|---|---|---|
zeros_ones.tm |
Decide | 6 |
w_sep_w.tm |
Decide , con = como separador |
10 |
anbncn.tm |
Decide | 8 |
has_one.tm |
Decide las cadenas con algún | 3 |
has_one_loops.tm |
Reconoce el mismo lenguaje y no lo decide | 3 |
left_end.tm |
No se detiene con ninguna entrada: repite una configuración en el borde izquierdo | 4 |
nondet_branch.tm |
No determinista, con una rama que no se detiene | 4 |
La cuenta de estados incluye a q_accept y q_reject. Para experimentar, copien una máquina, cámbienle una
transición y vuelvan a correr run_tm con las mismas cadenas.
En tm.h, igual que en el dfa.h de la semana 1, es un std::map con los nombres de los estados
como cadenas. Se eligió así para que el código se lea como la definición, y no por velocidad: cada paso busca
en el mapa comparando nombres. Para los ejemplos del capítulo sobra. Para el laboratorio no.
El laboratorio
En lab/tm_sim está el enunciado, un esqueleto y los casos. El problema es escribir un simulador: la entrada
es una máquina de Turing determinista en formato .tm, un límite de pasos y una lista de cadenas, y la
salida es, por cada cadena, acepta, rechaza o no se detuvo en N pasos.
cd lab/tm_sim
make # compila solution.cpp
make test # corre el juez con todos los casos
solution.cpp se escribe sin incluir tm.h. El trabajo está en tres sitios. El primero es leer el formato
completo: la línea limit: va entre la última transición y el bloque strings:. El segundo son los casos de
borde, que son los de este capítulo: la cadena vacía, un movimiento a la izquierda en la primera celda, una
transición que falta, una máquina que no se detiene, y una que se detiene justo en el paso . El tercero es
la cinta. Tiene que crecer hacia la derecha sin un tamaño fijo, y cada paso tiene que costar tiempo constante:
los casos grandes dan decenas de millones de pasos sobre cintas de cientos de miles de celdas, y una cinta que
se copia o se corre en cada paso no termina a tiempo. El enunciado propone además una opción para imprimir las
configuraciones, que el juez no usa y que les va a servir para depurar sus propias máquinas.
Resumen
- Una máquina de Turing es : un control finito, una cinta infinita hacia la derecha y un cabezal que lee, escribe y se mueve una celda por paso. : pasar a , escribir , mover hacia .
- En este curso, un movimiento en la primera celda deja el cabezal donde está, y un par sin transición lleva a .
- Una configuración es el estado, la cinta y la posición del cabezal, que está sobre el primer símbolo de . La ejecución es la secuencia de configuraciones, cada una produce la siguiente.
- Con una entrada, la máquina acepta, rechaza o no se detiene. Que no se haya detenido en pasos no dice que no se vaya a detener.
- Las máquinas de , y usan la misma técnica: marcar lo procesado y dar vueltas. Las tres se detienen en a lo sumo pasos.
- reconoce . Si además se detiene con toda entrada, es un decididor y lo decide. Un lenguaje es reconocible o decidible si alguna máquina lo reconoce o lo decide. Todo decidible es reconocible.
- Una máquina se describe en tres niveles: formal (la tabla), de implementación (el cabezal, en prosa) y alto (un algoritmo en pasos).
- Varias cintas no agregan poder: una cinta las simula con separadores y marcas, en pasos.
- El no determinismo tampoco: una máquina determinista recorre el árbol de ejecuciones por niveles. En profundidad no sirve, porque una rama puede ser infinita. La simulación cuesta un tiempo exponencial.
- Un lenguaje es reconocible si y solo si algún enumerador lo enumera. La construcción ejecuta la máquina pasos con las primeras cadenas, para
- El cálculo , las funciones recursivas, la máquina RAM y los lenguajes de programación calculan lo mismo que las máquinas de Turing. Una computadora más rápida no calcula más.
- La tesis de Church-Turing dice que lo calculable por un procedimiento mecánico es lo calculable por una máquina de Turing. No es un teorema: relaciona una definición con una noción intuitiva, y se sostiene con evidencia. Permite definir algoritmo y describir las máquinas en el nivel alto.
- es la codificación de un objeto como cadena. Una máquina de Turing también se codifica, , y puede ser la entrada de otra.
Ejercicios
- Escriban a mano las configuraciones de la máquina de
machines/zeros_ones.tmcon las entradas , y , y comprueben conrun_tm. En las dos que rechaza, digan qué casilla vacía de la tabla usó y qué quiere decir sobre la entrada. - Para cada configuración, escriban la que produce, con la máquina de
machines/w_sep_w.tmy las tres reglas de la sección Configuraciones: (a) ; (b) ; (c) ; (d) . Después expliquen con la tercera regla por quéleft_end.tmrepite la configuración . - Modifiquen la máquina de para que decida
. Den la tabla de lo que hace cada estado y el archivo
.tm, y pruébenlo conrun_tm --quieten diez cadenas, cinco del lenguaje y cinco que no. ¿Cuántos pasos da con ? - Den una descripción de implementación de una máquina que decide
. Digan qué marcas
usa y por qué se detiene siempre. Después escriban el archivo
.tmy compruébenlo con todas las cadenas de la forma con y . - Demuestren que la máquina de
machines/w_sep_w.tmdecide , con el esquema de la demostración de : enuncien qué conserva cada vuelta, y úsenlo para mostrar que si la máquina acepta, la entrada está en el lenguaje. Después cuenten los pasos con y , y verifiquen que son . - Diseñen una máquina de Turing que decida los palíndromos sobre . Den los tres niveles de descripción. En el formal, ¿cómo sabe la máquina dónde está el borde izquierdo de lo que falta revisar? Den una cota para la cantidad de pasos con una entrada de longitud .
- Demuestren que los lenguajes decidibles son cerrados bajo unión y bajo intersección, describiendo en el nivel alto la máquina que decide. Después demuestren que los reconocibles son cerrados bajo unión. ¿Por qué no sirve “ejecutar con ; si acepta, aceptar; si no, ejecutar con ”? ¿Qué técnica de este capítulo lo arregla?
- Una máquina con cinta infinita hacia los dos lados no tiene primera celda: el cabezal siempre puede ir a la izquierda. Describan, en el nivel de implementación, cómo la simula una máquina del modelo del curso. Una idea: doblar la cinta por la mitad, de modo que cada celda guarde dos símbolos. Digan qué tiene que recordar el estado.
- Den una máquina de dos cintas que decida en una cantidad de pasos lineal en la longitud de la entrada: la tabla en el formato de la sección Máquinas de varias cintas, y la cuenta de pasos. ¿Qué cota da el teorema del costo para su simulación con una cinta? Compárenla con los pasos de la máquina de una cinta.
- En la demostración de que el recorrido por niveles funciona, ¿dónde se usa que cada configuración tiene una cantidad finita de hijos? Supongan un modelo en el que una configuración pudiera tener infinitos hijos: muestren que el recorrido por niveles podría no llegar nunca al nivel 2. Después den una máquina no determinista de tres estados de trabajo en la que el recorrido en profundidad falle aunque se elija siempre la última opción en lugar de la primera.
- Un enumerador imprime en orden si imprime las cadenas de su lenguaje primero las más cortas y, entre las de igual longitud, en el orden del alfabeto, sin repetir. Demuestren que un lenguaje es decidible si y solo si algún enumerador lo imprime en orden. Una de las dos direcciones necesita tratar aparte el caso en que el lenguaje es finito: digan cuál y por qué.
- Para programar. Modifiquen
enumerate.cpppara que imprima cada cadena una sola vez, sin guardar la lista de las que ya imprimió. Pista: la cadena , que la máquina acepta en pasos, sale por primera vez en la ronda ; ¿cómo se reconoce, dentro de una ronda, que es la primera? - Para programar. Agreguen a
tm.huna función que ejecute una máquina y se detenga cuando una configuración se repite, respondiendo “no se detiene”. Pruébenla conleft_end.tmy conhas_one_loops.tm. ¿Con cuál de las dos no sirve, y por qué? ¿Puede esa función responder “no se detiene” con una máquina que sí se detiene? - Digan si cada afirmación es un teorema, es la tesis de Church-Turing o una consecuencia de ella, o es falsa, y justifiquen: (a) toda máquina de tres cintas tiene una equivalente de una cinta; (b) todo lo que hace un programa en Python lo puede hacer una máquina de Turing; (c) cualquier método de cálculo que se invente en el futuro se podrá simular con una máquina de Turing; (d) una computadora con el doble de memoria RAM decide lenguajes que la anterior no podía decidir, si las dos se idealizan con memoria sin límite; (e) si una máquina no se detuvo después de pasos, no se detiene.