Semana 7 — Máquinas de Turing
Objetivos
- Definir una máquina de Turing y seguir su ejecución escribiendo sus configuraciones.
- Distinguir entre decidir un lenguaje y reconocerlo.
- Explicar por qué las variantes de la máquina (varias cintas, no determinismo) no agregan poder.
- Enunciar la tesis de Church-Turing y decir por qué no es un teorema.
Sesión A — Máquinas de Turing: definición, configuraciones y ejemplos
Lectura: Apuntes, semana 7.
Apoyo: Sipser, sec. 3.1 (Turing Machines). Erickson, Models of Computation, nota 6 (Turing machines).
Temas:
- Qué les faltaba a los modelos anteriores: escribir, y volver sobre lo escrito. Una cinta infinita y un cabezal que va en los dos sentidos.
- Definición formal: , con .
- Configuración: estado, cinta y posición, escrita como . Una configuración produce la siguiente.
- Tres finales posibles: aceptar, rechazar o no detenerse nunca. Es la diferencia con todo lo anterior.
- Ejemplos seguidos paso a paso: , , y , que no era libre de contexto.
- Reconocer y decidir. Lenguajes reconocibles y decidibles.
- Los tres niveles de descripción: formal, de implementación y de alto nivel. Cuándo se usa cada uno.
- Error común: decir que una máquina “decide” un lenguaje cuando hay entradas con las que no se detiene.
Sesión B — Variantes de la máquina · Tesis de Church-Turing
Lectura: Apuntes, semana 7.
Apoyo: Sipser, sec. 3.2 (Variants of Turing Machines) y 3.3 (The Definition of Algorithm). Erickson, Models of Computation, nota 6.
Temas:
- Robustez: cambiar los detalles del modelo no cambia lo que puede calcular.
- Varias cintas: una sola cinta las simula, con marcas para cada cabezal. El costo en pasos es cuadrático; importa en la semana 12.
- No determinismo: una máquina determinista recorre el árbol de ejecuciones por niveles. Por qué en profundidad no sirve.
- Enumeradores: un lenguaje es reconocible si y solo si alguna máquina lo enumera.
- Otros modelos equivalentes: el cálculo de Church, las funciones recursivas, una máquina con memoria de acceso directo, y cualquier lenguaje de programación.
- Tesis de Church-Turing: lo calculable por un procedimiento mecánico es lo calculable por una máquina de Turing. Es una afirmación sobre el mundo, y no se demuestra.
- Qué permite: desde ahora, “algoritmo” y “máquina de Turing” son lo mismo, y se describe en alto nivel.
- Codificar objetos como cadenas: para un grafo, para una máquina.
- Error común: creer que una computadora real calcula más que una máquina de Turing porque es más rápida.
Laboratorio — Un simulador de máquinas de Turing
- Leer la tabla de una máquina de Turing de una cinta y una lista de cadenas.
- Simularla con cada cadena y responder
acepta,rechazaono se detuvo en N pasos, con el límite del enunciado. - Guardar la cinta de modo que crezca a la derecha sin límite.
- Con una opción, imprimir la secuencia de configuraciones en el formato de la clase.
- Escribir la máquina de en el formato del curso y comprobarla con su simulador.
Preguntas de repaso
- Escriban las configuraciones de la máquina de con la entrada
0011. - Den una descripción de implementación de una máquina que decide .
- ¿Qué diferencia hay entre un lenguaje decidible y uno reconocible? Si y su complemento son reconocibles, ¿qué se concluye?
- ¿Por qué la simulación de una máquina no determinista recorre el árbol por niveles?
- ¿Qué tipo de evidencia sostiene la tesis de Church-Turing, si no se puede demostrar?
Código de la semana
Compilar y probar dentro del contenedor del curso con make y make test.
Ejemplos (15)Errores (4)Pruebas (3)Laboratorio (3)Compilación (1)
Ejemplos
Los programas que usan los apuntes y la clase.
// De una máquina que reconoce un lenguaje a un enumerador de ese lenguaje:
//
// enumerate ARCHIVO.tm RONDAS
//
// En la ronda i se ejecuta la máquina i pasos con cada una de las primeras i cadenas
// s1, s2, …, si (en el orden de siempre: primero las más cortas) y se imprimen las que acepta.
// Una cadena aceptada vuelve a salir en las rondas siguientes: un enumerador puede repetir.
#include <cstddef>
#include <iostream>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>
#include "tm.h"
int main(int argc, char** argv) {
if (argc != 3) {
std::cerr << "uso: enumerate ARCHIVO.tm RONDAS\n";
return 2;
}
try {
Tm m = load_tm(argv[1]);
std::size_t rounds = std::stoul(argv[2]);
// Suficientes cadenas para tener s1, …, s_rondas.
std::size_t max_len = 0;
std::vector<std::string> strings = all_strings(m.alphabet, max_len);
while (strings.size() < rounds) {
strings = all_strings(m.alphabet, ++max_len);
}
std::set<std::string> printed;
std::vector<std::string> in_order;
for (std::size_t i = 1; i <= rounds; i++) {
std::cout << "ronda " << i << ":";
for (std::size_t j = 0; j < i; j++) {
if (run(m, strings[j], static_cast<long long>(i)).outcome == Outcome::Accept) {
std::cout << ' ' << (strings[j].empty() ? "ε" : strings[j]);
if (printed.insert(strings[j]).second) {
in_order.push_back(strings[j]);
}
}
}
std::cout << '\n';
}
std::cout << "cadenas distintas impresas en " << rounds << " rondas (" << in_order.size() << "):";
for (const std::string& s : in_order) {
std::cout << ' ' << (s.empty() ? "ε" : s);
}
std::cout << '\n';
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// La máquina de dos cintas del capítulo y su simulación con una sola cinta.
//
// multitape_demo run CADENA la máquina de dos cintas, paso a paso
// multitape_demo sim CADENA la cinta única de la simulación después de cada paso simulado
// multitape_demo table cuántos pasos cuesta cada cosa con 0^n 1^n
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <string>
#include "multitape.h"
#include "tm.h"
static const char* verdict(const std::string& state, const MultiTm& m) {
return state == m.accept ? "acepta" : "rechaza";
}
int main(int argc, char** argv) {
std::string mode = argc > 1 ? argv[1] : "";
try {
MultiTm m = two_tape_zeros_ones();
if (mode == "run" && argc == 3) {
std::string w = argv[2];
MultiConfig c = initial_config(m, w);
long long steps = 0;
std::cout << "w = " << (w.empty() ? "ε" : w) << '\n';
std::cout << std::setw(3) << steps << " " << to_string(c) << '\n';
while (!halted(m, c)) {
step(m, c);
steps++;
std::cout << std::setw(3) << steps << " " << to_string(c) << '\n';
}
std::cout << " " << verdict(c.state, m) << " en " << steps << (steps == 1 ? " paso\n" : " pasos\n");
} else if (mode == "sim" && argc == 3) {
std::string w = argv[2];
Simulation s = start_simulation(m, w);
std::cout << "w = " << (w.empty() ? "ε" : w) << '\n';
std::cout << "pasos de M estado de M cinta de S pasos de S\n";
auto row = [&s]() {
std::cout << std::setw(10) << s.rounds << " " << std::left << std::setw(11) << s.state << " "
<< std::setw(21) << to_string(s.tape) << std::right << std::setw(13) << s.tape.steps << '\n';
};
row();
while (s.state != m.accept && s.state != m.reject) {
simulate_step(m, s);
row();
}
std::cout << " " << verdict(s.state, m) << ": " << s.rounds << (s.rounds == 1 ? " paso de M, " : " pasos de M, ")
<< s.tape.steps
<< " pasos de S (" << s.setup << " para preparar la cinta)\n";
} else if (mode == "table") {
Tm one = load_tm("machines/zeros_ones.tm");
std::cout << "Entrada 0^n 1^n, de longitud 2n. Pasos hasta aceptar:\n\n";
std::cout << " n una cinta (zeros_ones.tm) dos cintas dos cintas simuladas en una\n";
for (int n = 5; n <= 320; n *= 2) {
std::string w = std::string(n, '0') + std::string(n, '1');
Run direct = run(one, w, 100000000);
MultiRun two = run_multi(m, w, 100000000);
SimulationRun sim = run_simulation(m, w, 100000000);
if (direct.outcome != Outcome::Accept || two.outcome != Outcome::Accept ||
sim.outcome != Outcome::Accept) {
throw std::runtime_error("alguna de las tres no aceptó");
}
std::cout << std::setw(5) << n << std::setw(20) << direct.steps << std::setw(21) << two.steps
<< std::setw(21) << sim.steps << '\n';
}
} else {
std::cerr << "uso: multitape_demo run CADENA | sim CADENA | table\n";
return 2;
}
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Máquina de Turing de k cintas, y su simulación con una sola cinta.
//
// La máquina de k cintas se ejecuta directamente con run_multi. La simulación (struct
// Simulation) trabaja sobre una única cinta y solo la toca como lo haría un cabezal: lee la
// celda donde está, escribe en ella y se mueve una celda. Cada una de esas operaciones cuenta
// como un paso, así que al final se sabe cuántos pasos da la máquina de una cinta.
//
// El formato .tm del curso describe máquinas de una cinta. La máquina de dos cintas del
// capítulo se arma en C++, en two_tape_zeros_ones().
#ifndef MULTITAPE_H
#define MULTITAPE_H
#include <cstddef>
#include <map>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
#include "tm.h"
// ------------------------------------------------------------
// La máquina de k cintas
// ------------------------------------------------------------
// δ(q, a1…ak) = (r, b1…bk, D1…Dk). Cada movimiento es L, R o S (quedarse).
struct MultiAction {
std::string state;
std::string write; // un símbolo por cinta
std::string move; // un movimiento por cinta
};
struct MultiTm {
std::size_t tapes = 1; // k
std::vector<std::string> states; // Q
std::vector<char> alphabet; // Σ
std::vector<char> tape; // Γ
std::map<std::pair<std::string, std::string>, MultiAction> delta; // δ : Q' × Γ^k → Q × Γ^k × {L, R, S}^k
std::string start; // q0
std::string accept; // q_accept
std::string reject; // q_reject
};
struct MultiConfig {
std::string state;
std::vector<std::string> cells; // el contenido de cada cinta
std::vector<std::size_t> head; // la posición de cada cabezal
};
// La entrada va en la primera cinta. Las demás empiezan en blanco.
inline MultiConfig initial_config(const MultiTm& m, const std::string& w) {
MultiConfig c;
c.state = m.start;
c.cells.assign(m.tapes, "");
c.cells[0] = w;
c.head.assign(m.tapes, 0);
return c;
}
inline bool halted(const MultiTm& m, const MultiConfig& c) {
return c.state == m.accept || c.state == m.reject;
}
// Los k símbolos que están bajo los cabezales.
inline std::string scanned(const MultiConfig& c) {
std::string symbols;
for (std::size_t i = 0; i < c.cells.size(); i++) {
symbols += c.head[i] < c.cells[i].size() ? c.cells[i][c.head[i]] : BLANK;
}
return symbols;
}
// Un paso. Sin transición para lo que leen los cabezales, la máquina pasa a q_reject sin
// escribir ni moverse.
inline void step(const MultiTm& m, MultiConfig& c) {
auto it = m.delta.find({c.state, scanned(c)});
if (it == m.delta.end()) {
c.state = m.reject;
return;
}
const MultiAction& action = it->second;
for (std::size_t i = 0; i < m.tapes; i++) {
if (c.head[i] >= c.cells[i].size()) {
c.cells[i].resize(c.head[i] + 1, BLANK);
}
c.cells[i][c.head[i]] = action.write[i];
if (action.move[i] == 'R') {
c.head[i]++;
} else if (action.move[i] == 'L' && c.head[i] > 0) {
c.head[i]--;
}
}
c.state = action.state;
}
struct MultiRun {
Outcome outcome = Outcome::Limit;
long long steps = 0;
};
inline MultiRun run_multi(const MultiTm& m, const std::string& w, long long limit) {
MultiRun result;
MultiConfig c = initial_config(m, w);
while (!halted(m, c) && result.steps < limit) {
step(m, c);
result.steps++;
}
if (c.state == m.accept) {
result.outcome = Outcome::Accept;
} else if (c.state == m.reject) {
result.outcome = Outcome::Reject;
}
return result;
}
// Cada cinta en una línea, con el símbolo bajo el cabezal entre corchetes.
inline std::string to_string(const MultiConfig& c) {
std::string text = c.state;
for (std::size_t i = 0; i < c.cells.size(); i++) {
std::string cells = c.cells[i];
std::size_t end = cells.size();
while (end > 0 && cells[end - 1] == BLANK) {
end--;
}
cells.resize(end < c.head[i] + 1 ? c.head[i] + 1 : end, BLANK);
text += " cinta " + std::to_string(i + 1) + ": ";
for (std::size_t j = 0; j < cells.size(); j++) {
text += (j == c.head[i]) ? std::string("[") + cells[j] + "]" : std::string(1, cells[j]);
}
}
return text;
}
// La máquina de dos cintas del capítulo. Decide { 0^n 1^n : n >= 0 } con una pasada: copia los
// ceros a la segunda cinta y después los va descontando, uno por cada 1.
//
// q0 marca con $ el inicio de la cinta 2 (y acepta de una vez la cadena vacía)
// q1 copia cada 0 a la cinta 2; con el primer 1, retrocede un paso en la cinta 2
// q2 por cada 1 de la cinta 1, retrocede sobre un 0 de la cinta 2
inline MultiTm two_tape_zeros_ones() {
MultiTm m;
m.tapes = 2;
m.states = {"q0", "q1", "q2", "q_accept", "q_reject"};
m.alphabet = {'0', '1'};
m.tape = {'0', '1', '$', BLANK};
m.start = "q0";
m.accept = "q_accept";
m.reject = "q_reject";
m.delta[{"q0", "__"}] = {"q_accept", "__", "SS"};
m.delta[{"q0", "0_"}] = {"q1", "0$", "SR"};
m.delta[{"q1", "0_"}] = {"q1", "00", "RR"};
m.delta[{"q1", "1_"}] = {"q2", "1_", "SL"};
m.delta[{"q2", "10"}] = {"q2", "10", "RL"};
m.delta[{"q2", "_$"}] = {"q_accept", "_$", "SS"};
return m;
}
// ------------------------------------------------------------
// Una sola cinta, usada solo como la usa un cabezal
// ------------------------------------------------------------
// Una celda de la cinta única. El alfabeto de esa cinta tiene, por cada símbolo a de Γ, el
// símbolo a y el símbolo "a con marca", además del separador #. La marca dice que ahí está
// uno de los cabezales de la máquina de k cintas.
struct Cell {
char symbol = BLANK;
bool mark = false;
bool operator==(const Cell& other) const = default;
};
inline constexpr char SEPARATOR = '#';
struct OneTape {
std::vector<Cell> cells;
std::size_t head = 0;
long long steps = 0; // pasos de la máquina de una cinta
Cell read() const { return head < cells.size() ? cells[head] : Cell{}; }
// Un paso de máquina de Turing: escribir en la celda actual y mover el cabezal.
void write_move(Cell c, char direction) {
if (head >= cells.size()) {
cells.resize(head + 1);
}
cells[head] = c;
if (direction == 'R') {
head++;
} else if (head > 0) {
head--;
}
steps++;
}
// Moverse sin cambiar lo escrito.
void move(char direction) { write_move(read(), direction); }
};
inline bool is_separator(const Cell& c) {
return c.symbol == SEPARATOR && !c.mark;
}
// La cinta única, de la primera celda al último separador: #[0]011#[_]#
inline std::string to_string(const OneTape& t) {
std::size_t end = t.cells.size();
while (end > 0 && t.cells[end - 1] == Cell{}) {
end--;
}
std::string text;
for (std::size_t i = 0; i < end; i++) {
const Cell& c = t.cells[i];
text += c.mark ? std::string("[") + c.symbol + "]" : std::string(1, c.symbol);
}
return text;
}
// ------------------------------------------------------------
// La simulación
// ------------------------------------------------------------
// El estado de la máquina S que simula a M. Lo que S recuerda fuera de la cinta es una
// cantidad acotada de datos (el estado de M, k símbolos, contadores hasta k + 1): cabe en
// sus estados.
struct Simulation {
OneTape tape;
std::string state; // el estado de M
long long rounds = 0; // pasos de M ya simulados
long long setup = 0; // pasos de S que costó preparar la cinta
long long length = 0; // celdas en uso: de la primera al último separador
};
// Vuelve a la primera celda desde el último separador, contando separadores: el primero de la
// cinta es el número k + 1 que se encuentra yendo hacia la izquierda.
inline void return_to_start(OneTape& t, std::size_t k) {
std::size_t seen = 1;
while (seen < k + 1) {
t.move('L');
if (is_separator(t.read())) {
seen++;
}
}
}
// Prepara la cinta: de w1 w2 … wn pasa a #[w1]w2…wn#[_]#[_]#…#, con k tramos.
inline Simulation start_simulation(const MultiTm& m, const std::string& w) {
Simulation s;
for (char a : w) {
s.tape.cells.push_back({a, false});
}
s.state = m.start;
OneTape& t = s.tape;
const std::size_t k = m.tapes;
// Correr la entrada una celda a la derecha: en cada paso se deja lo que se traía y se
// levanta lo que había. La entrada no tiene blancos, así que el primer blanco es su final.
Cell carried = {SEPARATOR, false};
bool first = true;
while (true) {
Cell here = t.read();
t.write_move(carried, 'R');
if (here == Cell{}) {
break;
}
carried = {here.symbol, first};
first = false;
}
if (first) {
t.write_move({BLANK, true}, 'R'); // entrada vacía: el cabezal de la cinta 1 está sobre un blanco
}
// Los otros k − 1 tramos, cada uno con un blanco marcado, y el último separador.
for (std::size_t i = 1; i < k; i++) {
t.write_move({SEPARATOR, false}, 'R');
t.write_move({BLANK, true}, 'R');
}
t.write_move({SEPARATOR, false}, 'R');
t.move('L'); // de vuelta sobre el último separador
s.length = static_cast<long long>(t.head) + 1;
return_to_start(t, k);
s.setup = t.steps;
return s;
}
// Simula un paso de M. El cabezal de S empieza y termina en la primera celda.
inline void simulate_step(const MultiTm& m, Simulation& s) {
OneTape& t = s.tape;
const std::size_t k = m.tapes;
// Pasada 1, hacia la derecha: anotar el símbolo marcado de cada tramo.
std::string seen(k, BLANK);
std::size_t segment = 0;
while (segment < k) {
t.move('R');
Cell here = t.read();
if (is_separator(here)) {
segment++;
} else if (here.mark) {
seen[segment] = here.symbol;
}
}
// Ya se sabe qué hace M. Sin transición, pasa a q_reject y la simulación termina.
auto it = m.delta.find({s.state, seen});
if (it == m.delta.end()) {
s.state = m.reject;
s.rounds++;
return_to_start(t, k);
return;
}
const MultiAction& action = it->second;
return_to_start(t, k);
// Pasada 2, hacia la derecha: actualizar cada tramo.
for (std::size_t i = 0; i < k; i++) {
// Del separador que abre el tramo i hasta su celda marcada.
do {
t.move('R');
} while (!t.read().mark);
Cell written = {action.write[i], false};
if (action.move[i] == 'S') {
written.mark = true;
t.write_move(written, 'R');
} else if (action.move[i] == 'L') {
t.write_move(written, 'L');
if (is_separator(t.read())) {
// El cabezal de M estaba en su primera celda: se queda ahí.
t.move('R');
t.write_move({action.write[i], true}, 'R');
} else {
t.write_move({t.read().symbol, true}, 'R');
}
} else {
t.write_move(written, 'R');
if (!is_separator(t.read())) {
t.write_move({t.read().symbol, true}, 'R');
} else {
// El cabezal de M llega a una celda que este tramo todavía no tiene. Se pone ahí un
// blanco marcado y todo lo que sigue se corre una celda a la derecha. Quedan por
// dejar k − i separadores; el último cae en la primera celda libre de la cinta.
Cell carried = {BLANK, true};
std::size_t placed = 0;
while (placed < k - i) {
Cell here = t.read();
t.write_move(carried, 'R');
if (is_separator(carried)) {
placed++;
}
carried = here;
}
s.length++;
// Volver hasta el separador que cierra el tramo i: es el número k − i desde el final.
std::size_t passed = 0;
while (passed < k - i) {
t.move('L');
if (is_separator(t.read())) {
passed++;
}
}
}
}
// Avanzar hasta el separador que cierra el tramo i.
while (!is_separator(t.read())) {
t.move('R');
}
}
return_to_start(t, k);
s.state = action.state;
s.rounds++;
}
// Lo que la cinta de S dice sobre M: los k tramos y la posición de la marca en cada uno.
// Lanza std::runtime_error si la cinta no tiene la forma #…#…#, con una marca por tramo.
inline MultiConfig decode(const MultiTm& m, const Simulation& s) {
MultiConfig c;
c.state = s.state;
const std::vector<Cell>& cells = s.tape.cells;
if (cells.empty() || !is_separator(cells[0])) {
throw std::runtime_error("la cinta no empieza con un separador");
}
std::string current;
std::size_t head = 0;
int marks = 0;
for (std::size_t i = 1; i < cells.size() && c.cells.size() < m.tapes; i++) {
if (is_separator(cells[i])) {
if (marks != 1) {
throw std::runtime_error("un tramo no tiene exactamente una marca");
}
c.cells.push_back(current);
c.head.push_back(head);
current.clear();
marks = 0;
} else {
if (cells[i].mark) {
head = current.size();
marks++;
}
current += cells[i].symbol;
}
}
if (c.cells.size() != m.tapes) {
throw std::runtime_error("la cinta no tiene k tramos");
}
return c;
}
// Dos configuraciones de M son la misma si coinciden el estado, los cabezales y el contenido
// de cada cinta sin contar los blancos del final.
inline bool same_config(MultiConfig a, MultiConfig b) {
if (a.state != b.state || a.head != b.head || a.cells.size() != b.cells.size()) {
return false;
}
for (std::size_t i = 0; i < a.cells.size(); i++) {
for (std::string* cells : {&a.cells[i], &b.cells[i]}) {
while (!cells->empty() && cells->back() == BLANK) {
cells->pop_back();
}
}
if (a.cells[i] != b.cells[i]) {
return false;
}
}
return true;
}
struct SimulationRun {
Outcome outcome = Outcome::Limit;
long long rounds = 0; // pasos de M
long long steps = 0; // pasos de S, contando la preparación
};
inline SimulationRun run_simulation(const MultiTm& m, const std::string& w, long long limit) {
Simulation s = start_simulation(m, w);
while (s.state != m.accept && s.state != m.reject && s.rounds < limit) {
simulate_step(m, s);
}
SimulationRun result;
result.rounds = s.rounds;
result.steps = s.tape.steps;
if (s.state == m.accept) {
result.outcome = Outcome::Accept;
} else if (s.state == m.reject) {
result.outcome = Outcome::Reject;
}
return result;
}
#endif// El árbol de ejecuciones de una máquina no determinista, nivel por nivel:
//
// ntm_demo ARCHIVO.tm CADENA [NIVELES]
//
// Imprime las configuraciones de cada nivel hasta que alguna acepta, todas las ramas se
// detienen o se llega a NIVELES (por omisión, 8). Después muestra qué pasa si se sigue
// siempre la primera opción, como haría un recorrido en profundidad.
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "ntm.h"
int main(int argc, char** argv) {
if (argc < 3 || argc > 4) {
std::cerr << "uso: ntm_demo ARCHIVO.tm CADENA [NIVELES]\n";
return 2;
}
try {
Ntm m = load_ntm(argv[1]);
std::string w = argv[2];
long long max_depth = argc == 4 ? std::stoll(argv[3]) : 8;
std::cout << "w = " << (w.empty() ? "ε" : w) << '\n';
std::vector<Config> level = {{m.start, w, 0}};
bool accepted = false;
for (long long depth = 0; depth <= max_depth && !level.empty() && !accepted; depth++) {
std::cout << "nivel " << depth << ":";
std::vector<Config> next_level;
for (const Config& c : level) {
std::cout << " " << to_string(c);
accepted = accepted || c.state == m.accept;
for (const Config& child : successors(m, c)) {
next_level.push_back(child);
}
}
std::cout << '\n';
level = next_level;
}
Search search = breadth_first(m, w, max_depth);
if (search.outcome == Outcome::Accept) {
std::cout << "por niveles: acepta en el nivel " << search.depth << ", después de revisar " << search.visited
<< " configuraciones\n";
} else if (search.outcome == Outcome::Reject) {
std::cout << "por niveles: rechaza, todas las ramas se detuvieron antes del nivel " << search.depth + 1
<< '\n';
} else {
std::cout << "por niveles: ninguna rama aceptó hasta el nivel " << max_depth << '\n';
}
const long long limit = 1000000;
Run first = first_branch(m, w, limit);
if (first.outcome == Outcome::Limit) {
std::cout << "siempre la primera opción: no se detuvo en " << limit << " pasos\n";
} else {
std::cout << "siempre la primera opción: " << (first.outcome == Outcome::Accept ? "acepta" : "rechaza")
<< " en " << first.steps << " pasos\n";
}
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Máquina de Turing no determinista: δ(q, a) es un conjunto de acciones, y la máquina acepta
// si alguna de sus ejecuciones llega a q_accept. Se escribe en el mismo formato .tm, con
// varias líneas para el mismo par de estado y símbolo.
//
// Aquí está la simulación determinista: recorrer el árbol de ejecuciones por niveles.
#ifndef NTM_H
#define NTM_H
#include <cstddef>
#include <fstream>
#include <map>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
#include "tm.h"
struct Ntm {
std::vector<std::string> states; // Q
std::vector<char> alphabet; // Σ
std::vector<char> tape; // Γ
std::map<std::pair<std::string, char>, std::vector<Action>> delta; // δ : Q' × Γ → P(Q × Γ × {L, R})
std::string start; // q0
std::string accept; // q_accept
std::string reject; // q_reject
};
inline Ntm load_ntm(const std::string& path) {
std::ifstream file(path);
if (!file) {
throw std::runtime_error("no se pudo abrir " + path);
}
try {
Description d = read_description(file);
Ntm m;
m.states = d.states;
m.alphabet = d.alphabet;
m.tape = d.tape;
m.start = d.start;
m.accept = d.accept;
m.reject = d.reject;
for (const Rule& rule : d.rules) {
m.delta[{rule.state, rule.read}].push_back(rule.action); // en el orden del archivo
}
return m;
} catch (const std::runtime_error& error) {
throw std::runtime_error(path + ": " + error.what());
}
}
// Las opciones de la máquina en una configuración. Sin ninguna línea, la única es ir a q_reject.
inline std::vector<Action> choices(const Ntm& m, const Config& c) {
auto it = m.delta.find({c.state, scanned(c)});
if (it == m.delta.end()) {
return {{m.reject, scanned(c), 'R'}};
}
return it->second;
}
// Los hijos de una configuración en el árbol de ejecuciones. Una configuración final no tiene.
inline std::vector<Config> successors(const Ntm& m, const Config& c) {
std::vector<Config> result;
if (c.state == m.accept || c.state == m.reject) {
return result;
}
for (const Action& action : choices(m, c)) {
Config next = c;
apply(next, action);
result.push_back(next);
}
return result;
}
struct Search {
Outcome outcome = Outcome::Limit;
long long depth = 0; // el nivel al que llegó
long long visited = 0; // cuántas configuraciones sacó de la cola
};
// Recorre el árbol por niveles: el nivel d tiene las configuraciones a las que se llega con d
// pasos. Acepta en cuanto encuentra una con q_accept. Rechaza si un nivel queda vacío, porque
// entonces todas las ramas se detuvieron sin aceptar. Si pasa de max_depth, no se sabe.
inline Search breadth_first(const Ntm& m, const std::string& w, long long max_depth) {
Search result;
std::vector<Config> level = {{m.start, w, 0}};
for (long long depth = 0; depth <= max_depth; depth++) {
result.depth = depth;
std::vector<Config> next_level;
for (const Config& c : level) {
result.visited++;
if (c.state == m.accept) {
result.outcome = Outcome::Accept;
return result;
}
for (const Config& child : successors(m, c)) {
next_level.push_back(child);
}
}
if (next_level.empty()) {
result.outcome = Outcome::Reject;
return result;
}
level = next_level;
}
return result;
}
// Lo que haría un recorrido en profundidad antes de retroceder por primera vez: seguir
// siempre la primera opción. Si esa rama no se detiene, el recorrido no vuelve nunca.
inline Run first_branch(const Ntm& m, const std::string& w, long long limit) {
Run result;
result.last = {m.start, w, 0};
while (result.last.state != m.accept && result.last.state != m.reject && result.steps < limit) {
apply(result.last, choices(m, result.last).front());
result.steps++;
}
if (result.last.state == m.accept) {
result.outcome = Outcome::Accept;
} else if (result.last.state == m.reject) {
result.outcome = Outcome::Reject;
}
return result;
}
#endif// Sigue una máquina de Turing con una o más cadenas, configuración por configuración:
//
// run_tm [--limit N] [--show K] [--quiet] ARCHIVO.tm CADENA...
//
// --limit N da a lo sumo N pasos por cadena (por omisión, 1000)
// --show K imprime solo las primeras K configuraciones, y la última si la máquina se detuvo
// --quiet no imprime configuraciones, solo el resultado
// La cadena vacía se pasa como '' en la terminal.
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "tm.h"
int main(int argc, char** argv) {
long long limit = 1000;
long long show = -1;
bool quiet = false;
int next = 1;
try {
while (next < argc && std::string(argv[next]).rfind("--", 0) == 0) {
std::string option = argv[next++];
if (option == "--quiet") {
quiet = true;
} else if (option == "--limit" && next < argc) {
limit = std::stoll(argv[next++]);
} else if (option == "--show" && next < argc) {
show = std::stoll(argv[next++]);
} else {
std::cerr << "opción desconocida: " << option << '\n';
return 2;
}
}
if (argc - next < 2) {
std::cerr << "uso: run_tm [--limit N] [--show K] [--quiet] ARCHIVO.tm CADENA...\n";
return 2;
}
Tm m = load_tm(argv[next++]);
for (; next < argc; next++) {
std::string w = argv[next];
std::cout << "w = " << (w.empty() ? "ε" : w) << '\n';
Config c = initial_config(m, w);
long long steps = 0;
bool skipped = false;
while (true) {
bool last = halted(m, c) || steps == limit;
if (!quiet && (show < 0 || steps < show || halted(m, c))) {
std::cout << std::setw(5) << steps << " " << to_string(c) << '\n';
} else if (!quiet && !skipped) {
std::cout << " …\n";
skipped = true;
}
if (last) {
break;
}
step(m, c);
steps++;
}
const char* unit = steps == 1 ? " paso\n" : " pasos\n";
if (c.state == m.accept) {
std::cout << " acepta en " << steps << unit;
} else if (c.state == m.reject) {
std::cout << " rechaza en " << steps << unit;
} else {
std::cout << " no se detuvo en " << limit << " pasos\n";
}
}
} catch (const std::exception& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Muestra una máquina de Turing como séptupla y como tabla: show_tm ARCHIVO.tm
// En la tabla, un punto es un par sin transición: ese par lleva a q_reject.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include "tm.h"
static std::string pad(const std::string& text, std::size_t width) {
return text.size() >= width ? text : text + std::string(width - text.size(), ' ');
}
template <typename Items>
static void print_set(const std::string& label, const Items& items) {
std::cout << label << "{";
bool first = true;
for (const auto& item : items) {
std::cout << (first ? "" : ", ") << item;
first = false;
}
std::cout << "}\n";
}
int main(int argc, char** argv) {
if (argc != 2) {
std::cerr << "uso: show_tm ARCHIVO.tm\n";
return 2;
}
try {
Tm m = load_tm(argv[1]);
print_set("Q = ", m.states);
print_set("Σ = ", m.alphabet);
print_set("Γ = ", m.tape);
std::cout << "q0 = " << m.start << ", q_accept = " << m.accept << ", q_reject = " << m.reject << "\n\n";
// Una fila por cada estado del que sale alguna transición posible, una columna por símbolo.
std::size_t name_width = 1;
std::size_t cell_width = 1;
for (const std::string& q : m.states) {
name_width = std::max(name_width, q.size());
}
std::vector<std::vector<std::string>> rows;
for (const std::string& q : m.states) {
if (q == m.accept || q == m.reject) {
continue;
}
std::vector<std::string> row = {q};
for (char a : m.tape) {
auto it = m.delta.find({q, a});
std::string cell = ".";
if (it != m.delta.end()) {
cell = it->second.state + " " + it->second.write + " " + it->second.move;
}
cell_width = std::max(cell_width, cell.size());
row.push_back(cell);
}
rows.push_back(row);
}
std::string header = pad("δ", name_width + 1); // δ ocupa dos bytes y una columna
for (char a : m.tape) {
header += " " + pad(std::string(1, a), cell_width);
}
rows.insert(rows.begin(), {header});
for (const std::vector<std::string>& row : rows) {
std::string line = pad(row[0], name_width);
for (std::size_t i = 1; i < row.size(); i++) {
line += " " + pad(row[i], cell_width);
}
while (!line.empty() && line.back() == ' ') {
line.pop_back();
}
std::cout << line << '\n';
}
std::cout << "\ntransiciones escritas: " << m.delta.size() << " de " << (rows.size() - 1) * m.tape.size() << '\n';
} catch (const std::runtime_error& error) {
std::cerr << "error: " << error.what() << '\n';
return 1;
}
}// Máquina de Turing de una cinta. El struct tiene los siete componentes de la definición
// M = (Q, Σ, Γ, δ, q0, q_accept, q_reject), con los nombres del formato .tm de code/formats.md.
// Además: leer ese formato, las configuraciones u q v, dar un paso y ejecutar con un límite
// de pasos.
//
// El modelo es el del curso: la cinta es infinita solo hacia la derecha, un movimiento L en la
// primera celda deja el cabezal donde está, y un par (estado, símbolo) sin transición lleva a
// q_reject.
//
// La lectura de campos sigue la de code/week-01/dfa.h, adaptada a los campos de una máquina.
#ifndef TM_H
#define TM_H
#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
// El símbolo blanco, como se escribe en los archivos.
inline constexpr char BLANK = '_';
// El resultado de δ(q, a) = (r, b, D): pasar a r, escribir b, mover el cabezal hacia D.
struct Action {
std::string state; // r
char write = BLANK; // b
char move = 'R'; // D: 'L' o 'R'
};
struct Tm {
std::vector<std::string> states; // Q, en el orden del archivo
std::vector<char> alphabet; // Σ, el alfabeto de entrada
std::vector<char> tape; // Γ, el alfabeto de la cinta
std::map<std::pair<std::string, char>, Action> delta; // δ : Q' × Γ → Q × Γ × {L, R}
std::string start; // q0
std::string accept; // q_accept
std::string reject; // q_reject
};
// ------------------------------------------------------------
// Leer el formato .tm
// ------------------------------------------------------------
// Una línea de delta: "estado lee -> destino escribe movimiento".
struct Rule {
std::string state;
char read = BLANK;
Action action;
};
// Lo que dice un archivo .tm, sin exigir todavía que sea determinista: una máquina no
// determinista se escribe igual, con varias líneas para el mismo par (ntm.h).
struct Description {
std::vector<std::string> states;
std::vector<char> alphabet;
std::vector<char> tape;
std::string start;
std::string accept;
std::string reject;
std::vector<Rule> rules;
};
inline std::vector<std::string> split_words(const std::string& text) {
std::istringstream in(text);
std::vector<std::string> words;
std::string word;
while (in >> word) {
words.push_back(word);
}
return words;
}
// Lanza std::runtime_error si la descripción no cumple la definición.
inline void check_description(const Description& d) {
std::set<std::string> q(d.states.begin(), d.states.end());
std::set<char> sigma(d.alphabet.begin(), d.alphabet.end());
std::set<char> gamma(d.tape.begin(), d.tape.end());
if (q.size() != d.states.size()) {
throw std::runtime_error("hay un estado repetido en states");
}
if (sigma.size() != d.alphabet.size() || gamma.size() != d.tape.size()) {
throw std::runtime_error("hay un símbolo repetido en alphabet o en tape");
}
if (gamma.count(BLANK) == 0) {
throw std::runtime_error("el símbolo blanco _ tiene que estar en tape");
}
if (sigma.count(BLANK) > 0) {
throw std::runtime_error("el símbolo blanco _ no puede estar en alphabet");
}
for (char a : d.alphabet) {
if (gamma.count(a) == 0) {
throw std::runtime_error(std::string("el símbolo ") + a + " está en alphabet y no en tape");
}
}
for (const std::string* name : {&d.start, &d.accept, &d.reject}) {
if (q.count(*name) == 0) {
throw std::runtime_error("el estado " + *name + " no está en states");
}
}
if (d.accept == d.reject) {
throw std::runtime_error("accept y reject tienen que ser estados distintos");
}
for (const Rule& rule : d.rules) {
const std::string where = "δ(" + rule.state + ", " + rule.read + ")";
if (q.count(rule.state) == 0 || q.count(rule.action.state) == 0) {
throw std::runtime_error(where + ": hay un estado que no está en states");
}
if (gamma.count(rule.read) == 0 || gamma.count(rule.action.write) == 0) {
throw std::runtime_error(where + ": hay un símbolo que no está en tape");
}
if (rule.action.move != 'L' && rule.action.move != 'R') {
throw std::runtime_error(where + ": el movimiento es L o R");
}
if (rule.state == d.accept || rule.state == d.reject) {
throw std::runtime_error(where + ": de " + rule.state + " no sale ninguna transición, la máquina ya se detuvo");
}
}
}
// Lee una descripción completa, hasta el final de la entrada.
inline Description read_description(std::istream& in) {
int number = 0;
auto fail = [&number](const std::string& message) {
throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
};
// Siguiente línea que no es comentario ni está vacía. Devuelve false al final.
auto next_line = [&in, &number](std::vector<std::string>& words) {
std::string line;
while (std::getline(in, line)) {
number++;
if (!line.empty() && line[0] == '#') {
continue;
}
words = split_words(line);
if (!words.empty()) {
return true;
}
}
return false;
};
// Un campo: "nombre: valor valor ...". Devuelve los valores.
auto field = [&next_line, &fail](const std::string& name) {
std::vector<std::string> words;
if (!next_line(words) || words[0] != name + ":") {
fail("se esperaba el campo " + name + ":");
}
words.erase(words.begin());
return words;
};
auto symbols = [&field, &fail](const std::string& name) {
std::vector<char> result;
for (const std::string& symbol : field(name)) {
if (symbol.size() != 1 || symbol[0] == '#') {
fail("un símbolo es un solo carácter distinto de #: " + symbol);
}
result.push_back(symbol[0]);
}
return result;
};
auto one_state = [&field, &fail](const std::string& name) {
std::vector<std::string> words = field(name);
if (words.size() != 1) {
fail(name + ": lleva exactamente un estado");
}
return words[0];
};
Description d;
d.states = field("states");
d.alphabet = symbols("alphabet");
d.tape = symbols("tape");
d.start = one_state("start");
d.accept = one_state("accept");
d.reject = one_state("reject");
if (!field("delta").empty()) {
fail("después de delta: las transiciones van una por línea");
}
std::vector<std::string> words;
while (next_line(words)) {
if (words.size() != 6 || words[1].size() != 1 || words[2] != "->" || words[4].size() != 1 ||
words[5].size() != 1) {
fail("una transición se escribe: estado lee -> destino escribe movimiento");
}
d.rules.push_back({words[0], words[1][0], {words[3], words[4][0], words[5][0]}});
}
try {
check_description(d);
} catch (const std::runtime_error& error) {
fail(error.what());
}
return d;
}
// Una máquina determinista: a lo sumo una línea por cada par de estado y símbolo.
inline Tm read_tm(std::istream& in) {
Description d = read_description(in);
Tm m;
m.states = d.states;
m.alphabet = d.alphabet;
m.tape = d.tape;
m.start = d.start;
m.accept = d.accept;
m.reject = d.reject;
for (const Rule& rule : d.rules) {
if (!m.delta.insert({{rule.state, rule.read}, rule.action}).second) {
throw std::runtime_error("hay dos transiciones para δ(" + rule.state + ", " + rule.read +
"): la máquina no es determinista");
}
}
return m;
}
inline Tm load_tm(const std::string& path) {
std::ifstream file(path);
if (!file) {
throw std::runtime_error("no se pudo abrir " + path);
}
try {
return read_tm(file);
} catch (const std::runtime_error& error) {
throw std::runtime_error(path + ": " + error.what());
}
}
// ------------------------------------------------------------
// Configuraciones
// ------------------------------------------------------------
// Una configuración: el estado, el contenido de la cinta y la posición del cabezal.
// cells guarda las celdas que la máquina ya visitó o que traía la entrada: todas las demás
// tienen el símbolo blanco. Así la cinta crece hacia la derecha solo cuando hace falta.
struct Config {
std::string state;
std::string cells;
std::size_t head = 0;
};
// La configuración inicial con la entrada w: q0 w.
inline Config initial_config(const Tm& m, const std::string& w) {
return {m.start, w, 0};
}
// El símbolo que está bajo el cabezal.
inline char scanned(const Config& c) {
return c.head < c.cells.size() ? c.cells[c.head] : BLANK;
}
inline bool halted(const Tm& m, const Config& c) {
return c.state == m.accept || c.state == m.reject;
}
// La configuración escrita como en clase, u q v: u es lo que está a la izquierda del cabezal,
// q el estado, y v empieza en la celda del cabezal y llega hasta el último símbolo no blanco.
// Si a partir del cabezal todo es blanco, v es un solo blanco.
inline std::string to_string(const Config& c) {
std::size_t end = c.cells.size();
while (end > 0 && c.cells[end - 1] == BLANK) {
end--;
}
if (end < c.head + 1) {
end = c.head + 1;
}
std::string all = c.cells;
all.resize(end, BLANK);
std::string u = all.substr(0, c.head);
std::string v = all.substr(c.head);
return (u.empty() ? "" : u + " ") + c.state + " " + v;
}
// ------------------------------------------------------------
// Ejecutar
// ------------------------------------------------------------
// δ(q, a). Si el archivo no trae esa línea, la máquina pasa a q_reject: se toma como si la
// línea fuera "q a -> q_reject a R".
inline Action action_for(const Tm& m, const std::string& q, char a) {
auto it = m.delta.find({q, a});
if (it == m.delta.end()) {
return {m.reject, a, 'R'};
}
return it->second;
}
// Aplica una acción a una configuración: escribe, cambia de estado y mueve el cabezal.
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
}
}
// Un paso: de una configuración a la siguiente. No se llama con una configuración final.
inline void step(const Tm& m, Config& c) {
apply(c, action_for(m, c.state, scanned(c)));
}
enum class Outcome { Accept, Reject, Limit };
struct Run {
Outcome outcome = Outcome::Limit;
long long steps = 0; // pasos que dio
Config last; // la configuración en la que quedó
};
// Ejecuta M con la entrada w, a lo sumo limit pasos. Si después de limit pasos no llegó a
// q_accept ni a q_reject, el resultado es Limit: no se sabe si se detendría más adelante.
inline Run run(const Tm& m, const std::string& w, long long limit) {
Run result;
result.last = initial_config(m, w);
while (!halted(m, result.last) && result.steps < limit) {
step(m, result.last);
result.steps++;
}
if (result.last.state == m.accept) {
result.outcome = Outcome::Accept;
} else if (result.last.state == m.reject) {
result.outcome = Outcome::Reject;
}
return result;
}
// La secuencia de configuraciones C0, C1, …, hasta detenerse o hasta dar limit pasos.
inline std::vector<Config> trace(const Tm& m, const std::string& w, long long limit) {
std::vector<Config> sequence = {initial_config(m, w)};
while (!halted(m, sequence.back()) && static_cast<long long>(sequence.size()) <= limit) {
Config next = sequence.back();
step(m, next);
sequence.push_back(next);
}
return sequence;
}
// ------------------------------------------------------------
// Cadenas en orden
// ------------------------------------------------------------
// Todas las cadenas sobre el alfabeto con longitud a lo sumo max_len, primero las más cortas
// y, entre las de igual longitud, en el orden del alfabeto. Es la función de la semana 1.
inline std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_len) {
std::vector<std::string> result = {""};
std::size_t first = 0; // dónde empiezan las cadenas de la longitud anterior
for (std::size_t len = 1; len <= max_len; len++) {
std::size_t last = result.size();
for (std::size_t i = first; i < last; i++) {
for (char a : alphabet) {
result.push_back(result[i] + a);
}
}
first = last;
}
return result;
}
#endif# Decide { a^n b^n c^n : n >= 0 }, que no es libre de contexto.
states: q0 q1 q2 q3 q4 q5 q_accept q_reject
alphabet: a b c
tape: a b c X Y Z _
start: q0
accept: q_accept
reject: q_reject
delta:
# q0: tachar la primera a que queda
q0 a -> q1 X R
q0 Y -> q4 Y R
q0 _ -> q_accept _ R
# q1: buscar la primera b
q1 a -> q1 a R
q1 Y -> q1 Y R
q1 b -> q2 Y R
# q2: buscar la primera c
q2 b -> q2 b R
q2 Z -> q2 Z R
q2 c -> q3 Z L
# q3: volver hasta la última X
q3 a -> q3 a L
q3 b -> q3 b L
q3 Y -> q3 Y L
q3 Z -> q3 Z L
q3 X -> q0 X R
# q4 y q5: ya no hay a; solo deben quedar Y y después Z
q4 Y -> q4 Y R
q4 Z -> q5 Z R
q5 Z -> q5 Z R
q5 _ -> q_accept _ R# 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# Decide las cadenas binarias que tienen algún 1: al llegar al primer blanco, rechaza.
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 _ -> q_reject _ R# Para ver qué pasa en el borde izquierdo: la máquina va hasta el final de la entrada y
# vuelve moviéndose a la izquierda sin parar. En la primera celda, L la deja donde está.
# No se detiene con ninguna entrada.
states: q0 q1 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q0 0 R
q0 1 -> q0 1 R
q0 _ -> q1 _ L
q1 0 -> q1 0 L
q1 1 -> q1 1 L
q1 _ -> q1 _ L# 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# Decide { w=w : w es una cadena sobre {0, 1} }: dos copias de la misma cadena con un
# separador en medio. En clase el separador se escribe con el signo de número; en estos
# archivos ese signo empieza un comentario y no puede ser un símbolo, así que aquí es =.
states: q0 q1 q2 q3 q4 q5 q6 q7 q_accept q_reject
alphabet: 0 1 =
tape: 0 1 = X _
start: q0
accept: q_accept
reject: q_reject
delta:
# q0: tomar el primer símbolo sin tachar de la izquierda
q0 0 -> q1 X R
q0 1 -> q2 X R
q0 = -> q7 = R
# q1: recordando un 0, ir hasta el separador
q1 0 -> q1 0 R
q1 1 -> q1 1 R
q1 = -> q3 = R
# q2: recordando un 1, ir hasta el separador
q2 0 -> q2 0 R
q2 1 -> q2 1 R
q2 = -> q4 = R
# q3 y q4: saltar lo tachado de la derecha y comparar
q3 X -> q3 X R
q3 0 -> q5 X L
q4 X -> q4 X R
q4 1 -> q5 X L
# q5: volver hasta el separador
q5 X -> q5 X L
q5 = -> q6 = L
# q6: volver hasta la última X de la izquierda
q6 0 -> q6 0 L
q6 1 -> q6 1 L
q6 X -> q0 X R
# q7: la izquierda se acabó; a la derecha no debe sobrar nada
q7 X -> q7 X R
q7 _ -> q_accept _ R# 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 _ RErrores
Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.
# Error: una transición que sale de q_accept. Al entrar a q_accept o a q_reject la máquina se
# detiene, así que de esos dos estados no sale nada.
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
q_accept 0 -> q0 0 R# Error: q_accept y q_reject son el mismo estado. La definición pide que sean distintos.
states: q0 q_fin
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_fin
reject: q_fin
delta:
q0 0 -> q0 0 R
q0 1 -> q_fin 1 R# Error: la máquina escribe X, pero X no está en el alfabeto de la cinta.
states: q0 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q0 X R
q0 1 -> q_accept 1 R# Error: dos transiciones para el mismo estado y el mismo símbolo. Una máquina determinista
# tiene a lo sumo una. (Una máquina así es no determinista: la segunda mitad del capítulo.)
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 0 -> q_accept 0 R
q0 1 -> q0 1 RPruebas
Comprueban lo que afirman los apuntes; se ejecutan con make test.
// Pruebas de la sesión B sobre máquinas de varias cintas: la máquina de dos cintas decide
// { 0^n 1^n } en tiempo lineal, y la simulación con una sola cinta mantiene, paso a paso, la
// misma configuración que la máquina simulada, dentro de la cota cuadrática de los apuntes.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <random>
#include <string>
#include <vector>
#include "multitape.h"
#include "tm.h"
static bool is_zeros_ones(const std::string& w) {
std::size_t n = w.size() / 2;
return w.size() % 2 == 0 && w == std::string(n, '0') + std::string(n, '1');
}
// Ejecuta M y la simulación S a la vez y compara después de cada paso de M.
// Devuelve los pasos de S. Comprueba las cotas de los apuntes:
// - la cinta de S ocupa a lo sumo n + 2k + 1 + k·t celdas después de t pasos de M;
// - simular un paso cuesta a lo sumo (2k + 6)·L pasos de S, con L celdas en uso al terminar;
// - preparar la cinta cuesta a lo sumo 2(n + 2k + 1) pasos.
static long long check_simulation(const MultiTm& m, const std::string& w, long long limit) {
const long long k = static_cast<long long>(m.tapes);
const long long n = static_cast<long long>(w.size());
MultiConfig c = initial_config(m, w);
Simulation s = start_simulation(m, w);
assert(s.tape.head == 0);
assert(same_config(decode(m, s), c));
assert(s.setup <= 2 * (n + 2 * k + 1));
assert(s.length == (n == 0 ? 1 : n) + 2 * k);
long long t = 0;
while (!halted(m, c) && t < limit) {
long long before = s.tape.steps;
step(m, c);
simulate_step(m, s);
t++;
assert(s.rounds == t);
assert(s.tape.head == 0);
assert(same_config(decode(m, s), c));
assert(s.length <= n + 2 * k + 1 + k * t);
assert(s.tape.steps - before <= (2 * k + 6) * s.length);
}
assert(s.tape.steps <= 2 * (n + 2 * k + 1) + t * (2 * k + 6) * (n + 2 * k + 1 + k * t));
return s.tape.steps;
}
static void test_two_tapes() {
MultiTm m = two_tape_zeros_ones();
std::size_t strings = 0;
for (const std::string& w : all_strings(m.alphabet, 11)) {
MultiRun r = run_multi(m, w, 1000);
assert(r.outcome != Outcome::Limit);
assert((r.outcome == Outcome::Accept) == is_zeros_ones(w));
assert(r.steps <= static_cast<long long>(w.size()) + 3); // tiempo lineal
SimulationRun sim = run_simulation(m, w, 1000);
assert(sim.outcome == r.outcome && sim.rounds == r.steps);
assert(check_simulation(m, w, 1000) == sim.steps);
strings++;
}
std::printf(" dos cintas: %zu cadenas, la simulación coincide paso a paso\n", strings);
}
// Los números de la tabla de los apuntes.
static void test_table() {
MultiTm m = two_tape_zeros_ones();
Tm one = load_tm("machines/zeros_ones.tm");
const std::vector<std::vector<long long>> rows = {
{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}};
for (const std::vector<long long>& row : rows) {
std::string w = std::string(row[0], '0') + std::string(row[0], '1');
assert(run(one, w, 10000000).steps == row[1]);
assert(run_multi(m, w, 10000000).steps == row[2]);
assert(row[2] == 2 * row[0] + 3);
assert(run_simulation(m, w, 10000000).steps == row[3]);
}
// La simulación del ejemplo corto.
SimulationRun sim = run_simulation(m, "01", 100);
assert(sim.outcome == Outcome::Accept && sim.rounds == 5 && sim.steps == 168);
Simulation s = start_simulation(m, "01");
assert(to_string(s.tape) == "#[0]1#[_]#" && s.setup == 12);
simulate_step(m, s);
assert(to_string(s.tape) == "#[0]1#$[_]#" && s.tape.steps == 36);
simulate_step(m, s);
assert(to_string(s.tape) == "#0[1]#$0[_]#" && s.tape.steps == 64);
Simulation empty = start_simulation(m, "");
assert(to_string(empty.tape) == "#[_]#[_]#" && empty.setup == 10);
}
// Máquinas de 1, 2 y 3 cintas con transiciones al azar (semilla fija): la simulación tiene que
// coincidir con cualquier máquina, no solo con la del capítulo. Ejercita los movimientos L en
// la primera celda, los S y los corrimientos en cada cinta.
static void test_random_machines() {
std::mt19937 rng(7007);
const std::string gamma = "01_";
long long machines = 0;
for (std::size_t k = 1; k <= 3; k++) {
for (int round = 0; round < 60; round++) {
MultiTm m;
m.tapes = k;
m.states = {"p0", "p1", "p2", "q_accept", "q_reject"};
m.alphabet = {'0', '1'};
m.tape = {'0', '1', BLANK};
m.start = "p0";
m.accept = "q_accept";
m.reject = "q_reject";
std::size_t combos = 1;
for (std::size_t i = 0; i < k; i++) {
combos *= gamma.size();
}
for (std::size_t q = 0; q < 3; q++) {
for (std::size_t combo = 0; combo < combos; combo++) {
std::string read;
std::size_t rest = combo;
for (std::size_t i = 0; i < k; i++) {
read += gamma[rest % gamma.size()];
rest /= gamma.size();
}
unsigned kind = rng() % 20;
if (kind == 0) {
continue; // sin transición: va a q_reject
}
MultiAction action;
action.state = (kind == 1) ? "q_accept" : m.states[rng() % 3];
for (std::size_t i = 0; i < k; i++) {
action.write += gamma[rng() % gamma.size()];
action.move += "LRRS"[rng() % 4];
}
m.delta[{m.states[q], read}] = action;
}
}
for (const std::string& w : all_strings(m.alphabet, 4)) {
check_simulation(m, w, 60);
}
machines++;
}
}
std::printf(" %lld máquinas al azar de 1, 2 y 3 cintas: la simulación coincide paso a paso\n", machines);
}
int main() {
std::printf("test_multitape:\n");
test_two_tapes();
test_table();
test_random_machines();
std::printf("test_multitape: ok\n");
}// Pruebas de lo que los apuntes afirman sobre las máquinas de una cinta (sesión A).
// Cada máquina de machines/ se compara con una función de C++ que decide el mismo lenguaje
// mirando la cadena completa, sobre todas las cadenas hasta cierta longitud. Para las que
// deciden, se comprueba además que el límite de pasos de la prueba no se alcanza nunca.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
#include "tm.h"
static bool is_zeros_ones(const std::string& w) {
std::size_t n = w.size() / 2;
return w.size() % 2 == 0 && w == std::string(n, '0') + std::string(n, '1');
}
// w = x=x, con x sobre {0, 1}.
static bool is_w_sep_w(const std::string& w) {
std::size_t n = w.size() / 2;
return w.size() % 2 == 1 && w[n] == '=' && w.substr(0, n) == w.substr(n + 1) &&
w.find('=') == n;
}
static bool is_anbncn(const std::string& w) {
std::size_t n = w.size() / 3;
return w.size() % 3 == 0 && w == std::string(n, 'a') + std::string(n, 'b') + std::string(n, 'c');
}
static bool has_one(const std::string& w) {
return w.find('1') != std::string::npos;
}
struct Checked {
std::size_t strings = 0;
long long max_steps = 0;
};
// La máquina decide el lenguaje: con cada cadena se detiene antes del límite y responde bien.
static Checked check_decider(const std::string& path, std::size_t max_len,
const std::function<bool(const std::string&)>& in_language,
const std::function<long long(std::size_t)>& bound) {
const long long limit = 100000;
Tm m = load_tm(path);
Checked checked;
for (const std::string& w : all_strings(m.alphabet, max_len)) {
Run r = run(m, w, limit);
assert(r.outcome != Outcome::Limit);
assert((r.outcome == Outcome::Accept) == in_language(w));
// La cota de pasos que dan los apuntes, en función de la longitud de la entrada.
assert(r.steps <= bound(w.size()));
checked.max_steps = std::max(checked.max_steps, r.steps);
checked.strings++;
}
assert(checked.max_steps < limit);
return checked;
}
static void test_deciders() {
// Las tres máquinas que tachan: a lo sumo n/2 vueltas de 2n − 1 pasos y un tramo final de n + 2.
auto quadratic = [](std::size_t n) { return static_cast<long long>(n * n + n + 2); };
Checked a = check_decider("machines/zeros_ones.tm", 13, is_zeros_ones, quadratic);
Checked b = check_decider("machines/w_sep_w.tm", 9, is_w_sep_w, quadratic);
Checked c = check_decider("machines/anbncn.tm", 9, is_anbncn, quadratic);
Checked d = check_decider("machines/has_one.tm", 13, has_one,
[](std::size_t n) { return static_cast<long long>(n + 1); });
std::printf(" zeros_ones: %zu cadenas, a lo sumo %lld pasos\n", a.strings, a.max_steps);
std::printf(" w_sep_w: %zu cadenas, a lo sumo %lld pasos\n", b.strings, b.max_steps);
std::printf(" anbncn: %zu cadenas, a lo sumo %lld pasos\n", c.strings, c.max_steps);
std::printf(" has_one: %zu cadenas, a lo sumo %lld pasos\n", d.strings, d.max_steps);
}
// Las cuentas exactas de los apuntes.
static void test_step_counts() {
Tm zeros = load_tm("machines/zeros_ones.tm");
for (long long n = 0; n <= 60; n++) {
Run r = run(zeros, std::string(n, '0') + std::string(n, '1'), 100000);
assert(r.outcome == Outcome::Accept);
assert(r.steps == 2 * n * n + 2 * n + 1);
}
Tm abc = load_tm("machines/anbncn.tm");
for (long long n = 1; n <= 40; n++) {
Run r = run(abc, std::string(n, 'a') + std::string(n, 'b') + std::string(n, 'c'), 100000);
assert(r.outcome == Outcome::Accept);
assert(r.steps == 4 * n * n + 3 * n + 1);
}
Tm copy = load_tm("machines/w_sep_w.tm");
for (long long n = 0; n <= 40; n++) {
std::string x;
for (long long i = 0; i < n; i++) {
x += (i % 3 == 0) ? '1' : '0';
}
Run r = run(copy, x + "=" + x, 100000);
assert(r.outcome == Outcome::Accept);
assert(r.steps == 2 * n * n + 4 * n + 2);
}
}
static std::vector<std::string> trace_text(const Tm& m, const std::string& w, long long limit) {
std::vector<std::string> lines;
for (const Config& c : trace(m, w, limit)) {
lines.push_back(to_string(c));
}
return lines;
}
// Las secuencias de configuraciones que los apuntes muestran.
static void test_traces() {
Tm zeros = load_tm("machines/zeros_ones.tm");
assert(trace_text(zeros, "0011", 100) ==
(std::vector<std::string>{"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 _"}));
assert(trace_text(zeros, "", 100) == (std::vector<std::string>{"q0 _", "_ q_accept _"}));
// Un par sin transición: δ(q3, 0) no está escrita, y la máquina pasa a q_reject.
assert(zeros.delta.count({"q3", '0'}) == 0);
assert(trace_text(zeros, "010", 100) ==
(std::vector<std::string>{"q0 010", "X q1 10", "q2 XY0", "X q0 Y0", "XY q3 0", "XY0 q_reject _"}));
Tm copy = load_tm("machines/w_sep_w.tm");
std::vector<std::string> lines = trace_text(copy, "01=01", 100);
assert(lines.size() == 19);
assert(lines[3] == "X1= q3 01" && lines[4] == "X1 q5 =X1" && lines[7] == "X q0 1=X1");
assert(lines[14] == "XX q0 =XX" && lines[18] == "XX=XX_ q_accept _");
assert(trace_text(copy, "=", 100) == (std::vector<std::string>{"q0 =", "= q7 _", "=_ q_accept _"}));
assert(run(copy, "", 100).outcome == Outcome::Reject);
assert(run(copy, "01=0", 100).outcome == Outcome::Reject);
assert(run(copy, "01=011", 100).outcome == Outcome::Reject);
assert(run(copy, "01=01=01", 100).outcome == Outcome::Reject);
Tm abc = load_tm("machines/anbncn.tm");
assert(trace_text(abc, "abc", 100) ==
(std::vector<std::string>{"q0 abc", "X q1 bc", "XY q2 c", "X q3 YZ", "q3 XYZ", "X q0 YZ", "XY q4 Z",
"XYZ q5 _", "XYZ_ q_accept _"}));
assert(run(abc, "aabbcc", 1000).steps == 23);
assert(run(abc, "aabbc", 1000).outcome == Outcome::Reject);
assert(run(abc, "abcabc", 1000).outcome == Outcome::Reject);
}
// La máquina que reconoce y no decide: acepta exactamente las cadenas con algún 1, y con las
// demás no se detiene.
static void test_recognizer_that_loops() {
Tm loops = load_tm("machines/has_one_loops.tm");
for (const std::string& w : all_strings(loops.alphabet, 12)) {
Run r = run(loops, w, 1000);
if (has_one(w)) {
assert(r.outcome == Outcome::Accept);
assert(r.steps == static_cast<long long>(w.find('1')) + 1);
} else {
// Después de t pasos, la configuración es 0^n seguido de blancos, con q0 en la celda t.
assert(r.outcome == Outcome::Limit);
assert(r.last.state == "q0" && r.last.head == 1000);
}
}
// Con la entrada 000 pasa de un millón de pasos sin detenerse.
const long long million = 1000000;
Run r = run(loops, "000", million);
assert(r.outcome == Outcome::Limit && r.steps == million);
assert(r.last.state == "q0" && r.last.head == static_cast<std::size_t>(million));
assert(r.last.cells.substr(0, 3) == "000");
assert(r.last.cells.find_first_not_of(BLANK, 3) == std::string::npos);
assert(trace_text(loops, "00", 5) ==
(std::vector<std::string>{"q0 00", "0 q0 0", "00 q0 _", "00_ q0 _", "00__ q0 _", "00___ q0 _"}));
}
// El borde izquierdo de la cinta: un movimiento L en la primera celda no mueve el cabezal.
static void test_left_end() {
Tm m = load_tm("machines/left_end.tm");
std::vector<std::string> lines = trace_text(m, "01", 12);
assert(lines.size() == 13);
assert(lines[2] == "01 q0 _" && lines[3] == "0 q1 1" && lines[4] == "q1 01");
for (std::size_t i = 4; i < lines.size(); i++) {
assert(lines[i] == "q1 01");
}
for (const std::string& w : all_strings(m.alphabet, 6)) {
Run r = run(m, w, 500);
assert(r.outcome == Outcome::Limit && r.last.head == 0 && r.last.state == "q1");
}
}
static void test_to_string() {
assert(to_string({"q0", "", 0}) == "q0 _");
assert(to_string({"q1", "ab", 0}) == "q1 ab");
assert(to_string({"q1", "ab", 2}) == "ab q1 _");
assert(to_string({"q1", "ab", 4}) == "ab__ q1 _");
assert(to_string({"q1", "a_b__", 1}) == "a q1 _b");
}
static bool fails_to_load(const std::string& path) {
try {
load_tm(path);
} catch (const std::runtime_error&) {
return true;
}
return false;
}
static void test_errors() {
assert(fails_to_load("errors/two_transitions.tm"));
assert(fails_to_load("errors/moves_after_halting.tm"));
assert(fails_to_load("errors/symbol_not_in_tape.tm"));
assert(fails_to_load("errors/same_accept_reject.tm"));
assert(fails_to_load("machines/nondet_branch.tm")); // no determinista: se lee con ntm.h
assert(fails_to_load("machines/no_such_file.tm"));
std::istringstream blank_in_alphabet(
"states: q0 a r\nalphabet: 0 _\ntape: 0 _\nstart: q0\naccept: a\nreject: r\ndelta:\n");
bool failed = false;
try {
read_tm(blank_in_alphabet);
} catch (const std::runtime_error&) {
failed = true;
}
assert(failed);
}
int main() {
std::printf("test_tm:\n");
test_deciders();
test_step_counts();
test_traces();
test_recognizer_that_loops();
test_left_end();
test_to_string();
test_errors();
std::printf("test_tm: ok\n");
}// Pruebas de la sesión B sobre el no determinismo y los enumeradores.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <set>
#include <string>
#include <vector>
#include "ntm.h"
#include "tm.h"
static bool has_one(const std::string& w) {
return w.find('1') != std::string::npos;
}
static bool is_zeros_ones(const std::string& w) {
std::size_t n = w.size() / 2;
return w.size() % 2 == 0 && w == std::string(n, '0') + std::string(n, '1');
}
// La máquina no determinista del capítulo: el recorrido por niveles acepta exactamente las
// cadenas con algún 1, en el nivel que dicen los apuntes. Seguir siempre la primera opción
// no termina si la cadena empieza con 0.
static void test_breadth_first() {
Ntm m = load_ntm("machines/nondet_branch.tm");
assert(m.delta.at({"q0", '0'}).size() == 2);
for (const std::string& w : all_strings(m.alphabet, 9)) {
Search search = breadth_first(m, w, 40);
if (has_one(w)) {
assert(search.outcome == Outcome::Accept);
assert(search.depth == static_cast<long long>(w.find('1')) + 1);
} else if (w.empty()) {
assert(search.outcome == Outcome::Reject); // una sola rama, que se detiene
} else {
assert(search.outcome == Outcome::Limit); // hay una rama que no se detiene
}
Run first = first_branch(m, w, 5000);
if (!w.empty() && w[0] == '0') {
assert(first.outcome == Outcome::Limit && first.last.state == "q1");
}
}
// El ejemplo de los apuntes.
Search search = breadth_first(m, "001", 8);
assert(search.outcome == Outcome::Accept && search.depth == 3 && search.visited == 9);
assert(first_branch(m, "001", 1000000).outcome == Outcome::Limit);
assert(breadth_first(m, "00", 5).outcome == Outcome::Limit);
}
// Una máquina determinista es un caso particular: el árbol es un solo camino, y el recorrido
// por niveles responde lo mismo que la ejecución, en el mismo número de pasos.
static void test_deterministic_as_ntm() {
Ntm n = load_ntm("machines/zeros_ones.tm");
Tm d = load_tm("machines/zeros_ones.tm");
for (const std::string& w : all_strings(d.alphabet, 10)) {
Search search = breadth_first(n, w, 1000);
Run r = run(d, w, 1000);
assert(search.outcome == r.outcome);
assert((search.outcome == Outcome::Accept) == is_zeros_ones(w));
assert(search.depth == r.steps);
}
}
// El enumerador que se construye a partir de una máquina que reconoce: en la ronda i, i pasos
// con cada una de s1, …, si. Se comprueba con la máquina que no se detiene con las cadenas sin
// unos: aun así, toda cadena del lenguaje sale impresa, y ninguna que no esté.
static void test_enumerator() {
Tm m = load_tm("machines/has_one_loops.tm");
std::vector<std::string> strings = all_strings(m.alphabet, 6); // s1, …, s127
const std::size_t rounds = strings.size();
std::set<std::string> printed;
std::vector<std::size_t> first_round(strings.size(), 0);
for (std::size_t i = 1; i <= rounds; i++) {
for (std::size_t j = 0; j < i; j++) {
if (run(m, strings[j], static_cast<long long>(i)).outcome == Outcome::Accept) {
printed.insert(strings[j]);
if (first_round[j] == 0) {
first_round[j] = i;
}
}
}
if (i == 8) {
assert(printed == (std::set<std::string>{"1", "01", "10", "11"})); // la salida de los apuntes
}
}
for (std::size_t j = 0; j < strings.size(); j++) {
const std::string& s = strings[j];
assert((printed.count(s) > 0) == has_one(s));
if (has_one(s)) {
// s_j sale por primera vez en la ronda max(j, pasos que tarda M en aceptarla).
std::size_t steps = s.find('1') + 1;
assert(first_round[j] == std::max(j + 1, steps));
}
}
// Ejecutar M con s1, después con s2… no sirve: con s1 = ε no se detiene.
assert(run(m, strings[0], 1000000).outcome == Outcome::Limit);
}
int main() {
test_breadth_first();
test_deterministic_as_ntm();
test_enumerator();
std::printf("test_variants: ok\n");
}Laboratorio
Archivos de partida del laboratorio de la semana.
TIEMPO = 2
include ../../../lab.mk# 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.// Un simulador de máquinas de Turing. Lee la descripción de una máquina, un límite de pasos y
// una lista de cadenas, e imprime por cada cadena si la máquina la acepta, la rechaza o no se
// detuvo dentro del límite.
#include <iostream>
#include <string>
#include <vector>
// El resultado de δ(q, a) = (r, b, D).
struct Action {
int state = 0; // r, como posición en states
char write = '_'; // b
char move = 'R'; // D: 'L' o 'R'
};
// Los siete componentes de M = (Q, Σ, Γ, δ, q0, q_accept, q_reject), con los nombres del
// formato. Los tipos son una propuesta: cada estado se guarda por su posición en la lista,
// para que dar un paso no dependa de buscar un nombre. Pueden cambiarlos.
struct Tm {
std::vector<std::string> states; // Q: los nombres, en el orden de la entrada
std::vector<char> alphabet; // Σ
std::vector<char> tape; // Γ
std::vector<std::vector<Action>> delta; // δ: una fila por estado; ustedes deciden las columnas
int start = 0; // q0
int accept = 0; // q_accept
int reject = 0; // q_reject
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Tm m;
std::string line;
// Por hacer: leer la descripción línea por línea con std::getline, hasta la línea limit:.
// Después viene la línea strings: y las cadenas (una línea vacía es ε). Por cada cadena,
// simular a lo sumo el límite de pasos y responder.
while (std::getline(std::cin, line)) {
}
// Este esqueleto no imprime nada, así que el juez da WA en todos los casos.
return static_cast<int>(m.states.size());
}Compilación
Cómo se compilan y ejecutan los ejemplos.
# Semana 7: máquinas de Turing, sus variantes y la tesis de Church-Turing.
# Se usa dentro del entorno del curso.
#
# make compila los programas de la clase en build/
# make test corre las pruebas de los ejemplos, con sanitizers
# make clean borra lo generado
#
# Las pruebas leen las máquinas de machines/ y de errors/, así que se corren desde esta carpeta.
# El laboratorio está en lab/tm_sim y tiene su propio Makefile: estas reglas no lo tocan.
CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BUILD = build
PROGRAMS = show_tm run_tm multitape_demo ntm_demo enumerate
TESTS = test_tm test_multitape test_variants
HEADERS = tm.h ntm.h multitape.h
.PHONY: all test clean
all: $(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%)
$(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
$(CXX) $(CXXFLAGS) $< -o $@
$(BUILD):
mkdir -p $@
test: $(TESTS:%=$(BUILD)/%) $(PROGRAMS:%=$(BUILD)/%)
@for t in $(TESTS); do $(BUILD)/$$t || exit 1; done
@echo "Todas las pruebas pasaron."
clean:
rm -rf $(BUILD)