Semana 10 — Reducciones

Objetivos

  • Demostrar que un problema es indecidible con una reducción, en la dirección correcta.
  • Definir la reducción por función y usarla también para lenguajes no reconocibles.
  • Aplicar el teorema de Rice, comprobando sus dos condiciones.
  • Explicar cómo las historias de cómputo llevan la indecidibilidad a problemas sin máquinas: fichas y gramáticas.

Sesión A — Reducciones · Teorema de Rice

Lectura: Apuntes, semana 10.

Apoyo: Sipser, sec. 5.1 (Undecidable Problems from Language Theory) y 5.3 (Mapping Reducibility). Erickson, Models of Computation, nota 7 (Undecidability).

Temas:

  • La idea, que ya conocen de Algoritmos: si con una solución de BB se resuelve AA, y AA no tiene solución, BB tampoco.
  • La dirección: para demostrar que BB es indecidible se reduce desde un problema indecidible conocido hacia BB.
  • HALTTM\mathrm{HALT}_{\mathrm{TM}} es indecidible, reduciendo desde ATMA_{\mathrm{TM}}.
  • ETME_{\mathrm{TM}}: construir, a partir de ⟨M,w⟩\langle M, w \rangle, una máquina que solo acepta algo si MM acepta ww. La técnica de fijar la entrada dentro de la máquina.
  • REGULARTM\mathrm{REGULAR}_{\mathrm{TM}} y EQTM\mathrm{EQ}_{\mathrm{TM}} con la misma técnica.
  • Reducción por función: A≤mBA \leq_m B con una función computable ff tal que w∈Aw \in A si y solo si f(w)∈Bf(w) \in B. Qué conserva: decidible, reconocible y sus negaciones.
  • EQTM\mathrm{EQ}_{\mathrm{TM}} no es reconocible, y su complemento tampoco.
  • Teorema de Rice: toda propiedad no trivial del lenguaje de una máquina es indecidible. Demostración, y ejemplos de uso.
  • Lo que Rice no dice: las propiedades de la máquina misma (“tiene 5 estados”, “se detiene en 100 pasos”) sí pueden ser decidibles.
  • Error común: reducir en la dirección contraria. Reducir BB a ATMA_{\mathrm{TM}} solo muestra que BB no es más difícil que ATMA_{\mathrm{TM}}.

Sesión B — Historias de cómputo · Problema de correspondencia de Post · Problemas indecidibles sobre gramáticas

Lectura: Apuntes, semana 10.

Apoyo: Sipser, sec. 5.1 (la parte de computation histories) y 5.2 (A Simple Undecidable Problem).

Temas:

  • Problemas indecidibles que no hablan de máquinas. Hace falta un puente.
  • Historia de cómputo: la secuencia de configuraciones C1#C2#⋯#CkC_1 \mathtt{\#} C_2 \mathtt{\#} \cdots \mathtt{\#} C_k de una máquina que acepta. Comprobar que una historia es válida es fácil y local.
  • El problema de correspondencia de Post: fichas con una cadena arriba y otra abajo. Ejemplos con y sin solución.
  • PCP es indecidible: las fichas obligan a escribir arriba y abajo una historia de cómputo, con la parte de abajo una configuración adelantada. Se muestra la construcción con un ejemplo y se enumeran los tipos de ficha.
  • PCP es reconocible: buscar por longitud creciente encuentra la solución si existe.
  • ALLCFG\mathrm{ALL}_{\mathrm{CFG}}, ¿una gramática genera todas las cadenas?: es indecidible, porque una gramática puede generar todo lo que no es una historia de cómputo válida.
  • Consecuencias: EQCFG\mathrm{EQ}_{\mathrm{CFG}} es indecidible, y también decidir si una gramática es ambigua. La deuda de la semana 9.
  • El contraste con los autómatas finitos, donde todo eso era decidible.
  • Error común: creer que un problema es decidible porque todas las instancias que uno probó tenían respuesta.

Laboratorio — Buscar una solución de PCP

  1. Leer un conjunto de fichas y buscar una solución de a lo sumo NN fichas, con el NN del enunciado.
  2. Buscar en anchura sobre el exceso entre la cadena de arriba y la de abajo, que es todo lo que hay que recordar.
  3. Evitar repetir estados ya visitados.
  4. Responder con la secuencia de fichas, o con sin solución hasta N; nunca con “no tiene solución”.
  5. Explicar en dos líneas, en un archivo respuestas.md, por qué su programa reconoce PCP y no lo decide.

Preguntas de repaso

  1. Demuestren que { ⟨M⟩:M acepta la cadena vacıˊa }\{\, \langle M \rangle : M \text{ acepta la cadena vacía} \,\} es indecidible con una reducción. Después, con Rice.
  2. ¿Cuáles de estas propiedades caen bajo el teorema de Rice? ”L(M)L(M) es finito”, ”MM tiene un estado inútil”, ”L(M)L(M) contiene a 0”, ”MM se detiene con toda entrada en menos de 10 pasos”.
  3. Si A≤mBA \leq_m B y BB es reconocible, ¿qué se sabe de AA? ¿Y si AA no es reconocible, qué se sabe de BB?
  4. Encuentren una solución de un PCP de cuatro fichas, o argumenten por qué no existe.
  5. ¿Por qué comprobar que una historia de cómputo es válida es “local”? ¿Qué parte de dos configuraciones seguidas puede cambiar?

Código de la semana

Compilar y probar dentro del contenedor del curso con make y make test.

Ejemplos (23)Errores (1)Pruebas (4)Laboratorio (4)Compilación (1)

Ejemplos

Los programas que usan los apuntes y la clase.

check_history.cppDescargar check_history.cpp
// Comprueba si una cadena es una historia de cómputo de aceptación de M con w.
//   check_history maquina.tm w "C1 # C2 # … # Ck"
// Los símbolos de la historia van separados por espacios. La cadena vacía se escribe eps.
#include <exception>
#include <iostream>
#include <string>

#include "tm.h"

int main(int argc, char** argv) {
    if (argc != 4) {
        std::cerr << "uso: check_history maquina.tm w \"C1 # C2 # … # Ck\"\n";
        return 2;
    }
    try {
        const Tm m = load_tm(argv[1]);
        const std::string w = std::string(argv[2]) == "eps" ? "" : argv[2];
        const std::string problem = check_history(m, w, split(argv[3]));
        if (problem.empty()) {
            std::cout << "es una historia de aceptación\n";
            return 0;
        }
        std::cout << "no es una historia de aceptación\n  " << problem << "\n";
        return 1;
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << "\n";
        return 2;
    }
}
fix_input.cppDescargar fix_input.cpp
// Escribe, en formato .tm, la máquina M_w que tiene la entrada w fijada dentro.
//   fix_input maquina.tm w        (la cadena vacía se escribe eps)
#include <exception>
#include <iostream>
#include <string>

#include "fix_input.h"

int main(int argc, char** argv) {
    if (argc != 3) {
        std::cerr << "uso: fix_input maquina.tm w\n";
        return 2;
    }
    try {
        const Tm m = load_tm(argv[1]);
        const std::string w = std::string(argv[2]) == "eps" ? "" : argv[2];
        std::cout << "# M_w para M = " << argv[1] << " y w = " << argv[2] << ".\n";
        std::cout << "# Con la entrada x: si x no es w, rechaza; si lo es, corre M con w.\n";
        write_tm(std::cout, fix_input(m, w));
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << "\n";
        return 2;
    }
    return 0;
}
fix_input.hDescargar fix_input.h
// La técnica de fijar la entrada dentro de la máquina: de M y w se construye M_w, que con su
// entrada x primero comprueba que x = w y después corre M con w.
//   L(M_w) = {w} si M acepta w, y L(M_w) = ∅ si no.
// Es la función computable de la reducción de A_TM al complemento de E_TM.
#pragma once

#include <stdexcept>
#include <string>

#include "tm.h"

inline Tm fix_input(const Tm& m, const std::string& w) {
    const char mark = '@';   // marca la primera celda mientras se compara
    if (has_symbol(m.tape, mark)) throw std::runtime_error("la cinta de M no puede usar el símbolo @");
    initial_configuration(m, w);   // comprueba que w usa el alfabeto de entrada
    const int n = static_cast<int>(w.size());

    Tm result;
    result.alphabet = m.alphabet;
    result.tape = m.tape;
    result.tape.push_back(mark);
    // Los estados de M pasan con el prefijo m. para que no choquen con los nuevos.
    auto old = [](const std::string& q) { return "m." + q; };
    auto compare = [](int i) { return "c" + std::to_string(i); };
    for (int i = 0; i <= n; ++i) result.states.push_back(compare(i));
    result.states.push_back("back");
    for (const std::string& q : m.states) result.states.push_back(old(q));
    result.start = compare(0);
    result.accept = old(m.accept);
    result.reject = old(m.reject);

    if (n == 0) {
        // w = ε: la entrada debe ser vacía. L en la primera celda deja el cabezal en su sitio.
        result.delta[{compare(0), '_'}] = Transition{old(m.start), '_', 'L'};
    } else {
        // c_i: los primeros i símbolos de x coinciden con los de w. El primero se cambia por la marca.
        result.delta[{compare(0), w[0]}] = Transition{compare(1), mark, 'R'};
        for (int i = 1; i < n; ++i) result.delta[{compare(i), w[i]}] = Transition{compare(i + 1), w[i], 'R'};
        // c_n con un blanco: x = w. Volver a la primera celda, restaurar su símbolo y empezar M.
        result.delta[{compare(n), '_'}] = Transition{"back", '_', 'L'};
        for (char a : m.alphabet) result.delta[{"back", a}] = Transition{"back", a, 'L'};
        result.delta[{"back", mark}] = Transition{old(m.start), w[0], 'L'};
    }
    // Cualquier otro caso de la comparación no tiene transición: va a reject.
    for (const auto& [key, t] : m.delta) {
        result.delta[{old(key.first), key.second}] = Transition{old(t.next), t.write, t.move};
    }
    return result;
}
history.cppDescargar history.cpp
// Escribe la historia de cómputo de una máquina de Turing con una entrada.
//   history maquina.tm w [--alterna] [--pasos N]
// La cadena vacía se escribe eps. Con --alterna, las configuraciones pares van al revés.
#include <cstdlib>
#include <exception>
#include <iostream>
#include <string>

#include "tm.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: history maquina.tm w [--alterna] [--pasos N]\n";
        return 2;
    }
    try {
        const Tm m = load_tm(argv[1]);
        const std::string w = std::string(argv[2]) == "eps" ? "" : argv[2];
        bool alternate = false;
        long max_steps = 10000;
        for (int i = 3; i < argc; ++i) {
            const std::string option = argv[i];
            if (option == "--alterna") alternate = true;
            else if (option == "--pasos" && i + 1 < argc) max_steps = std::atol(argv[++i]);
        }
        const Run run = run_tm(m, w, max_steps);
        for (std::size_t i = 0; i < run.configurations.size() && i < 40; ++i) {
            std::cout << "C" << i + 1 << (i + 1 < 10 ? "   " : "  ") << join(tokens_of(run.configurations[i])) << "\n";
        }
        if (run.configurations.size() > 40) std::cout << "…\n";
        if (!run.halted) {
            std::cout << "sin detenerse después de " << run.steps << " pasos: no hay historia que mostrar\n";
            return 1;
        }
        if (!run.accepted) {
            std::cout << "rechaza después de " << run.steps << " pasos: no hay historia de aceptación\n";
            return 1;
        }
        std::cout << "acepta después de " << run.steps << (run.steps == 1 ? " paso\n" : " pasos\n");
        std::cout << "historia: " << join(history_tokens(run.configurations, alternate)) << "\n";
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << "\n";
        return 2;
    }
    return 0;
}
pcp_check.cppDescargar pcp_check.cpp
// Comprueba si una secuencia de fichas es una solución de una instancia de PCP.
//   pcp_check instancia.pcp i1 i2 ... ik      (las fichas se numeran desde 1)
// Muestra, ficha por ficha, lo que se lee arriba y abajo.
#include <cstdlib>
#include <exception>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

#include "pcp.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: pcp_check instancia.pcp i1 i2 ... ik\n";
        return 2;
    }
    try {
        std::ifstream file(argv[1]);
        if (!file) throw std::runtime_error(std::string("no se pudo abrir ") + argv[1]);
        const std::vector<Domino> dominoes = read_pcp(file);
        std::vector<int> sequence;
        for (int i = 2; i < argc; ++i) {
            const int index = std::atoi(argv[i]);
            if (index < 1 || index > static_cast<int>(dominoes.size())) {
                throw std::runtime_error(std::string("no existe la ficha ") + argv[i]);
            }
            sequence.push_back(index - 1);
        }
        std::string top_pieces;
        std::string bottom_pieces;
        for (int i : sequence) {
            top_pieces += " " + dominoes[i].top;
            bottom_pieces += " " + dominoes[i].bottom;
        }
        const std::string top = concatenate(dominoes, sequence, true);
        const std::string bottom = concatenate(dominoes, sequence, false);
        std::cout << "arriba:" << top_pieces << "  =  " << top << "\n";
        std::cout << "abajo: " << bottom_pieces << "  =  " << bottom << "\n";
        if (is_solution(dominoes, sequence)) {
            std::cout << "es una solución (" << sequence.size() << " fichas, " << top.size() << " símbolos)\n";
            return 0;
        }
        std::size_t common = 0;
        while (common < top.size() && common < bottom.size() && top[common] == bottom[common]) ++common;
        if (common == top.size() || common == bottom.size()) {
            const bool top_ahead = top.size() > bottom.size();
            std::cout << "no es una solución: " << (top_ahead ? "arriba" : "abajo") << " sobra "
                      << (top_ahead ? top.substr(common) : bottom.substr(common)) << "\n";
        } else {
            std::cout << "no es una solución: las cadenas difieren en la posición " << common + 1 << "\n";
        }
        return 1;
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << "\n";
        return 2;
    }
}
pcp_meet.cppDescargar pcp_meet.cpp
// Busca una solución de PCP desde los dos extremos: con a lo sumo D fichas desde el principio
// y a lo sumo D desde el final.
//   pcp_meet instancia.pcp D
// Si existe una solución de a lo sumo 2D fichas, encuentra una de las más cortas.
#include <cstdlib>
#include <exception>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

#include "pcp.h"

int main(int argc, char** argv) {
    if (argc != 3) {
        std::cerr << "uso: pcp_meet instancia.pcp D\n";
        return 2;
    }
    try {
        std::ifstream file(argv[1]);
        if (!file) throw std::runtime_error(std::string("no se pudo abrir ") + argv[1]);
        const std::vector<Domino> dominoes = read_pcp(file);
        const int half = std::atoi(argv[2]);
        std::cout << dominoes.size() << " fichas, hasta " << half << " desde cada extremo\n";
        const PcpResult result = solve_pcp_two_ends(dominoes, half);
        if (result.found) {
            std::cout << "solución con " << result.sequence.size() << (result.sequence.size() == 1 ? " ficha:" : " fichas:");
            for (int i : result.sequence) std::cout << ' ' << i + 1;
            std::cout << "\n" << (is_solution(dominoes, result.sequence) ? "comprobada" : "ERROR: no es una solución")
                      << ": arriba y abajo se leen " << concatenate(dominoes, result.sequence, true).size() << " símbolos\n";
        } else {
            std::cout << "sin solución hasta " << 2 * half << "\n";
        }
        std::cout << "excesos visitados: " << result.visited << "\n";
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << "\n";
        return 1;
    }
    return 0;
}
pcp_solve.cppDescargar pcp_solve.cpp
// Busca una solución de una instancia de PCP con a lo sumo N fichas.
//   pcp_solve instancia.pcp N [--primera]
// Con --primera, la solución debe empezar con la ficha 1 (el PCP modificado).
#include <cstdlib>
#include <exception>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

#include "pcp.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: pcp_solve instancia.pcp N [--primera]\n";
        return 2;
    }
    try {
        std::ifstream file(argv[1]);
        if (!file) throw std::runtime_error(std::string("no se pudo abrir ") + argv[1]);
        const std::vector<Domino> dominoes = read_pcp(file);
        const int bound = std::atoi(argv[2]);
        const bool fixed_first = argc > 3 && std::string(argv[3]) == "--primera";

        std::cout << dominoes.size() << " fichas, hasta " << bound << " por solución"
                  << (fixed_first ? ", empezando con la ficha 1" : "") << "\n";
        const PcpResult result = solve_pcp(dominoes, bound, fixed_first ? 0 : -1);
        if (result.found) {
            std::cout << "solución con " << result.sequence.size() << (result.sequence.size() == 1 ? " ficha:" : " fichas:");
            for (int i : result.sequence) std::cout << ' ' << i + 1;
            std::cout << "\ncadena: " << concatenate(dominoes, result.sequence, true) << "\n";
        } else if (result.gave_up) {
            std::cout << "búsqueda abandonada: demasiados excesos distintos\n";
        } else if (result.exhausted) {
            std::cout << "sin solución: la búsqueda se quedó sin excesos nuevos\n";
        } else {
            std::cout << "sin solución hasta " << bound << "\n";
        }
        std::cout << "excesos visitados: " << result.visited << "\n";
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << "\n";
        return 1;
    }
    return 0;
}
pcp.hDescargar pcp.h
// El problema de correspondencia de Post (PCP): fichas, comprobación de una solución y
// búsqueda en anchura sobre el exceso entre la cadena de arriba y la de abajo.
#pragma once

#include <cstddef>
#include <istream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <vector>

// Una ficha: una cadena arriba y otra abajo.
struct Domino {
    std::string top;
    std::string bottom;
};

// Lee una instancia: comentarios (#) y líneas vacías antes de `dominoes: k`, y después k líneas
// `arriba abajo`. Después de `dominoes:` ya no hay comentarios, porque las fichas que salen de
// una máquina de Turing usan el símbolo #.
inline std::vector<Domino> read_pcp(std::istream& in) {
    std::string line;
    int count = -1;
    while (std::getline(in, line)) {
        if (line.empty() || line[0] == '#') continue;
        std::istringstream fields(line);
        std::string name;
        fields >> name;
        if (name != "dominoes:" || !(fields >> count) || count < 1) {
            throw std::runtime_error("se esperaba `dominoes: k`, con k >= 1");
        }
        break;
    }
    if (count < 0) throw std::runtime_error("falta la línea `dominoes: k`");
    std::vector<Domino> dominoes;
    for (int i = 0; i < count; ++i) {
        Domino d;
        if (!std::getline(in, line)) throw std::runtime_error("faltan fichas");
        std::istringstream fields(line);
        if (!(fields >> d.top >> d.bottom)) {
            throw std::runtime_error("la ficha " + std::to_string(i + 1) + " no tiene dos cadenas");
        }
        dominoes.push_back(d);
    }
    return dominoes;
}

// La cadena de arriba (o la de abajo) de una secuencia de fichas. Las posiciones cuentan desde 0.
inline std::string concatenate(const std::vector<Domino>& dominoes, const std::vector<int>& sequence, bool top) {
    std::string result;
    for (int i : sequence) result += top ? dominoes.at(i).top : dominoes.at(i).bottom;
    return result;
}

// ¿Es la secuencia una solución? Debe tener al menos una ficha, y arriba y abajo se debe leer
// la misma cadena.
inline bool is_solution(const std::vector<Domino>& dominoes, const std::vector<int>& sequence) {
    if (sequence.empty()) return false;
    for (int i : sequence) {
        if (i < 0 || i >= static_cast<int>(dominoes.size())) return false;
    }
    return concatenate(dominoes, sequence, true) == concatenate(dominoes, sequence, false);
}

// El estado de la búsqueda: qué lado va adelantado y con qué cadena (el exceso).
// Se guarda en una sola cadena: 'T' o 'B' seguido del exceso.
struct Overhang {
    char side = 'T';        // 'T': arriba va adelantado; 'B': abajo
    std::string excess;     // lo que el lado adelantado tiene de más
};

// Agrega una ficha a un estado. Devuelve false si las cadenas dejan de coincidir.
inline bool extend(const Overhang& from, const Domino& d, Overhang& to) {
    // `ahead` es lo que tiene pendiente el lado adelantado después de agregar la ficha,
    // y `behind` lo que agrega el otro lado. Uno debe ser prefijo del otro.
    const std::string ahead = from.excess + (from.side == 'T' ? d.top : d.bottom);
    const std::string& behind = from.side == 'T' ? d.bottom : d.top;
    if (ahead.size() >= behind.size()) {
        if (ahead.compare(0, behind.size(), behind) != 0) return false;
        to.side = from.side;
        to.excess = ahead.substr(behind.size());
    } else {
        if (behind.compare(0, ahead.size(), ahead) != 0) return false;
        to.side = from.side == 'T' ? 'B' : 'T';
        to.excess = behind.substr(ahead.size());
    }
    return true;
}

struct PcpResult {
    bool found = false;
    std::vector<int> sequence;   // la solución, como posiciones desde 0
    bool exhausted = false;      // no quedaron estados por explorar: no hay solución de ninguna longitud
    bool gave_up = false;        // se llegó al tope de excesos guardados antes de terminar
    std::size_t visited = 0;     // excesos distintos que se alcanzaron
};

// Búsqueda en anchura sobre el exceso, hasta `bound` fichas. Si `first` no es -1, la solución
// debe empezar con esa ficha (el PCP modificado). Como recorre por niveles, la solución que
// encuentra es una de las más cortas. `max_states` es un tope de memoria: la cantidad de excesos
// distintos puede crecer exponencialmente con la profundidad.
inline PcpResult solve_pcp(const std::vector<Domino>& dominoes, int bound, int first = -1,
                           std::size_t max_states = 2000000) {
    struct Node {
        int parent;
        int domino;
        Overhang state;
    };
    PcpResult result;
    std::vector<Node> nodes;
    std::unordered_map<std::string, int> seen;
    const int count = static_cast<int>(dominoes.size());

    auto path = [&nodes](int node, int last) {
        std::vector<int> reversed{last};
        for (int at = node; at != -1; at = nodes[at].parent) reversed.push_back(nodes[at].domino);
        return std::vector<int>(reversed.rbegin(), reversed.rend());
    };

    // Nivel 0: ninguna ficha puesta, exceso vacío. No se guarda como nodo: se representa con -1.
    std::vector<int> level{-1};
    for (int depth = 1; depth <= bound; ++depth) {
        std::vector<int> next;
        for (int at : level) {
            const Overhang from = at == -1 ? Overhang{} : nodes[at].state;
            for (int i = 0; i < count; ++i) {
                if (at == -1 && first != -1 && i != first) continue;
                Overhang to;
                if (!extend(from, dominoes[i], to)) continue;
                if (to.excess.empty()) {
                    result.found = true;
                    result.sequence = path(at, i);
                    result.visited = nodes.size();
                    return result;
                }
                const std::string key = to.side + to.excess;
                if (seen.count(key) != 0) continue;
                seen[key] = static_cast<int>(nodes.size());
                next.push_back(static_cast<int>(nodes.size()));
                nodes.push_back({at, i, to});
                if (nodes.size() >= max_states) {
                    result.gave_up = true;
                    result.visited = nodes.size();
                    return result;
                }
            }
        }
        level = next;
        if (level.empty()) {
            result.exhausted = true;
            break;
        }
    }
    result.visited = nodes.size();
    return result;
}

// Búsqueda desde los dos extremos. Una solución leída de derecha a izquierda es una solución
// del conjunto con todas las cadenas invertidas. Se buscan los excesos alcanzables con a lo
// sumo `half` fichas desde el principio y, en el conjunto invertido, desde el final. Un prefijo
// que deja arriba adelantado con el exceso e se completa con un sufijo que, leído al revés,
// deja abajo adelantado con e al revés (y lo mismo cambiando arriba por abajo).
// Encuentra una solución más corta si hay alguna de a lo sumo 2·half fichas.
inline PcpResult solve_pcp_two_ends(const std::vector<Domino>& dominoes, int half) {
    struct Reached {
        int depth;
        std::string parent;   // clave del estado anterior; "" es el estado sin fichas
        int domino;
    };
    using Table = std::unordered_map<std::string, Reached>;
    const std::string solved = "!";   // clave especial: exceso vacío después de al menos una ficha

    auto reach = [&solved, half](const std::vector<Domino>& set) {
        Table table;
        std::vector<std::string> level{""};
        for (int depth = 1; depth <= half && !level.empty(); ++depth) {
            std::vector<std::string> next;
            for (const std::string& from : level) {
                const Overhang state = from.empty() ? Overhang{} : Overhang{from[0], from.substr(1)};
                for (int i = 0; i < static_cast<int>(set.size()); ++i) {
                    Overhang to;
                    if (!extend(state, set[i], to)) continue;
                    const std::string key = to.excess.empty() ? solved : to.side + to.excess;
                    if (table.count(key) != 0) continue;
                    table[key] = Reached{depth, from, i};
                    if (key != solved) next.push_back(key);
                }
            }
            level = next;
        }
        return table;
    };
    // Las fichas desde una clave hasta el estado sin fichas, de la más cercana a la más lejana.
    auto walk = [](const Table& table, std::string key) {
        std::vector<int> result;
        while (!key.empty()) {
            const Reached& r = table.at(key);
            result.push_back(r.domino);
            key = r.parent;
        }
        return result;
    };

    std::vector<Domino> reversed;
    for (const Domino& d : dominoes) {
        reversed.push_back({std::string(d.top.rbegin(), d.top.rend()), std::string(d.bottom.rbegin(), d.bottom.rend())});
    }
    const Table forward = reach(dominoes);
    const Table backward = reach(reversed);

    PcpResult result;
    result.visited = forward.size() + backward.size();
    int best = 0;
    std::string best_forward;
    std::string best_backward;
    for (const auto& [key, r] : forward) {
        int total = 0;
        std::string other;
        if (key == solved) {
            total = r.depth;
        } else {
            other = (key[0] == 'T' ? 'B' : 'T') + std::string(key.rbegin(), key.rend() - 1);
            const auto it = backward.find(other);
            if (it == backward.end()) continue;
            total = r.depth + it->second.depth;
        }
        if (best == 0 || total < best || (total == best && key < best_forward)) {
            best = total;
            best_forward = key;
            best_backward = other;
        }
    }
    if (best == 0) return result;
    result.found = true;
    const std::vector<int> prefix = walk(forward, best_forward);
    result.sequence.assign(prefix.rbegin(), prefix.rend());
    if (!best_backward.empty()) {
        const std::vector<int> suffix = walk(backward, best_backward);
        result.sequence.insert(result.sequence.end(), suffix.begin(), suffix.end());
    }
    return result;
}
tm_pcp.hDescargar tm_pcp.h
// De una máquina de Turing M y una entrada w a un conjunto de fichas: la reducción de A_TM al
// problema de correspondencia de Post. Primero el PCP modificado (la solución debe empezar con
// la ficha 1) y después el paso que quita esa condición.
//
// Supone, como la demostración, que M nunca intenta moverse a la izquierda desde la primera celda.
#pragma once

#include <map>
#include <stdexcept>
#include <string>
#include <vector>

#include "pcp.h"
#include "tm.h"

struct TmDominoes {
    std::vector<Domino> dominoes;          // la ficha 1 (posición 0) es la de inicio
    std::vector<std::string> kinds;        // el tipo de cada ficha, para mostrarlas
    std::map<std::string, char> letter;    // el carácter que representa a cada estado
};

// En las fichas cada estado es un solo carácter: una letra mayúscula que la cinta no usa.
inline std::map<std::string, char> state_letters(const Tm& m) {
    for (char reserved : std::string("#*$")) {
        if (has_symbol(m.tape, reserved)) {
            throw std::runtime_error(std::string("la cinta no puede usar el símbolo ") + reserved);
        }
    }
    std::map<std::string, char> letter;
    char candidate = 'A';
    for (const std::string& q : m.states) {
        while (candidate <= 'Z' && has_symbol(m.tape, candidate)) ++candidate;
        if (candidate > 'Z') throw std::runtime_error("demasiados estados para nombrarlos con una letra");
        letter[q] = candidate;
        ++candidate;
    }
    return letter;
}

inline TmDominoes tm_to_mpcp(const Tm& m, const std::string& w) {
    TmDominoes result;
    result.letter = state_letters(m);
    auto add = [&result](const std::string& kind, const std::string& top, const std::string& bottom) {
        result.dominoes.push_back({top, bottom});
        result.kinds.push_back(kind);
    };
    auto name = [&result](const std::string& q) { return std::string(1, result.letter.at(q)); };
    const std::string accept = name(m.accept);

    // 1. Inicio: abajo queda escrita la configuración inicial. Si w es vacía, el estado lee un blanco.
    initial_configuration(m, w);   // comprueba que w usa el alfabeto de entrada
    add("inicio", "#", "#" + name(m.start) + (w.empty() ? "_" : w) + "#");

    // 2 y 3. Una ficha por cada transición hacia la derecha, y una por cada transición hacia la
    // izquierda y cada símbolo c que pueda estar a la izquierda del cabezal.
    for (const std::string& q : m.states) {
        for (char a : m.tape) {
            const auto it = m.delta.find({q, a});
            if (it == m.delta.end() || q == m.accept || q == m.reject) continue;
            const Transition& t = it->second;
            if (t.move == 'R') add("derecha", name(q) + a, t.write + name(t.next));
        }
    }
    for (const std::string& q : m.states) {
        for (char a : m.tape) {
            const auto it = m.delta.find({q, a});
            if (it == m.delta.end() || q == m.accept || q == m.reject) continue;
            const Transition& t = it->second;
            if (t.move != 'L') continue;
            for (char c : m.tape) add("izquierda", c + name(q) + a, name(t.next) + c + t.write);
        }
    }
    // 4. Copiar un símbolo de la cinta.
    for (char a : m.tape) add("copia", std::string(1, a), std::string(1, a));
    // 5. Copiar el separador, con o sin un blanco nuevo al final de la configuración.
    add("separador", "#", "#");
    add("separador", "#", "_#");
    // 6. Después de aceptar, el estado se come los símbolos vecinos.
    for (char a : m.tape) add("comer", a + accept, accept);
    for (char a : m.tape) add("comer", accept + a, accept);
    // 7. Cierre.
    add("final", accept + "##", "#");
    return result;
}

// Quita la condición de la primera ficha. De u = u1 u2 … un salen tres cadenas:
//   *u1*u2…*un,   u1*u2*…un*,   *u1*u2*…*un*.
// La instancia nueva tiene, en este orden: la ficha de inicio con asterisco antes arriba y antes
// y después abajo; todas las fichas (también la de inicio) con asterisco antes arriba y después
// abajo; y la ficha [*$ / $] para cerrar. Solo la primera puede empezar una solución.
inline std::vector<Domino> mpcp_to_pcp(const std::vector<Domino>& dominoes) {
    auto before = [](const std::string& u) {
        std::string result;
        for (char c : u) {
            result += '*';
            result += c;
        }
        return result;
    };
    auto after = [](const std::string& u) {
        std::string result;
        for (char c : u) {
            result += c;
            result += '*';
        }
        return result;
    };
    std::vector<Domino> result;
    result.push_back({before(dominoes.at(0).top), "*" + after(dominoes.at(0).bottom)});
    for (const Domino& d : dominoes) result.push_back({before(d.top), after(d.bottom)});
    result.push_back({"*$", "$"});
    return result;
}

// De la cadena de una solución, la lista de símbolos de la historia: se quitan los asteriscos
// y el cierre, y cada letra vuelve a ser el nombre de su estado.
inline Tokens decode_match(const TmDominoes& instance, const std::string& match) {
    std::map<char, std::string> state;
    for (const auto& [q, c] : instance.letter) state[c] = q;
    Tokens result;
    for (char c : match) {
        if (c == '*' || c == '$') continue;
        const auto it = state.find(c);
        result.push_back(it == state.end() ? std::string(1, c) : it->second);
    }
    return result;
}
tm_to_pcp.cppDescargar tm_to_pcp.cpp
// Las fichas que la demostración de la indecidibilidad de PCP construye para una máquina M y
// una entrada w.
//   tm_to_pcp maquina.tm w            muestra las fichas por tipo
//   tm_to_pcp maquina.tm w --mpcp     escribe la instancia (la solución debe empezar con la ficha 1)
//   tm_to_pcp maquina.tm w --pcp      escribe la instancia sin esa condición
// La cadena vacía se escribe eps.
#include <exception>
#include <iomanip>
#include <iostream>
#include <string>

#include "tm_pcp.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: tm_to_pcp maquina.tm w [--mpcp | --pcp]\n";
        return 2;
    }
    try {
        const Tm m = load_tm(argv[1]);
        const std::string w = std::string(argv[2]) == "eps" ? "" : argv[2];
        const std::string mode = argc > 3 ? argv[3] : "";
        const TmDominoes instance = tm_to_mpcp(m, w);

        std::string legend;
        for (const std::string& q : m.states) {
            legend += (legend.empty() ? "" : ", ") + std::string(1, instance.letter.at(q)) + " = " + q;
        }
        if (mode == "--mpcp" || mode == "--pcp") {
            const std::vector<Domino> dominoes = mode == "--pcp" ? mpcp_to_pcp(instance.dominoes) : instance.dominoes;
            std::cout << "# Fichas de " << argv[1] << " con la entrada " << argv[2] << ".\n";
            std::cout << "# Estados: " << legend << ".\n";
            std::cout << "dominoes: " << dominoes.size() << "\n";
            for (const Domino& d : dominoes) std::cout << d.top << ' ' << d.bottom << "\n";
            return 0;
        }
        std::cout << "estados: " << legend << "\n";
        std::cout << " n.º  tipo        arriba  abajo\n";
        for (std::size_t i = 0; i < instance.dominoes.size(); ++i) {
            std::cout << std::setw(4) << i + 1 << "  " << std::left << std::setw(12) << instance.kinds[i]
                      << std::setw(8) << instance.dominoes[i].top << instance.dominoes[i].bottom << std::right << "\n";
        }
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << "\n";
        return 2;
    }
    return 0;
}
tm.hDescargar tm.h
// Máquina de Turing determinista de una cinta, con el formato .tm de code/formats.md, y las
// historias de cómputo de esta semana: escribirlas y comprobarlas ventana por ventana.
#pragma once

#include <algorithm>
#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

// δ(q, a) = (next, write, move).
struct Transition {
    std::string next;
    char write = '_';
    char move = 'R';
};

// M = (Q, Σ, Γ, δ, q0, q_accept, q_reject), con los nombres del formato.
struct Tm {
    std::vector<std::string> states;                              // Q
    std::vector<char> alphabet;                                   // Σ
    std::vector<char> tape;                                       // Γ, que contiene a Σ y al blanco _
    std::map<std::pair<std::string, char>, Transition> delta;     // δ; un par sin entrada va a reject
    std::string start;                                            // q0
    std::string accept;                                           // q_accept
    std::string reject;                                           // q_reject
};

inline bool has_state(const Tm& m, const std::string& name) {
    return std::find(m.states.begin(), m.states.end(), name) != m.states.end();
}

inline bool has_symbol(const std::vector<char>& symbols, char c) {
    return std::find(symbols.begin(), symbols.end(), c) != symbols.end();
}

// Lee una descripción en formato .tm. Solo máquinas deterministas.
inline Tm read_tm(std::istream& in) {
    Tm m;
    std::string line;
    bool in_delta = false;
    auto words = [](const std::string& text) {
        std::istringstream fields(text);
        std::vector<std::string> result;
        std::string word;
        while (fields >> word) result.push_back(word);
        return result;
    };
    auto symbols = [](const std::vector<std::string>& list, std::size_t from) {
        std::vector<char> result;
        for (std::size_t i = from; i < list.size(); ++i) {
            if (list[i].size() != 1) throw std::runtime_error("un símbolo es un solo carácter: " + list[i]);
            result.push_back(list[i][0]);
        }
        return result;
    };
    auto one = [](const std::vector<std::string>& list) {
        if (list.size() != 2) throw std::runtime_error("el campo " + list[0] + " lleva un solo estado");
        return list[1];
    };
    while (std::getline(in, line)) {
        if (!line.empty() && line[0] == '#') continue;
        const std::vector<std::string> list = words(line);
        if (list.empty()) {
            if (in_delta) break;
            continue;
        }
        if (!in_delta) {
            if (list[0] == "states:") m.states.assign(list.begin() + 1, list.end());
            else if (list[0] == "alphabet:") m.alphabet = symbols(list, 1);
            else if (list[0] == "tape:") m.tape = symbols(list, 1);
            else if (list[0] == "start:") m.start = one(list);
            else if (list[0] == "accept:") m.accept = one(list);
            else if (list[0] == "reject:") m.reject = one(list);
            else if (list[0] == "delta:") in_delta = true;
            else throw std::runtime_error("campo desconocido: " + list[0]);
            continue;
        }
        // estado lee -> destino escribe movimiento
        if (list.size() != 6 || list[2] != "->" || list[1].size() != 1 || list[4].size() != 1 ||
            (list[5] != "L" && list[5] != "R")) {
            throw std::runtime_error("transición mal escrita: " + line);
        }
        const std::pair<std::string, char> key{list[0], list[1][0]};
        if (m.delta.count(key) != 0) {
            throw std::runtime_error("dos transiciones para (" + list[0] + ", " + list[1] + "): la máquina debe ser determinista");
        }
        m.delta[key] = Transition{list[3], list[4][0], list[5][0]};
    }
    if (!has_symbol(m.tape, '_')) throw std::runtime_error("el alfabeto de la cinta debe tener el blanco _");
    if (has_symbol(m.alphabet, '_')) throw std::runtime_error("el blanco _ no puede estar en el alfabeto de entrada");
    for (char c : m.alphabet) {
        if (!has_symbol(m.tape, c)) throw std::runtime_error(std::string("el símbolo de entrada ") + c + " no está en tape:");
    }
    for (const std::string& q : {m.start, m.accept, m.reject}) {
        if (!has_state(m, q)) throw std::runtime_error("estado desconocido en start, accept o reject: " + q);
    }
    if (m.accept == m.reject) throw std::runtime_error("accept y reject deben ser estados distintos");
    for (const auto& [key, t] : m.delta) {
        if (!has_state(m, key.first) || !has_state(m, t.next)) {
            throw std::runtime_error("estado desconocido en la transición de (" + key.first + ", " + key.second + ")");
        }
        if (!has_symbol(m.tape, key.second) || !has_symbol(m.tape, t.write)) {
            throw std::runtime_error("símbolo fuera de tape: en la transición de (" + key.first + ", " + key.second + ")");
        }
    }
    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);
    return read_tm(file);
}

// Escribe la máquina en formato .tm.
inline void write_tm(std::ostream& out, const Tm& m) {
    out << "states:";
    for (const std::string& q : m.states) out << ' ' << q;
    out << "\nalphabet:";
    for (char c : m.alphabet) out << ' ' << c;
    out << "\ntape:";
    for (char c : m.tape) out << ' ' << c;
    out << "\nstart: " << m.start << "\naccept: " << m.accept << "\nreject: " << m.reject << "\ndelta:\n";
    // En el orden de states y de tape, para que la salida no dependa del orden del mapa.
    for (const std::string& q : m.states) {
        for (char a : m.tape) {
            const auto it = m.delta.find({q, a});
            if (it == m.delta.end()) continue;
            out << q << ' ' << a << " -> " << it->second.next << ' ' << it->second.write << ' ' << it->second.move << "\n";
        }
    }
}

// Una configuración u q v: el cabezal está sobre el primer símbolo de v. Si v es vacía, está
// sobre un blanco. No se guardan los blancos del final de la cinta.
struct Configuration {
    std::string left;    // u
    std::string state;   // q
    std::string right;   // v
};

inline Configuration initial_configuration(const Tm& m, const std::string& w) {
    for (char c : w) {
        if (!has_symbol(m.alphabet, c)) throw std::runtime_error(std::string("la entrada usa un símbolo fuera del alfabeto: ") + c);
    }
    return Configuration{"", m.start, w};
}

inline bool halted(const Tm& m, const Configuration& c) {
    return c.state == m.accept || c.state == m.reject;
}

// Un paso. Devuelve false si la máquina ya se había detenido.
inline bool step(const Tm& m, Configuration& c) {
    if (halted(m, c)) return false;
    const char a = c.right.empty() ? '_' : c.right[0];
    const auto it = m.delta.find({c.state, a});
    if (it == m.delta.end()) {
        c.state = m.reject;
        return true;
    }
    const Transition& t = it->second;
    const std::string rest = c.right.empty() ? "" : c.right.substr(1);
    c.state = t.next;
    if (t.move == 'R') {
        c.left += t.write;
        c.right = rest;
    } else if (c.left.empty()) {
        // En la primera celda, L deja el cabezal donde está.
        c.right = t.write + rest;
    } else {
        const char previous = c.left.back();
        c.left.pop_back();
        c.right = std::string(1, previous) + t.write + rest;
    }
    while (!c.right.empty() && c.right.back() == '_') c.right.pop_back();
    return true;
}

// Resultado de correr la máquina con un tope de pasos.
struct Run {
    bool halted = false;
    bool accepted = false;
    long steps = 0;
    std::vector<Configuration> configurations;   // C1, C2, …, hasta donde se llegó
};

inline Run run_tm(const Tm& m, const std::string& w, long max_steps) {
    Run run;
    Configuration c = initial_configuration(m, w);
    run.configurations.push_back(c);
    while (!halted(m, c) && run.steps < max_steps) {
        step(m, c);
        ++run.steps;
        run.configurations.push_back(c);
    }
    run.halted = halted(m, c);
    run.accepted = c.state == m.accept;
    return run;
}

// Una configuración como lista de símbolos: los de u, el estado, los de v. El estado siempre
// lleva a su derecha el símbolo que lee: si v es vacía se escribe el blanco.
using Tokens = std::vector<std::string>;

inline Tokens tokens_of(const Configuration& c) {
    Tokens result;
    for (char a : c.left) result.push_back(std::string(1, a));
    result.push_back(c.state);
    for (char a : c.right) result.push_back(std::string(1, a));
    if (c.right.empty()) result.push_back("_");
    return result;
}

// La historia C1 # C2 # … # Ck como una sola lista de símbolos. Con `alternate`, las
// configuraciones pares (C2, C4, …) van al revés.
inline Tokens history_tokens(const std::vector<Configuration>& configurations, bool alternate = false) {
    Tokens result;
    for (std::size_t i = 0; i < configurations.size(); ++i) {
        if (i > 0) result.push_back("#");
        Tokens c = tokens_of(configurations[i]);
        if (alternate && i % 2 == 1) std::reverse(c.begin(), c.end());
        result.insert(result.end(), c.begin(), c.end());
    }
    return result;
}

inline std::string join(const Tokens& tokens) {
    std::string result;
    for (std::size_t i = 0; i < tokens.size(); ++i) {
        if (i > 0) result += ' ';
        result += tokens[i];
    }
    return result;
}

inline Tokens split(const std::string& text) {
    std::istringstream fields(text);
    Tokens result;
    std::string word;
    while (fields >> word) result.push_back(word);
    return result;
}

// Comprueba que `next` sigue a `current` en un paso de M, mirando solo ventanas de tres
// símbolos. Devuelve "" si todo está bien, o una frase que dice qué ventana falla.
//
// Las dos filas se completan con blancos hasta el mismo largo y se les pone # a la izquierda.
//   - Una ventana de arriba sin estado: el símbolo del centro se copia abajo sin cambios.
//   - La ventana con el estado en el centro: los tres símbolos de abajo los fija δ.
// Entre las dos reglas queda determinada cada posición de la fila de abajo.
inline std::string check_step(const Tm& m, const Tokens& current, const Tokens& next) {
    const std::size_t width = std::max(current.size(), next.size()) + 2;
    Tokens top{"#"};
    Tokens bottom{"#"};
    top.insert(top.end(), current.begin(), current.end());
    bottom.insert(bottom.end(), next.begin(), next.end());
    top.resize(width + 1, "_");
    bottom.resize(width + 1, "_");
    auto is_state = [&m](const std::string& token) { return has_state(m, token); };
    auto show = [](const Tokens& row, std::size_t j) { return row[j - 1] + " " + row[j] + " " + row[j + 1]; };

    for (std::size_t j = 1; j < width; ++j) {
        if (is_state(top[j])) {
            const std::string& q = top[j];
            const char a = top[j + 1][0];
            const auto it = m.delta.find({q, a});
            if (q == m.accept || q == m.reject || it == m.delta.end()) {
                return "δ(" + q + ", " + top[j + 1] + ") no lleva a una configuración siguiente";
            }
            const Transition& t = it->second;
            const std::string b(1, t.write);
            Tokens expected;
            if (t.move == 'R') expected = {top[j - 1], b, t.next};
            else if (top[j - 1] == "#") expected = {"#", t.next, b};
            else expected = {t.next, top[j - 1], b};
            if (bottom[j - 1] != expected[0] || bottom[j] != expected[1] || bottom[j + 1] != expected[2]) {
                return "ventana del cabezal en la posición " + std::to_string(j) + ": arriba [" + show(top, j) +
                       "], abajo [" + show(bottom, j) + "], y δ pide [" + join(expected) + "]";
            }
        } else if (!is_state(top[j - 1]) && !is_state(top[j + 1]) && bottom[j] != top[j]) {
            return "ventana lejos del cabezal en la posición " + std::to_string(j) + ": arriba [" + show(top, j) +
                   "], abajo [" + show(bottom, j) + "], y el centro debía copiarse";
        }
    }
    return "";
}

// Comprueba que la lista de símbolos es una historia de cómputo de aceptación de M con w.
// Devuelve "" si lo es, o la razón por la que no.
inline std::string check_history(const Tm& m, const std::string& w, const Tokens& history) {
    std::vector<Tokens> configurations(1);
    for (const std::string& token : history) {
        if (token == "#") configurations.emplace_back();
        else configurations.back().push_back(token);
    }
    // 1. Cada tramo es una configuración: símbolos de la cinta y exactamente un estado.
    for (std::size_t i = 0; i < configurations.size(); ++i) {
        int state_count = 0;
        for (const std::string& token : configurations[i]) {
            if (has_state(m, token)) ++state_count;
            else if (token.size() != 1 || !has_symbol(m.tape, token[0])) {
                return "C" + std::to_string(i + 1) + ": " + token + " no es un estado ni un símbolo de la cinta";
            }
        }
        if (state_count != 1) {
            return "C" + std::to_string(i + 1) + " tiene " + std::to_string(state_count) + " estados, y debe tener uno";
        }
    }
    // 2. C1 es la configuración inicial: q0 w, con los blancos que se quiera al final.
    Tokens first = configurations[0];
    while (first.size() > 1 && first.back() == "_") first.pop_back();
    Tokens expected{m.start};
    for (char a : w) expected.push_back(std::string(1, a));
    if (first != expected) return "C1 no es la configuración inicial " + join(expected);
    // 3. Cada configuración sigue a la anterior.
    for (std::size_t i = 0; i + 1 < configurations.size(); ++i) {
        const std::string problem = check_step(m, configurations[i], configurations[i + 1]);
        if (!problem.empty()) return "de C" + std::to_string(i + 1) + " a C" + std::to_string(i + 2) + ": " + problem;
    }
    // 4. La última es de aceptación.
    const Tokens& last = configurations.back();
    if (std::find(last.begin(), last.end(), m.accept) == last.end()) {
        return "la última configuración no está en " + m.accept;
    }
    return "";
}
instances/cycle.pcpDescargar instances/cycle.pcp
# Se puede seguir poniendo fichas para siempre, pero el exceso nunca queda vacío.
dominoes: 3
10 101
011 11
101 011
instances/four_66.pcpDescargar instances/four_66.pcp
# Cuatro fichas para el ejercicio 9 de los apuntes.
dominoes: 4
aab a
ab abb
ab bab
ba aab
instances/hard_75.pcpDescargar instances/hard_75.pcp
# Tres fichas de a lo sumo tres símbolos cuya solución más corta tiene 75 fichas. La cantidad
# de excesos distintos crece con la profundidad: pcp_solve abandona, y pcp_meet la encuentra
# buscando desde los dos extremos.
dominoes: 3
110 1
1 0
0 110
instances/hopcroft.pcpDescargar instances/hopcroft.pcp
# Tres fichas sobre {0, 1}. Tiene solución: 2 1 1 3.
dominoes: 3
1 111
10111 10
10 0
instances/long.pcpDescargar instances/long.pcp
# Tres fichas cortas cuya solución más corta tiene 45 fichas. Salió de probar instancias al
# azar con el programa de esta semana.
dominoes: 3
010 0
01 1000
0 10
instances/longer_top.pcpDescargar instances/longer_top.pcp
# En todas las fichas la cadena de arriba es más larga que la de abajo.
dominoes: 3
abc ab
caa a
acc a
instances/no_start.pcpDescargar instances/no_start.pcp
# Ninguna ficha puede ir primera: en todas, arriba y abajo empiezan con símbolos distintos.
dominoes: 3
abc ca
ca a
acc ba
instances/sipser.pcpDescargar instances/sipser.pcp
# Cuatro fichas sobre {a, b, c}. Tiene solución: 2 1 3 2 4.
dominoes: 4
b ca
a ab
ca a
abc c
machines/empty_ok.tmDescargar machines/empty_ok.tm
# Acepta solo la cadena vacía: con cualquier símbolo, rechaza.
states: q0 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 _ -> q_accept _ R
machines/loop_on_0.tmDescargar machines/loop_on_0.tm
# Acepta las cadenas que empiezan con 1, rechaza las que empiezan con 0 seguido de 1, y con 0
# seguido de solo ceros (o de nada) avanza a la derecha para siempre.
states: q0 q1 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 1 -> q_accept 1 R
q0 0 -> q1 0 R
q1 0 -> q1 0 R
q1 _ -> q1 _ R
machines/starts_01.tmDescargar machines/starts_01.tm
# Acepta las cadenas que empiezan con 01. Mira el segundo símbolo y vuelve al primero,
# para tener un movimiento a la izquierda en una historia corta.
states: q0 q1 q2 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q1 0 R
q1 1 -> q2 1 L
q2 0 -> q_accept 0 R
machines/zeros_ones.tmDescargar machines/zeros_ones.tm
# Decide { 0^n 1^n : n >= 0 }. Es la máquina de code/formats.md.
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

Errores

Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.

errors/two_moves.tmDescargar errors/two_moves.tm
# No es determinista: dos transiciones para (q0, 0). Los programas de esta semana la rechazan.
states: q0 q_accept q_reject
alphabet: 0
tape: 0 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q0 0 R
q0 0 -> q_accept 0 R

Pruebas

Comprueban lo que afirman los apuntes; se ejecutan con make test.

test_fix_input.cppDescargar test_fix_input.cpp
// Pruebas de la técnica de fijar la entrada: L(M_w) = {w} si M acepta w, y ∅ si no.
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

#include "fix_input.h"

static std::vector<std::string> binary_strings(int n) {
    std::vector<std::string> all{""};
    for (std::size_t i = 0; all[i].size() < static_cast<std::size_t>(n); ++i) {
        all.push_back(all[i] + "0");
        all.push_back(all[i] + "1");
    }
    return all;
}

int main() {
    const long steps = 5000;
    int pairs = 0;
    for (const std::string path : {"machines/starts_01.tm", "machines/zeros_ones.tm", "machines/loop_on_0.tm", "machines/empty_ok.tm"}) {
        const Tm m = load_tm(path);
        for (const std::string& w : binary_strings(4)) {
            const Run original = run_tm(m, w, steps);
            const Tm fixed = fix_input(m, w);
            for (const std::string& x : binary_strings(5)) {
                const Run run = run_tm(fixed, x, steps);
                if (x != w) {
                    // Una entrada distinta de w se rechaza siempre, haga lo que haga M.
                    assert(run.halted && !run.accepted);
                } else {
                    // Con w, M_w hace lo que M: acepta, rechaza o sigue corriendo.
                    assert(run.halted == original.halted && run.accepted == original.accepted);
                }
            }
            ++pairs;
        }
    }
    // El ejemplo de los apuntes: starts_01 con w = 01 tiene 9 estados y acepta 01 en 8 pasos.
    {
        const Tm fixed = fix_input(load_tm("machines/starts_01.tm"), "01");
        assert(fixed.states.size() == 9);
        const Run run = run_tm(fixed, "01", 100);
        assert(run.accepted && run.steps == 8);
        assert(!run_tm(fixed, "011", 100).accepted);
    }
    // La máquina que no se detiene con 00: M_00 tampoco se detiene con 00, y rechaza todo lo demás.
    {
        const Tm fixed = fix_input(load_tm("machines/loop_on_0.tm"), "00");
        assert(!run_tm(fixed, "00", steps).halted);
    }
    std::cout << "test_fix_input: ok (" << pairs << " pares de máquina y w, 63 entradas cada uno)\n";
    return 0;
}
test_history.cppDescargar test_history.cpp
// Pruebas de las historias de cómputo: las de los apuntes y el comprobador local.
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

#include "tm.h"

// Todas las cadenas sobre {0, 1} de longitud a lo sumo n, de la más corta a la más larga.
static std::vector<std::string> binary_strings(int n) {
    std::vector<std::string> all{""};
    for (std::size_t i = 0; all[i].size() < static_cast<std::size_t>(n); ++i) {
        all.push_back(all[i] + "0");
        all.push_back(all[i] + "1");
    }
    return all;
}

static bool in_zeros_ones(const std::string& w) {
    const std::size_t half = w.size() / 2;
    return w.size() % 2 == 0 && w == std::string(half, '0') + std::string(half, '1');
}

int main() {
    const Tm m = load_tm("machines/zeros_ones.tm");

    // La historia de 01 que muestran los apuntes: seis configuraciones.
    {
        const Run run = run_tm(m, "01", 1000);
        assert(run.accepted && run.steps == 5 && run.configurations.size() == 6);
        const std::string expected = "q0 0 1 # X q1 1 # q2 X Y # X q0 Y # X Y q3 _ # X Y _ q_accept _";
        assert(join(history_tokens(run.configurations)) == expected);
        assert(check_history(m, "01", split(expected)).empty());
        // No es la historia de otra entrada.
        assert(!check_history(m, "0011", split(expected)).empty());
        // Sin la última configuración no termina en aceptación.
        assert(!check_history(m, "01", split("q0 0 1 # X q1 1 # q2 X Y # X q0 Y # X Y q3 _")).empty());
        // Saltarse una configuración se nota en una ventana.
        assert(!check_history(m, "01", split("q0 0 1 # X q1 1 # X q0 Y # X Y q3 _ # X Y _ q_accept _")).empty());
        // Los blancos de más al final de una configuración no molestan.
        assert(check_history(m, "01", split("q0 0 1 _ # X q1 1 # q2 X Y _ _ # X q0 Y # X Y q3 _ # X Y _ q_accept _")).empty());
    }
    // 0011: catorce configuraciones, y la forma con las pares al revés.
    {
        const Run run = run_tm(m, "0011", 1000);
        assert(run.accepted && run.configurations.size() == 14);
        const Tokens alternate = history_tokens(run.configurations, true);
        const std::string start = "q0 0 0 1 1 # 1 1 0 q1 X # X 0 q1 1 1 #";
        assert(join(alternate).compare(0, start.size(), start) == 0);
    }
    // Con cada cadena corta: acepta exactamente las de la forma 0^n 1^n, y cuando acepta, su
    // historia pasa el comprobador. Además, cambiar un solo símbolo de la historia por cualquier
    // otro la estropea: no hay dos historias de aceptación que difieran en un símbolo.
    int histories = 0;
    long mutations = 0;
    for (const std::string& w : binary_strings(8)) {
        const Run run = run_tm(m, w, 100000);
        assert(run.halted);
        assert(run.accepted == in_zeros_ones(w));
        if (!run.accepted) continue;
        ++histories;
        const Tokens history = history_tokens(run.configurations);
        assert(check_history(m, w, history).empty());
        std::vector<std::string> options{"#"};
        for (const std::string& q : m.states) options.push_back(q);
        for (char a : m.tape) options.push_back(std::string(1, a));
        for (std::size_t i = 0; i < history.size(); ++i) {
            for (const std::string& other : options) {
                if (other == history[i]) continue;
                Tokens changed = history;
                changed[i] = other;
                assert(!check_history(m, w, changed).empty());
                ++mutations;
            }
        }
    }
    assert(histories == 5);

    // La máquina de las cadenas que empiezan con 01: un movimiento a la izquierda.
    {
        const Tm starts = load_tm("machines/starts_01.tm");
        const Run run = run_tm(starts, "01", 100);
        assert(run.accepted);
        assert(join(history_tokens(run.configurations)) == "q0 0 1 # 0 q1 1 # q2 0 1 # 0 q_accept 1");
        assert(check_history(starts, "01", history_tokens(run.configurations)).empty());
        assert(!check_history(starts, "01", split("q0 0 1 # 0 q1 1 # q2 0 0 # 0 q_accept 0")).empty());
        assert(!run_tm(starts, "00", 100).accepted);
    }
    // La que no se detiene: después de 1000 pasos sigue corriendo.
    {
        const Tm loop = load_tm("machines/loop_on_0.tm");
        assert(!run_tm(loop, "00", 1000).halted);
        assert(run_tm(loop, "1", 1000).accepted);
        const Run rejected = run_tm(loop, "01", 1000);
        assert(rejected.halted && !rejected.accepted);
    }
    // L en la primera celda deja el cabezal donde está, y el comprobador lo sabe.
    {
        Tm left = load_tm("machines/starts_01.tm");
        left.delta[{"q0", '1'}] = Transition{"q2", '0', 'L'};
        const Run run = run_tm(left, "1", 100);
        assert(run.accepted);
        assert(join(history_tokens(run.configurations)) == "q0 1 # q2 0 # 0 q_accept _");
        assert(check_history(left, "1", history_tokens(run.configurations)).empty());
    }
    // Una descripción no determinista se rechaza al leerla.
    {
        bool failed = false;
        try {
            load_tm("errors/two_moves.tm");
        } catch (const std::runtime_error&) {
            failed = true;
        }
        assert(failed);
    }
    std::cout << "test_history: ok (" << histories << " historias, " << mutations << " cambios de un símbolo, todos detectados)\n";
    return 0;
}
test_pcp.cppDescargar test_pcp.cpp
// Pruebas de la sesión B: las instancias de PCP de los apuntes, el comprobador y la búsqueda.
#include <cassert>
#include <fstream>
#include <iostream>
#include <random>
#include <string>
#include <vector>

#include "pcp.h"

static std::vector<Domino> load(const std::string& path) {
    std::ifstream file(path);
    assert(file);
    return read_pcp(file);
}

// Fuerza bruta: prueba todas las secuencias de a lo sumo `bound` fichas, por longitud creciente.
// Devuelve la longitud de la solución más corta, o 0 si no hay.
static int brute_force(const std::vector<Domino>& dominoes, int bound) {
    const int count = static_cast<int>(dominoes.size());
    for (int length = 1; length <= bound; ++length) {
        std::vector<int> sequence(length, 0);
        while (true) {
            if (is_solution(dominoes, sequence)) return length;
            int at = length - 1;
            while (at >= 0 && sequence[at] == count - 1) sequence[at--] = 0;
            if (at < 0) break;
            ++sequence[at];
        }
    }
    return 0;
}

int main() {
    // La instancia de cuatro fichas: la solución más corta es 2 1 3 2 4 y se lee abcaaabc.
    {
        const std::vector<Domino> d = load("instances/sipser.pcp");
        assert(d.size() == 4);
        const std::vector<int> claimed{1, 0, 2, 1, 3};
        assert(is_solution(d, claimed));
        assert(concatenate(d, claimed, true) == "abcaaabc");
        assert(!is_solution(d, {1, 0, 2}));
        assert(!is_solution(d, {}));
        const PcpResult r = solve_pcp(d, 10);
        assert(r.found && r.sequence == claimed);
        assert(brute_force(d, 5) == 5);
        // Con cota 4 no la encuentra, y tampoco puede decir que no existe.
        const PcpResult low = solve_pcp(d, 4);
        assert(!low.found && !low.exhausted);
        // Repetir una solución da otra solución.
        assert(is_solution(d, {1, 0, 2, 1, 3, 1, 0, 2, 1, 3}));
    }
    // La de tres fichas binarias: 2 1 1 3, y se lee 101111110.
    {
        const std::vector<Domino> d = load("instances/hopcroft.pcp");
        const PcpResult r = solve_pcp(d, 10);
        assert(r.found && r.sequence == (std::vector<int>{1, 0, 0, 2}));
        assert(concatenate(d, r.sequence, false) == "101111110");
    }
    // Tres instancias sin solución, en las que la búsqueda se queda sin excesos nuevos.
    for (const std::string name : {"no_start", "longer_top", "cycle"}) {
        const PcpResult r = solve_pcp(load("instances/" + name + ".pcp"), 1000);
        assert(!r.found && r.exhausted);
    }
    assert(solve_pcp(load("instances/no_start.pcp"), 1000).visited == 0);
    assert(solve_pcp(load("instances/cycle.pcp"), 1000).visited == 1);
    // La instancia de solución larga.
    {
        const std::vector<Domino> d = load("instances/long.pcp");
        const PcpResult r = solve_pcp(d, 200);
        assert(r.found && is_solution(d, r.sequence));
        assert(r.sequence.size() == 45 && r.visited == 1542);
        const PcpResult low = solve_pcp(d, static_cast<int>(r.sequence.size()) - 1);
        assert(!low.found && !low.exhausted);
    }
    // La instancia en la que los excesos se multiplican: con un tope de 100 000, la búsqueda
    // abandona. Buscando desde los dos extremos sale una solución de 75 fichas, y es la más corta.
    {
        const std::vector<Domino> d = load("instances/hard_75.pcp");
        const PcpResult r = solve_pcp(d, 400, -1, 100000);
        assert(!r.found && !r.exhausted && r.gave_up);
        const PcpResult low = solve_pcp(d, 45);
        assert(!low.found && !low.exhausted && !low.gave_up && low.visited == 70718);
        const PcpResult both = solve_pcp_two_ends(d, 40);
        assert(both.found && both.sequence.size() == 75 && is_solution(d, both.sequence));
        assert(!solve_pcp_two_ends(d, 37).found);
    }
    // Las instancias del ejercicio 9: (a) 3 2 3 1; (b) sin solución; (c) 66 fichas.
    {
        const std::vector<Domino> a{{"a", "baa"}, {"ab", "aa"}, {"bba", "bb"}};
        assert(solve_pcp(a, 10).sequence == (std::vector<int>{2, 1, 2, 0}));
        const std::vector<Domino> b{{"ab", "aba"}, {"baa", "aa"}, {"aba", "baa"}};
        assert(solve_pcp(b, 1000).exhausted);
        const PcpResult c = solve_pcp(load("instances/four_66.pcp"), 100);
        assert(c.found && c.sequence.size() == 66 && c.visited == 81441);
    }
    // Las dos búsquedas dan la misma longitud en las otras instancias.
    for (const std::string name : {"sipser", "hopcroft", "long"}) {
        const std::vector<Domino> d = load("instances/" + name + ".pcp");
        const PcpResult both = solve_pcp_two_ends(d, 30);
        assert(both.found && is_solution(d, both.sequence));
        assert(both.sequence.size() == solve_pcp(d, 60).sequence.size());
    }
    for (const std::string name : {"no_start", "longer_top", "cycle"}) {
        assert(!solve_pcp_two_ends(load("instances/" + name + ".pcp"), 30).found);
    }
    // El exceso: un paso de la búsqueda.
    {
        Overhang to;
        assert(extend(Overhang{}, Domino{"a", "ab"}, to) && to.side == 'B' && to.excess == "b");
        assert(extend(Overhang{'B', "b"}, Domino{"b", "ca"}, to) && to.side == 'B' && to.excess == "ca");
        assert(!extend(Overhang{'B', "b"}, Domino{"a", "ab"}, to));
        assert(extend(Overhang{'B', "c"}, Domino{"cab", "a"}, to) && to.side == 'T' && to.excess == "b");
        assert(extend(Overhang{'B', "c"}, Domino{"c", ""}, to) && to.excess.empty());
    }
    // PCP modificado: con la primera ficha fija, la de cuatro fichas ya no tiene la solución 2 1 3 2 4.
    {
        const std::vector<Domino> d = load("instances/sipser.pcp");
        const PcpResult r = solve_pcp(d, 30, 0);
        assert(!r.found);
        const PcpResult second = solve_pcp(d, 30, 1);
        assert(second.found && second.sequence.front() == 1);
    }
    // La búsqueda en anchura contra la fuerza bruta, en instancias pequeñas al azar.
    {
        std::mt19937 random(2024);
        int with_solution = 0;
        const int total = 3000;
        for (int test = 0; test < total; ++test) {
            std::vector<Domino> d(2 + random() % 2);
            for (Domino& domino : d) {
                for (std::string* side : {&domino.top, &domino.bottom}) {
                    const int length = 1 + static_cast<int>(random() % 3);
                    for (int i = 0; i < length; ++i) *side += static_cast<char>('a' + random() % 2);
                }
            }
            const int expected = brute_force(d, 7);
            const PcpResult r = solve_pcp(d, 7);
            assert(r.found == (expected != 0));
            const PcpResult both = solve_pcp_two_ends(d, 4);
            assert(both.found == r.found);
            if (r.found) {
                assert(both.sequence.size() == r.sequence.size() && is_solution(d, both.sequence));
                assert(is_solution(d, r.sequence));
                assert(static_cast<int>(r.sequence.size()) == expected);
                ++with_solution;
            }
        }
        std::cout << "test_pcp: ok (" << total << " instancias al azar, " << with_solution << " con solución)\n";
    }
    return 0;
}
test_tm_pcp.cppDescargar test_tm_pcp.cpp
// Pruebas de la reducción de A_TM a PCP en casos pequeños: las fichas tienen solución
// exactamente cuando la máquina acepta, y la solución lleva escrita la historia de cómputo.
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

#include "tm_pcp.h"

// ¿Intenta la máquina moverse a la izquierda desde la primera celda en los primeros pasos?
// La construcción supone que no.
static bool moves_left_at_first_cell(const Tm& m, const Run& run) {
    for (const Configuration& c : run.configurations) {
        if (!c.left.empty() || halted(m, c)) continue;
        const auto it = m.delta.find({c.state, c.right.empty() ? '_' : c.right[0]});
        if (it != m.delta.end() && it->second.move == 'L') return true;
    }
    return false;
}

// Quita los blancos del final de cada configuración, para comparar historias.
static Tokens without_trailing_blanks(const Tokens& history) {
    Tokens result;
    auto trim = [&result]() {
        while (!result.empty() && result.back() == "_") result.pop_back();
    };
    for (const std::string& token : history) {
        if (token == "#") trim();
        result.push_back(token);
    }
    trim();
    return result;
}

int main() {
    // El ejemplo de los apuntes: 18 fichas, solución de 15, y la cadena que se lee.
    {
        const Tm m = load_tm("machines/starts_01.tm");
        const TmDominoes instance = tm_to_mpcp(m, "01");
        assert(instance.dominoes.size() == 18);
        assert(instance.dominoes[0].top == "#" && instance.dominoes[0].bottom == "#A01#");
        const PcpResult r = solve_pcp(instance.dominoes, 100, 0);
        assert(r.found && r.sequence.size() == 15);
        assert(r.sequence == (std::vector<int>{0, 1, 7, 9, 3, 9, 2, 7, 9, 6, 15, 9, 11, 9, 17}));
        assert(concatenate(instance.dominoes, r.sequence, true) == "#A01#0B1#C01#0D1#0D#D##");
        // Sin la condición de la primera ficha: 20 fichas y una solución de 16.
        const std::vector<Domino> pcp = mpcp_to_pcp(instance.dominoes);
        assert(pcp.size() == 20);
        const PcpResult free = solve_pcp(pcp, 100);
        assert(free.found && free.sequence.size() == 16 && free.sequence.front() == 0 && free.sequence.back() == 19);
        // Con la entrada 00 la máquina rechaza y la búsqueda se agota: no hay solución.
        const PcpResult none = solve_pcp(tm_to_mpcp(m, "00").dominoes, 100, 0);
        assert(!none.found && none.exhausted);
    }

    struct Case {
        std::string machine;
        std::vector<std::string> inputs;
    };
    const std::vector<Case> cases{
        {"machines/starts_01.tm", {"", "0", "1", "00", "01", "10", "11", "010", "011", "0100"}},
        {"machines/zeros_ones.tm", {"", "0", "1", "01", "10", "001", "011"}},
        {"machines/loop_on_0.tm", {"", "0", "1", "00", "01", "10", "000"}},
        {"machines/empty_ok.tm", {"", "0", "1"}},
    };
    const int bound = 40;
    int accepted = 0;
    int total = 0;
    for (const Case& c : cases) {
        const Tm m = load_tm(c.machine);
        for (const std::string& w : c.inputs) {
            const Run run = run_tm(m, w, 2000);
            assert(!moves_left_at_first_cell(m, run));
            const TmDominoes instance = tm_to_mpcp(m, w);
            const PcpResult fixed = solve_pcp(instance.dominoes, bound, 0);
            const PcpResult free = solve_pcp(mpcp_to_pcp(instance.dominoes), bound);
            // Acepta si y solo si hay solución (hasta la cota, cuando no acepta).
            assert(fixed.found == run.accepted);
            assert(free.found == run.accepted);
            ++total;
            if (!run.accepted) continue;
            ++accepted;
            assert(is_solution(instance.dominoes, fixed.sequence));
            assert(free.sequence.size() == fixed.sequence.size() + 1);
            // La cadena de la solución empieza con # y la historia de aceptación de M con w.
            Tokens decoded = decode_match(instance, concatenate(instance.dominoes, fixed.sequence, true));
            assert(decoded.front() == "#");
            decoded.erase(decoded.begin());
            std::size_t end = 0;
            while (decoded[end] != m.accept) ++end;
            while (decoded[end] != "#") ++end;
            const Tokens history(decoded.begin(), decoded.begin() + static_cast<long>(end));
            assert(check_history(m, w, history).empty());
            assert(without_trailing_blanks(history) == without_trailing_blanks(history_tokens(run.configurations)));
        }
    }
    std::cout << "test_tm_pcp: ok (" << total << " pares de máquina y entrada, " << accepted
              << " con aceptación; sin solución hasta " << bound << " fichas en los demás)\n";
    return 0;
}

Laboratorio

Archivos de partida del laboratorio de la semana.

lab/pcp_search/MakefileDescargar lab/pcp_search/Makefile
TIEMPO = 2
VERIFICADOR = verificador.cpp
include ../../../lab.mk
lab/pcp_search/README.mdDescargar lab/pcp_search/README.md
# Buscar una solución de PCP

En el problema de correspondencia de Post (PCP) se da un conjunto de fichas. Cada ficha tiene una cadena arriba
y otra abajo. Una **solución** es una secuencia de una o más fichas, que se pueden repetir, tal que la cadena
que se lee arriba, juntando las de todas las fichas en orden, es igual a la que se lee abajo.

Esta semana se demostró que ningún algoritmo decide si un conjunto de fichas tiene solución. Lo que sí se puede
programar es una búsqueda: probar secuencias cada vez más largas. Si la solución existe, la búsqueda la
encuentra. Si no existe, la búsqueda no puede saberlo en general, y por eso el programa de este laboratorio
recibe una cota $N$ y nunca responde "no tiene solución".

## Entrada

```text
dominoes: 3
1 111
10111 10
10 0
bound: 10
```

- `dominoes: k` dice cuántas fichas hay. Siguen $k$ líneas, una por ficha: la cadena de arriba, un espacio y la
  cadena de abajo. Las fichas se numeran desde 1, en el orden de la entrada.
- `bound: N` es la cota: la cantidad máxima de fichas de la solución, contando las repeticiones.
- No hay comentarios ni líneas vacías.

## Salida

Una sola línea:

- los números de las fichas de una solución de **a lo sumo $N$ fichas**, en orden y separados por espacios; o
- `sin solución hasta N`, con el valor de $N$ de la entrada, si no existe ninguna solución de a lo sumo $N$
  fichas.

Si hay varias soluciones, cualquiera sirve: no tiene que ser la más corta, solo respetar la cota. El juez usa un
verificador (`verificador.cpp`, pueden leerlo) que pone las fichas de su respuesta y compara las dos cadenas. La
respuesta `sin solución hasta N` solo se acepta si de verdad no hay una solución de a lo sumo $N$ fichas.

## Límites

- $1 \leq k \leq 50$ fichas. Puede haber fichas repetidas.
- Cada cadena tiene entre 1 y 20 caracteres visibles, sin espacios. La mayoría de los casos usa `0` y `1` o
  letras minúsculas. Dos casos usan además `#`, `*`, `$`, `_` y letras mayúsculas: son fichas construidas a
  partir de una máquina de Turing, como en los apuntes.
- $1 \leq N \leq 200$.
- En todos los casos, la cantidad de pares distintos (lado adelantado, exceso) que se alcanzan con a lo sumo $N$
  fichas es menor que 100 000. Sin esa promesa el problema no tendría un límite de tiempo razonable: hay
  conjuntos de tres fichas en los que esa cantidad crece exponencialmente con $N$.

## Ejemplo

Para la entrada de arriba, una salida correcta es:

```text
2 1 1 3
```

Arriba se lee $\mathtt{10111}\,\mathtt{1}\,\mathtt{1}\,\mathtt{10}$ y abajo
$\mathtt{10}\,\mathtt{111}\,\mathtt{111}\,\mathtt{0}$: las dos son $\mathtt{101111110}$. También es correcta
`2 1 1 3 2 1 1 3`, que repite la solución y tiene 8 fichas, porque no pasa de la cota 10.

Con las mismas fichas y `bound: 3`, la salida es:

```text
sin solución hasta 3
```

La instancia tiene solución, pero ninguna de 3 fichas o menos. Por eso la respuesta lleva la cota.

## Tiempo

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

Probar todas las secuencias no alcanza. Con $k$ fichas hay $k^n$ secuencias de $n$ fichas. El caso `09` tiene
tres fichas y su solución más corta tiene 45: son $3^{45}$ secuencias, un número de 22 cifras.

## La idea: el exceso

Mientras se ponen fichas, una de las dos cadenas va adelantada, y lo que ya coincidió no vuelve a importar. Si
arriba se lee $\mathtt{10111}$ y abajo $\mathtt{10}$, lo único que hay que recordar es que **arriba** va
adelantado con el **exceso** $\mathtt{111}$: la ficha siguiente tiene que empezar a cubrirlo desde abajo.

El estado de la búsqueda es entonces un par: qué lado va adelantado y con qué cadena. Poner una ficha lleva de
un estado a otro, o no se puede si las cadenas dejan de coincidir. Una solución es un camino que vuelve al
exceso vacío después de poner al menos una ficha.

```text
(nada)  --ficha 2-->  arriba 111  --ficha 1-->  arriba 1  --ficha 1-->  abajo 1  --ficha 3-->  (nada)
```

Con eso el problema es una búsqueda en un grafo, como las de Algoritmos:

1. **Busquen en anchura**, por niveles: el nivel $n$ tiene los estados a los que se llega con $n$ fichas. Paren
   en el nivel $N$.
2. **No repitan estados.** Si dos secuencias llevan al mismo exceso, lo que se puede hacer después es lo mismo
   para las dos: basta seguir con la primera que llegó. Guarden los estados vistos en un `std::unordered_map` o un
   `std::set`. El caso `11` tiene fichas repetidas y castiga a quien no lo haga.
3. Para escribir la secuencia, guarden por cada estado de qué estado vino y con qué ficha, y reconstruyan el
   camino al final.

## Cómo avanzar

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

1. Lean la entrada y escriban la función que pone una ficha a un estado: recibe el lado adelantado, el exceso y
   la ficha, y devuelve el estado nuevo o avisa que no se puede. Pruébenla a mano con el ejemplo.
2. Escriban la búsqueda en anchura hasta $N$ fichas, todavía sin conjunto de visitados, y pasen los casos
   pequeños.
3. Agreguen el conjunto de visitados. Antes de correr el juez, respondan: ¿por qué no se pierde ninguna solución
   al descartar un estado repetido? ¿Y por qué la solución que encuentra la búsqueda en anchura es una de las
   más cortas?
4. Respondan con la secuencia o con `sin solución hasta N`. Revisen los casos de borde: una sola ficha con las
   dos cadenas iguales, $N = 1$, ninguna ficha que pueda ir primera.
5. Prueben su programa con las fichas de una máquina de Turing. Desde `code/week-10`:

   ```sh
   build/tm_to_pcp machines/starts_01.tm 01 --pcp
   ```

   escribe las fichas de la máquina `starts_01.tm` con la entrada `01`, con dos líneas de comentario al
   inicio. Quiten los comentarios, agreguen `bound: 30` y busquen. ¿Qué se lee en la solución? Es el caso `12`.

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

Los casos traen, entre otros: una solución que usa exactamente $N$ fichas, la misma instancia con una cota
menor, una sola ficha, ninguna ficha que pueda empezar, una instancia en la que se pueden poner fichas para
siempre sin terminar, fichas repetidas, la instancia de solución larga y dos conjuntos de fichas que salen de
máquinas de Turing.

## Preguntas

Respondan en un archivo `respuestas.md`, en esta carpeta.

1. Expliquen en dos líneas por qué su programa, si se le quita la cota $N$, **reconoce** PCP y no lo
   **decide**. ¿Qué hace con un conjunto de fichas que tiene solución? ¿Y con uno que no tiene?
2. El caso `07` no tiene solución de ninguna longitud, y su búsqueda lo puede saber sin llegar a la cota. ¿Cómo?
   ¿Por qué eso no contradice que PCP sea indecidible?
3. ¿Por qué la salida dice `sin solución hasta N` y no "no tiene solución"? Den un caso de la carpeta `casos/`
   en el que la segunda frase sería falsa.

## Para seguir

Opcional, sin casos en el juez.

- Cuenten cuántos estados distintos visita su búsqueda en cada nivel con las fichas
  `110 1`, `1 0`, `0 110`. ¿Por cuánto se multiplica, más o menos, de un nivel al siguiente? ¿Hasta qué $N$
  llega su programa en 2 segundos?
- Busquen desde los dos extremos: una solución leída de derecha a izquierda es una solución del conjunto de
  fichas con todas las cadenas invertidas. ¿Cómo se juntan las dos búsquedas?
lab/pcp_search/solution.cppDescargar lab/pcp_search/solution.cpp
// Buscar una solución de PCP con a lo sumo N fichas.
#include <iostream>
#include <string>
#include <vector>

// Una ficha: una cadena arriba y otra abajo.
struct Domino {
    std::string top;
    std::string bottom;
};

// El estado de la búsqueda: qué lado va adelantado y con qué cadena. Es una propuesta.
struct Overhang {
    char side = 'T';      // 'T' si arriba va adelantado, 'B' si abajo
    std::string excess;   // lo que el lado adelantado tiene de más
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string word;
    int count = 0;
    std::cin >> word >> count;   // dominoes: k
    std::vector<Domino> dominoes(count);
    for (Domino& d : dominoes) std::cin >> d.top >> d.bottom;
    int bound = 0;
    std::cin >> word >> bound;   // bound: N

    // Por hacer: buscar en anchura sobre el exceso, sin repetir excesos ya vistos, y escribir
    // los números de las fichas de una solución (desde 1) o `sin solución hasta N`.
    // Este esqueleto no escribe nada, así que el juez da WA en todos los casos.
    Overhang start;
    return static_cast<int>(start.excess.size());
}
lab/pcp_search/verificador.cppDescargar lab/pcp_search/verificador.cpp
// Verificador del laboratorio: una instancia de PCP puede tener muchas soluciones, así que no
// se compara el texto. Se llama como `verificador caso.in caso.out salida` y termina con 0 si
// la salida es correcta.
//   - Si la salida es una secuencia de fichas, se comprueba que tiene entre 1 y N fichas, que
//     todas existen y que arriba y abajo se lee la misma cadena.
//   - Si la salida es `sin solución hasta N`, solo se acepta cuando la referencia tampoco
//     encontró una. La referencia busca en anchura: si hay una solución de a lo sumo N fichas,
//     la encuentra.
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

struct Domino {
    std::string top;
    std::string bottom;
};

static int fail(const std::string& reason) {
    std::cout << reason << "\n";
    return 1;
}

int main(int argc, char** argv) {
    if (argc != 4) return fail("uso: verificador caso.in caso.out salida");
    std::ifstream input(argv[1]);
    std::ifstream expected(argv[2]);
    std::ifstream output(argv[3]);
    if (!input || !expected || !output) return fail("no se pudo abrir un archivo");

    std::string word;
    int count = 0;
    input >> word >> count;
    std::vector<Domino> dominoes(count);
    for (Domino& d : dominoes) input >> d.top >> d.bottom;
    int bound = 0;
    input >> word >> bound;

    std::string first_expected;
    expected >> first_expected;
    const bool reference_found = first_expected != "sin";

    std::vector<std::string> words;
    while (output >> word) words.push_back(word);
    if (words.empty()) return fail("la salida está vacía");

    if (words[0] == "sin") {
        const std::vector<std::string> wanted{"sin", "solución", "hasta", std::to_string(bound)};
        if (words != wanted) return fail("se esperaba exactamente: sin solución hasta " + std::to_string(bound));
        if (reference_found) return fail("sí hay una solución de a lo sumo " + std::to_string(bound) + " fichas");
        return 0;
    }

    if (static_cast<int>(words.size()) > bound) {
        return fail("la secuencia tiene " + std::to_string(words.size()) + " fichas y la cota es " + std::to_string(bound));
    }
    std::string top;
    std::string bottom;
    for (const std::string& text : words) {
        // Un número de ficha: solo dígitos, entre 1 y k.
        if (text.empty() || text.size() > 6 || text.find_first_not_of("0123456789") != std::string::npos) {
            return fail("no es un número de ficha: " + text);
        }
        const int index = std::stoi(text);
        if (index < 1 || index > count) return fail("no existe la ficha " + text);
        top += dominoes[index - 1].top;
        bottom += dominoes[index - 1].bottom;
    }
    if (top != bottom) return fail("la secuencia no es una solución: arriba y abajo se leen cadenas distintas");
    return 0;
}

Compilación

Cómo se compilan y ejecutan los ejemplos.

MakefileDescargar Makefile
# Semana 10: reducciones, historias de cómputo y el problema de correspondencia de Post.
# 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 las fichas de instances/, así que se corren desde
# esta carpeta. El laboratorio está en lab/pcp_search 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 = pcp_solve pcp_check pcp_meet history check_history tm_to_pcp fix_input
TESTS = test_fix_input test_history test_pcp test_tm_pcp
HEADERS = pcp.h tm.h tm_pcp.h fix_input.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)