Semana 11 — Autorreferencia

Objetivos

  • Explicar cómo un programa puede obtener su propio código, y escribir un quine.
  • Enunciar el teorema de recursión y usarlo para volver a demostrar que ATMA_{\mathrm{TM}} es indecidible.
  • Explicar qué dice el primer teorema de incompletitud de Gödel y cómo se sigue de la indecidibilidad.
  • Definir la complejidad de Kolmogorov y demostrar que hay cadenas incompresibles.

Sesión A — Autorreferencia: el teorema de recursión y los quines

Lectura: Apuntes, semana 11.

Apoyo: Sipser, sec. 6.1 (The Recursion Theorem).

Temas:

  • La objeción a la semana 9: la máquina DD se aplicaba a su propia descripción. ¿Puede una máquina tener su descripción?
  • Un programa que imprime su propio código. El intento ingenuo crece sin fin: el programa tendría que contenerse.
  • La solución en dos partes: AA imprime una descripción de BB, y BB, a partir de lo que AA dejó, reconstruye a AA. La frase en español que hace lo mismo.
  • Un quine en C++ leído línea por línea.
  • Teorema de recursión: toda máquina se puede escribir de modo que empiece obteniendo su propia descripción ⟨M⟩\langle M \rangle.
  • Usos: ATMA_{\mathrm{TM}} es indecidible, en cuatro líneas. No existe un algoritmo que diga si una máquina es la más pequeña para su lenguaje.
  • Los virus: un programa que se copia a sí mismo es un quine con algo más.
  • Error común: creer que un quine “hace trampa” leyendo su archivo. No lee nada: el código está construido para reproducirse.

Sesión B — Incompletitud de Gödel · ✂️ Complejidad de Kolmogorov

Lectura: Apuntes, semana 11.

Apoyo: Sipser, sec. 6.2 (Decidability of Logical Theories) y 6.4 (A Definition of Information). Barak, capítulo 11 (Is every theorem provable?).

Temas:

  • El programa de Hilbert: un procedimiento que decida toda afirmación matemática.
  • Sistema formal: axiomas, reglas, y demostraciones que una máquina puede comprobar. Demostrable no es lo mismo que verdadero.
  • ”MM no se detiene con ww” se puede escribir como una afirmación de la aritmética. Se da la idea, sin los detalles de la codificación.
  • Primer teorema de incompletitud: en todo sistema correcto que exprese la aritmética hay afirmaciones verdaderas sin demostración. Si no, enumerar demostraciones decidiría el problema de la parada.
  • La afirmación de Gödel, “esta afirmación no tiene demostración”, construida con el teorema de recursión.
  • Lo que el teorema no dice: no habla de la mente humana ni dice que “nada se puede demostrar”.
  • ✂️ Complejidad de Kolmogorov: K(x)K(x) es la longitud de la descripción más corta de xx. No depende mucho del lenguaje elegido.
  • ✂️ Hay cadenas incompresibles de toda longitud, por conteo. KK no es computable: la paradoja de “el menor número que no se puede describir con menos de veinte palabras”.
  • Error común: usar “incompleto” como si quisiera decir “contradictorio”. Son propiedades distintas, y el teorema las enfrenta.

Laboratorio — Práctica 3 · Opcional: un quine en C++

La sesión es para la Práctica 3 (semanas 6, 7, 9 y 10). Como ejercicio opcional:

  1. Escribir un programa en C++ que imprima exactamente su propio código fuente, sin abrir ningún archivo.
  2. Comprobarlo con make test, que compila el programa, lo ejecuta y compara la salida con el fuente.
  3. Modificarlo para que imprima su código y, además, cuántos caracteres tiene.

Preguntas de repaso

  1. ¿Por qué el intento ingenuo de escribir un quine no termina nunca? ¿Qué idea lo destraba?
  2. Demuestren con el teorema de recursión que ATMA_{\mathrm{TM}} es indecidible.
  3. ¿Por qué el conjunto de las afirmaciones demostrables es reconocible? ¿Qué pasaría si además toda afirmación verdadera fuera demostrable?
  4. Demuestren que para todo nn existe una cadena de longitud nn con K(x)≥nK(x) \geq n.
  5. Si KK fuera computable, ¿qué programa corto imprimiría una cadena de complejidad enorme? ¿Dónde está la contradicción?

Código de la semana

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

Ejemplos (11)Errores (2)Pruebas (2)Laboratorio (4)Compilación (1)

Ejemplos

Los programas que usan los apuntes y la clase.

compress.shDescargar compress.sh
#!/bin/sh
# Comprime tres cadenas binarias de la misma longitud con tres compresores y muestra cuánto
# ocupa cada resultado. El tamaño comprimido es una cota superior de lo que cuesta describir
# la cadena con ese compresor: no es la complejidad de Kolmogorov, que no se puede calcular.
# Se corre desde code/week-11, después de make:  ./compress.sh [n]
set -e
n=${1:-1000000}
tmp=build/compress
mkdir -p "$tmp"
echo "cadenas de $n símbolos (0 y 1); tamaños comprimidos en bits"
printf '%-8s %12s %12s %12s\n' cadena gzip bzip2 xz
for kind in pattern count prng; do
    build/gen_string "$kind" "$n" > "$tmp/$kind.txt"
    g=$(gzip -9 -c "$tmp/$kind.txt" | wc -c)
    b=$(bzip2 -9 -c "$tmp/$kind.txt" | wc -c)
    x=$(xz -9 -c "$tmp/$kind.txt" | wc -c)
    printf '%-8s %12d %12d %12d\n' "$kind" $((g * 8)) $((b * 8)) $((x * 8))
done
echo "el programa que las genera: $(($(wc -c < gen_string.cpp) * 8)) bits de código fuente"
gen_string.cppDescargar gen_string.cpp
// Escribe en la salida estándar una cadena de n bytes de uno de tres tipos. Las tres salen de
// este programa corto, así que las tres tienen una descripción corta: el programa y n.
//
//   build/gen_string pattern n    0101010101...
//   build/gen_string count n      11011100101110111...  (1, 10, 11, 100, 101... en binario, pegados)
//   build/gen_string prng n       los bits de un generador seudoaleatorio con semilla fija
#include <cstddef>
#include <iostream>
#include <random>
#include <string>

int main(int argc, char** argv) {
    if (argc != 3) {
        std::cerr << "uso: gen_string pattern|count|prng n\n";
        return 1;
    }
    const std::string kind = argv[1];
    const std::size_t n = std::stoul(argv[2]);
    std::string out;
    out.reserve(n + 32);
    if (kind == "pattern") {
        while (out.size() < n) {
            out += "01";
        }
    } else if (kind == "count") {
        for (std::size_t i = 1; out.size() < n; i++) {
            std::string digits;
            for (std::size_t rest = i; rest > 0; rest /= 2) {
                digits += static_cast<char>('0' + rest % 2);
            }
            out.append(digits.rbegin(), digits.rend());
        }
    } else if (kind == "prng") {
        // std::mt19937_64 da la misma secuencia en toda computadora: el estándar fija el algoritmo.
        std::mt19937_64 rng(2025);
        while (out.size() < n) {
            std::mt19937_64::result_type word = rng();
            for (int bit = 0; bit < 64; bit++) {
                out += static_cast<char>('0' + ((word >> bit) & 1));
            }
        }
    } else {
        std::cerr << "gen_string: tipo desconocido: " << kind << "\n";
        return 1;
    }
    out.resize(n);
    std::cout << out;
    return 0;
}
make_self.cppDescargar make_self.cpp
// Completa un molde con una copia de sí mismo: lee de la entrada estándar el texto de un
// programa con una arroba, y escribe el programa en el que la arroba es un literal con ese
// mismo texto. Así se construyeron quine.cpp, quine_payload.cpp y self_check.cpp.
//
//   build/make_self < templates/quine.tpl > quine.cpp
#include <exception>
#include <iostream>
#include <iterator>
#include <string>

#include "self.h"

int main() {
    const std::string tpl{std::istreambuf_iterator<char>(std::cin), std::istreambuf_iterator<char>()};
    try {
        std::cout << fill_hole(tpl);
    } catch (const std::exception& e) {
        std::cerr << "make_self: " << e.what() << "\n";
        return 1;
    }
    return 0;
}
naive_growth.cppDescargar naive_growth.cpp
// El intento ingenuo de escribir un quine: un programa que imprime un texto fijo. Si el texto
// es un programa P, el que lo imprime es otro programa, más largo que P. Este ejemplo arma la
// cadena P0, P1, P2... donde cada uno imprime al anterior, y muestra cómo crecen.
//
//   build/naive_growth            la tabla de tamaños
//   build/naive_growth --emit k   el código de Pk
#include <cstddef>
#include <iostream>
#include <string>

#include "self.h"

int main(int argc, char** argv) {
    const std::string p0 = "int main() {}\n";
    if (argc == 3 && std::string(argv[1]) == "--emit") {
        std::string p = p0;
        for (int k = std::stoi(argv[2]); k > 0; k--) {
            p = printer_of(p);
        }
        std::cout << p;
        return 0;
    }
    std::cout << " k   bytes de Pk   lo que imprime Pk\n";
    std::string p = p0;
    std::size_t printed = 0;
    for (int k = 0; k <= 8; k++) {
        std::cout.width(2);
        std::cout << k;
        std::cout.width(14);
        std::cout << p.size();
        if (k == 0) {
            std::cout << "   nada\n";
        } else {
            std::cout << "   P" << k - 1 << ", de " << printed << " bytes\n";
        }
        printed = p.size();
        p = printer_of(p);
    }
    return 0;
}
quine_payload.cppDescargar quine_payload.cpp
// Un quine con payload: escribe su código en la salida estándar y, además, hace otra cosa.
// Un virus tiene la misma forma: la parte que se copia y la parte que actúa. Aquí la segunda
// parte es inofensiva: cuenta sus propias líneas y lo dice por la salida de errores.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>

// Devuelve el código de este programa. Es la construcción del quine, sin imprimir.
std::string own_source() {
    const std::string text = R"~(// Un quine con payload: escribe su código en la salida estándar y, además, hace otra cosa.
// Un virus tiene la misma forma: la parte que se copia y la parte que actúa. Aquí la segunda
// parte es inofensiva: cuenta sus propias líneas y lo dice por la salida de errores.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>

// Devuelve el código de este programa. Es la construcción del quine, sin imprimir.
std::string own_source() {
    const std::string text = @;
    const std::size_t hole = text.find('@');
    return text.substr(0, hole) + "R\"~(" + text + ")~\"" + text.substr(hole + 1);
}

int main() {
    const std::string self = own_source();
    // La copia.
    std::cout << self;
    // El payload.
    const std::ptrdiff_t lines = std::count(self.begin(), self.end(), '\n');
    std::cerr << "payload: me copié completo, " << lines << " líneas y " << self.size() << " bytes\n";
    return 0;
}
)~";
    const std::size_t hole = text.find('@');
    return text.substr(0, hole) + "R\"~(" + text + ")~\"" + text.substr(hole + 1);
}

int main() {
    const std::string self = own_source();
    // La copia.
    std::cout << self;
    // El payload.
    const std::ptrdiff_t lines = std::count(self.begin(), self.end(), '\n');
    std::cerr << "payload: me copié completo, " << lines << " líneas y " << self.size() << " bytes\n";
    return 0;
}
quine.cppDescargar quine.cpp
// Un quine: imprime exactamente su propio código fuente, sin abrir ningún archivo.
#include <cstddef>
#include <iostream>
#include <string>

int main() {
    // Parte A: los datos. Es el texto de todo el programa, con una arroba en el lugar
    // donde va este mismo literal.
    const std::string text = R"~(// Un quine: imprime exactamente su propio código fuente, sin abrir ningún archivo.
#include <cstddef>
#include <iostream>
#include <string>

int main() {
    // Parte A: los datos. Es el texto de todo el programa, con una arroba en el lugar
    // donde va este mismo literal.
    const std::string text = @;

    // Parte B: el código. Imprime lo que hay antes de la arroba, después el texto otra
    // vez, ahora escrito como literal, y al final lo que hay después de la arroba.
    const std::size_t hole = text.find('@');
    std::cout << text.substr(0, hole);
    std::cout << "R\"~(" << text << ")~\"";
    std::cout << text.substr(hole + 1);
    return 0;
}
)~";

    // Parte B: el código. Imprime lo que hay antes de la arroba, después el texto otra
    // vez, ahora escrito como literal, y al final lo que hay después de la arroba.
    const std::size_t hole = text.find('@');
    std::cout << text.substr(0, hole);
    std::cout << "R\"~(" << text << ")~\"";
    std::cout << text.substr(hole + 1);
    return 0;
}
self_check.cppDescargar self_check.cpp
// El teorema de recursión en pequeño: el programa obtiene su propio código y después sigue
// calculando con él. Este lee la entrada estándar y dice si es su propio código.
#include <cstddef>
#include <iostream>
#include <iterator>
#include <string>

// Devuelve el código de este programa. Es la construcción del quine, sin imprimir.
std::string own_source() {
    const std::string text = R"~(// El teorema de recursión en pequeño: el programa obtiene su propio código y después sigue
// calculando con él. Este lee la entrada estándar y dice si es su propio código.
#include <cstddef>
#include <iostream>
#include <iterator>
#include <string>

// Devuelve el código de este programa. Es la construcción del quine, sin imprimir.
std::string own_source() {
    const std::string text = @;
    const std::size_t hole = text.find('@');
    return text.substr(0, hole) + "R\"~(" + text + ")~\"" + text.substr(hole + 1);
}

int main() {
    const std::string self = own_source();
    const std::string input{std::istreambuf_iterator<char>(std::cin), std::istreambuf_iterator<char>()};
    if (input == self) {
        std::cout << "es mi código: " << self.size() << " bytes\n";
    } else {
        std::cout << "no es mi código: yo tengo " << self.size() << " bytes y la entrada " << input.size() << "\n";
    }
    return 0;
}
)~";
    const std::size_t hole = text.find('@');
    return text.substr(0, hole) + "R\"~(" + text + ")~\"" + text.substr(hole + 1);
}

int main() {
    const std::string self = own_source();
    const std::string input{std::istreambuf_iterator<char>(std::cin), std::istreambuf_iterator<char>()};
    if (input == self) {
        std::cout << "es mi código: " << self.size() << " bytes\n";
    } else {
        std::cout << "no es mi código: yo tengo " << self.size() << " bytes y la entrada " << input.size() << "\n";
    }
    return 0;
}
self.hDescargar self.h
// Las funciones de la semana 11: escribir un texto como literal de C++, construir el programa
// que imprime un texto, y completar un molde con una copia de sí mismo (la construcción
// del quine, que es la del teorema de recursión).
#ifndef SELF_H
#define SELF_H

#include <cstddef>
#include <stdexcept>
#include <string>

// El texto s escrito como un literal común de C++, con comillas y secuencias de escape.
// Sirve para textos ASCII y UTF-8: los bytes que no son comilla, barra ni salto pasan igual.
inline std::string cpp_literal(const std::string& s) {
    std::string out = "\"";
    for (char c : s) {
        if (c == '\n') {
            out += "\\n";
        } else if (c == '"' || c == '\\') {
            out += '\\';
            out += c;
        } else {
            out += c;
        }
    }
    out += '"';
    return out;
}

// El texto s escrito como raw string literal. Entre R"~( y )~" todo se toma tal cual:
// comillas, barras invertidas y saltos de línea. No sirve si s contiene el cierre )~".
inline std::string raw_literal(const std::string& s) {
    const std::string open = "R\"~(";
    const std::string close = ")~\"";
    if (s.find(close) != std::string::npos) {
        throw std::invalid_argument("el texto contiene )~\" y no cabe en un raw string literal");
    }
    return open + s + close;
}

// El código de un programa de C++ que imprime w y termina. Es la función q de los apuntes:
// de una cadena w a la descripción de una máquina P_w que escribe w.
inline std::string printer_of(const std::string& w) {
    return "#include <iostream>\nint main() { std::cout << " + cpp_literal(w) + "; }\n";
}

// La construcción del quine. El molde es el texto de un programa con una arroba en el
// lugar donde debe ir un literal con el molde mismo. Devuelve el programa completo:
// lo que hay antes de la primera arroba, el molde como raw string literal, y el resto.
inline std::string fill_hole(const std::string& tpl) {
    const std::size_t hole = tpl.find('@');
    if (hole == std::string::npos) {
        throw std::invalid_argument("el molde no tiene una arroba");
    }
    return tpl.substr(0, hole) + raw_literal(tpl) + tpl.substr(hole + 1);
}

#endif
templates/quine_payload.tplDescargar templates/quine_payload.tpl
// Un quine con payload: escribe su código en la salida estándar y, además, hace otra cosa.
// Un virus tiene la misma forma: la parte que se copia y la parte que actúa. Aquí la segunda
// parte es inofensiva: cuenta sus propias líneas y lo dice por la salida de errores.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>

// Devuelve el código de este programa. Es la construcción del quine, sin imprimir.
std::string own_source() {
    const std::string text = @;
    const std::size_t hole = text.find('@');
    return text.substr(0, hole) + "R\"~(" + text + ")~\"" + text.substr(hole + 1);
}

int main() {
    const std::string self = own_source();
    // La copia.
    std::cout << self;
    // El payload.
    const std::ptrdiff_t lines = std::count(self.begin(), self.end(), '\n');
    std::cerr << "payload: me copié completo, " << lines << " líneas y " << self.size() << " bytes\n";
    return 0;
}
templates/quine.tplDescargar templates/quine.tpl
// Un quine: imprime exactamente su propio código fuente, sin abrir ningún archivo.
#include <cstddef>
#include <iostream>
#include <string>

int main() {
    // Parte A: los datos. Es el texto de todo el programa, con una arroba en el lugar
    // donde va este mismo literal.
    const std::string text = @;

    // Parte B: el código. Imprime lo que hay antes de la arroba, después el texto otra
    // vez, ahora escrito como literal, y al final lo que hay después de la arroba.
    const std::size_t hole = text.find('@');
    std::cout << text.substr(0, hole);
    std::cout << "R\"~(" << text << ")~\"";
    std::cout << text.substr(hole + 1);
    return 0;
}
templates/self_check.tplDescargar templates/self_check.tpl
// El teorema de recursión en pequeño: el programa obtiene su propio código y después sigue
// calculando con él. Este lee la entrada estándar y dice si es su propio código.
#include <cstddef>
#include <iostream>
#include <iterator>
#include <string>

// Devuelve el código de este programa. Es la construcción del quine, sin imprimir.
std::string own_source() {
    const std::string text = @;
    const std::size_t hole = text.find('@');
    return text.substr(0, hole) + "R\"~(" + text + ")~\"" + text.substr(hole + 1);
}

int main() {
    const std::string self = own_source();
    const std::string input{std::istreambuf_iterator<char>(std::cin), std::istreambuf_iterator<char>()};
    if (input == self) {
        std::cout << "es mi código: " << self.size() << " bytes\n";
    } else {
        std::cout << "no es mi código: yo tengo " << self.size() << " bytes y la entrada " << input.size() << "\n";
    }
    return 0;
}

Errores

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

errors/prints_other.cppDescargar errors/prints_other.cpp
// El intento ingenuo. Imprime un programa, pero no es el suyo: lo que imprime no tiene la
// línea que imprime. Para arreglarlo habría que meter esa línea dentro de las comillas, y
// entonces la línea cambia y hay que volver a meterla.
#include <iostream>

int main() {
    std::cout << "#include <iostream>\n\nint main() {\n}\n";
}
errors/reads_file.cppDescargar errors/reads_file.cpp
// No es un quine: abre su propio archivo y lo copia. Deja de funcionar apenas el ejecutable
// se separa del fuente, y no dice nada sobre lo que un programa puede calcular por sí solo.
#include <fstream>
#include <iostream>

int main() {
    std::ifstream source(__FILE__);
    if (!source) {
        std::cerr << "no encuentro mi código fuente\n";
        return 1;
    }
    std::cout << source.rdbuf();
    return 0;
}

Pruebas

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

test_quines.shDescargar test_quines.sh
#!/bin/sh
# Las pruebas que no caben en un assert: compilar programas, ejecutarlos y comparar su salida
# con un archivo, byte por byte. Lo llama make test, desde code/week-11.
set -e
CXX=${CXX:-g++}
CXXFLAGS=${CXXFLAGS:--Wall -Wextra -std=c++20}
BUILD=${BUILD:-build}
tmp=$BUILD/tmp
mkdir -p "$tmp"

# 1. Cada programa es lo que make_self construye con su molde.
for name in quine quine_payload self_check; do
    "$BUILD/make_self" < "templates/$name.tpl" | cmp - "$name.cpp"
done
echo "make_self: ok (3 moldes)"

# 2. El quine imprime su fuente. Su salida, compilada, vuelve a imprimir lo mismo.
"$BUILD/quine" > "$tmp/copy.cpp"
cmp "$tmp/copy.cpp" quine.cpp
$CXX $CXXFLAGS "$tmp/copy.cpp" -o "$tmp/copy"
"$tmp/copy" | cmp - quine.cpp
echo "quine: ok ($(wc -c < quine.cpp) bytes, y la copia de la copia es igual)"

# 3. El quine con payload: la salida estándar es el fuente, y el payload dice sus líneas y bytes.
"$BUILD/quine_payload" > "$tmp/payload.out" 2> "$tmp/payload.err"
cmp "$tmp/payload.out" quine_payload.cpp
lines=$(wc -l < quine_payload.cpp)
bytes=$(wc -c < quine_payload.cpp)
echo "payload: me copié completo, $((lines)) líneas y $((bytes)) bytes" | cmp - "$tmp/payload.err"
echo "quine_payload: ok ($((lines)) líneas, $((bytes)) bytes)"

# 4. self_check reconoce su código y solo su código.
"$BUILD/self_check" < self_check.cpp | grep -q '^es mi código'
"$BUILD/self_check" < quine.cpp | grep -q '^no es mi código'
"$BUILD/self_check" < /dev/null | grep -q '^no es mi código'
{ cat self_check.cpp; echo; } | "$BUILD/self_check" | grep -q '^no es mi código'
echo "self_check: ok"

# 5. El intento ingenuo: P2 imprime P1, P1 imprime P0, y ninguno se imprime a sí mismo.
for k in 0 1 2 3; do
    "$BUILD/naive_growth" --emit "$k" > "$tmp/p$k.cpp"
done
for k in 1 2 3; do
    $CXX $CXXFLAGS "$tmp/p$k.cpp" -o "$tmp/p$k"
    "$tmp/p$k" | cmp - "$tmp/p$((k - 1)).cpp"
    if "$tmp/p$k" | cmp -s - "$tmp/p$k.cpp"; then
        echo "P$k se imprime a sí mismo: no debería"
        exit 1
    fi
done
echo "naive_growth: ok (P3 imprime P2, P2 imprime P1, P1 imprime P0)"

# 6. Los programas de errors/ compilan y no son quines.
for name in prints_other reads_file; do
    $CXX $CXXFLAGS "errors/$name.cpp" -o "$tmp/$name"
done
if "$tmp/prints_other" | cmp -s - errors/prints_other.cpp; then
    echo "errors/prints_other.cpp se imprime a sí mismo: no debería"
    exit 1
fi
# reads_file sí imprime su fuente, pero solo si se ejecuta desde la carpeta donde se compiló:
# el compilador dejó dentro del ejecutable la ruta errors/reads_file.cpp, y desde otra carpeta
# esa ruta no lleva a nada.
"$tmp/reads_file" | cmp - errors/reads_file.cpp
if (cd "$tmp" && ./reads_file) > "$tmp/reads_file.out" 2> /dev/null; then
    echo "errors/reads_file.cpp funcionó sin su archivo: no debería"
    exit 1
fi
echo "errors: ok (prints_other no se imprime; reads_file falla sin su archivo)"

# 7. Las cadenas de la sección de Kolmogorov: longitud exacta, siempre las mismas, y los
# compresores devuelven la original.
for kind in pattern count prng; do
    "$BUILD/gen_string" "$kind" 100000 > "$tmp/$kind.txt"
    test "$(wc -c < "$tmp/$kind.txt")" -eq 100000
    "$BUILD/gen_string" "$kind" 100000 | cmp - "$tmp/$kind.txt"
    gzip -9 -c "$tmp/$kind.txt" | gzip -dc | cmp - "$tmp/$kind.txt"
    xz -9 -c "$tmp/$kind.txt" | xz -dc | cmp - "$tmp/$kind.txt"
done
test "$("$BUILD/gen_string" pattern 12)" = 010101010101
test "$("$BUILD/gen_string" count 17)" = 11011100101110111
# Con un bit por símbolo, ningún código de prefijo baja de n/8 bytes para la cadena del generador.
test "$(gzip -9 -c "$tmp/prng.txt" | wc -c)" -ge 12500
test "$(gzip -9 -c "$tmp/pattern.txt" | wc -c)" -lt 1000
echo "gen_string: ok"
test_self.cppDescargar test_self.cpp
// Pruebas de lo que los apuntes afirman sobre las construcciones de la semana: el literal, el
// programa que imprime un texto, el molde que se completa consigo mismo, la frase que se
// describe a sí misma y los conteos de la complejidad de Kolmogorov.
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <stdexcept>
#include <string>
#include <vector>

#include "self.h"

// Lee un literal común de C++ (el que escribe cpp_literal) y devuelve el texto que denota.
static std::string read_literal(const std::string& lit) {
    assert(lit.size() >= 2 && lit.front() == '"' && lit.back() == '"');
    std::string out;
    for (std::size_t i = 1; i + 1 < lit.size(); i++) {
        if (lit[i] == '\\') {
            i++;
            assert(i + 1 < lit.size());
            out += (lit[i] == 'n') ? '\n' : lit[i];
        } else {
            assert(lit[i] != '"' && lit[i] != '\n');
            out += lit[i];
        }
    }
    return out;
}

static void test_literal() {
    assert(cpp_literal("hola") == "\"hola\"");
    assert(cpp_literal("a\"b") == "\"a\\\"b\"");
    assert(cpp_literal("a\\b\n") == "\"a\\\\b\\n\"");
    // Leer el literal devuelve el texto, también cuando el texto ya es un literal.
    std::string w = "int main() {}\n";
    for (int k = 0; k < 6; k++) {
        assert(read_literal(cpp_literal(w)) == w);
        w = cpp_literal(w) + "\n";
    }
    // El literal siempre es más largo que el texto: al menos las dos comillas.
    for (const std::string& s : {std::string(""), std::string("x"), std::string("\"\\\n")}) {
        assert(cpp_literal(s).size() >= s.size() + 2);
    }
}

static void test_printer() {
    // printer_of(w) contiene el literal de w, así que es más largo que w: ningún texto es
    // igual al programa que lo imprime. Es la razón por la que el intento ingenuo no termina.
    std::string p = "int main() {}\n";
    std::vector<std::size_t> sizes;
    for (int k = 0; k <= 8; k++) {
        sizes.push_back(p.size());
        const std::string next = printer_of(p);
        assert(next.size() > p.size());
        assert(next != p);
        // El programa siguiente contiene el literal del anterior, y ese literal denota al anterior.
        const std::size_t from = next.find('"', next.find("cout"));
        const std::size_t to = next.rfind('"');
        assert(read_literal(next.substr(from, to - from + 1)) == p);
        p = next;
    }
    // Los tamaños de la tabla de los apuntes.
    const std::vector<std::size_t> expected = {14, 67, 124, 188, 266, 372, 534, 808, 1306};
    assert(sizes == expected);
}

static void test_fill_hole() {
    // El programa completo es: antes de la arroba, el molde como literal, después de la arroba.
    const std::string tpl = "AAA @ BBB";
    assert(fill_hole(tpl) == "AAA R\"~(AAA @ BBB)~\" BBB");
    // El molde aparece entero, como datos, dentro del programa.
    assert(fill_hole(tpl).find(tpl) != std::string::npos);
    // El tamaño: dos veces el molde, menos la arroba, más los siete caracteres de R"~( y )~".
    for (const std::string& t : {std::string("@"), std::string("x@y@z"), std::string("uno\n@\ndos\n")}) {
        assert(fill_hole(t).size() == 2 * t.size() - 1 + 7);
    }
    // Solo la primera arroba es el hueco.
    assert(fill_hole("x@y@z") == "xR\"~(x@y@z)~\"y@z");
    // Lo que el programa hace al correr: con el texto del literal vuelve a armarse a sí mismo.
    // Aquí se hace la misma cuenta a mano, sin compilar nada.
    const std::string program = fill_hole(tpl);
    const std::size_t open = program.find("R\"~(") + 4;
    const std::size_t close = program.find(")~\"");
    const std::string text = program.substr(open, close - open);
    assert(text == tpl);
    const std::size_t hole = text.find('@');
    assert(text.substr(0, hole) + "R\"~(" + text + ")~\"" + text.substr(hole + 1) == program);
    // Dos moldes que no sirven.
    bool failed = false;
    try {
        fill_hole("sin hueco");
    } catch (const std::invalid_argument&) {
        failed = true;
    }
    assert(failed);
    failed = false;
    try {
        fill_hole("@ con el cierre )~\" adentro");
    } catch (const std::invalid_argument&) {
        failed = true;
    }
    assert(failed);
}

static void test_sentence() {
    // La frase que se describe a sí misma. La instrucción dice qué hacer con el texto que
    // sigue a los dos puntos: escribirlo dos veces, la segunda vez entre comillas.
    const std::string part = "Escriban dos veces lo que sigue, la segunda vez entre comillas:";
    const std::string sentence = part + " «" + part + "»";
    // Obedecer la instrucción: tomar lo que está entre comillas y escribirlo dos veces.
    const std::size_t open = sentence.find("«") + std::string("«").size();
    const std::size_t close = sentence.find("»");
    const std::string quoted = sentence.substr(open, close - open);
    const std::string result = quoted + " «" + quoted + "»";
    assert(result == sentence);
}

static void test_counting() {
    // Cadenas binarias de longitud menor que n: 2^0 + 2^1 + ... + 2^(n-1) = 2^n - 1.
    for (std::uint64_t n = 0; n <= 60; n++) {
        std::uint64_t shorter = 0;
        for (std::uint64_t len = 0; len < n; len++) {
            shorter += std::uint64_t{1} << len;
        }
        assert(shorter == (std::uint64_t{1} << n) - 1);
        assert(shorter < (std::uint64_t{1} << n));  // menos descripciones que cadenas de longitud n
    }
    // Cadenas de longitud n que se pueden comprimir c bits o más: a lo sumo 2^(n-c+1) - 1.
    // Para n = 1000000 y c = 10, la fracción es menor que 2^(-9) = 1/512.
    for (std::uint64_t n = 10; n <= 60; n++) {
        for (std::uint64_t c = 1; c <= n; c++) {
            const std::uint64_t descriptions = (std::uint64_t{1} << (n - c + 1)) - 1;  // longitud <= n - c
            // descriptions / 2^n < 2^(1-c)
            assert(descriptions < (std::uint64_t{1} << (n - c + 1)));
        }
    }
}

int main() {
    test_literal();
    test_printer();
    test_fill_hole();
    test_sentence();
    test_counting();
    std::puts("test_self: ok");
    return 0;
}

Laboratorio

Archivos de partida del laboratorio de la semana.

lab/quine/check.shDescargar lab/quine/check.sh
#!/bin/sh
# Comprueba un quine. Lo llama el Makefile: sh check.sh quine|length archivo.cpp carpeta
#
#   quine    la salida del programa debe ser igual a su fuente, byte por byte
#   length   la salida debe ser el fuente y, después, una línea con su cantidad de bytes
CXX=${CXX:-g++}
CXXFLAGS=${CXXFLAGS:--Wall -Wextra -std=c++20 -O2}
mode=$1
source=$2
build=${3:-build}

if [ ! -f "$source" ]; then
    echo "no existe $source"
    [ "$mode" = length ] && echo "para el paso 3, copien su quine: cp solution.cpp length.cpp"
    exit 1
fi

# 1. El fuente no puede leerse a sí mismo. La lista es corta a propósito: la regla es no usar
# nada que le entregue al programa su propio texto, esté o no en esta lista.
forbidden='fstream|fopen|freopen|filesystem|__FILE__|source_location|# *embed|# *include *"|popen|system *\(|argv|/proc/|R"'
if grep -n -E "$forbidden" "$source" > /dev/null; then
    echo "RECHAZADO: $source usa algo que el problema no permite:"
    grep -n -o -E "$forbidden" "$source" | sed 's/^/  línea /; s/:/: /'
    echo "Un quine no abre archivos ni le pide su texto al compilador, y en este problema"
    echo "tampoco se usan raw string literals. Lean las reglas en README.md."
    exit 1
fi

# 2. Compilar.
mkdir -p "$build"
if ! $CXX $CXXFLAGS "$source" -o "$build/quine"; then
    echo "ERROR DE COMPILACIÓN: $source"
    exit 1
fi

# 3. Ejecutar, sin entrada y con un límite de 5 segundos.
timeout 5 "$build/quine" < /dev/null > "$build/output.txt"
status=$?
if [ "$status" -ne 0 ]; then
    echo "RE: el programa terminó con código $status (124 quiere decir que pasó de 5 segundos)"
    exit 1
fi

# 4. Comparar byte por byte.
if [ "$mode" = length ]; then
    { cat "$source"; echo "$(($(wc -c < "$source")))"; } > "$build/expected.txt"
else
    cp "$source" "$build/expected.txt"
fi
if cmp -s "$build/output.txt" "$build/expected.txt"; then
    echo "AC: la salida es igual a lo esperado, $(($(wc -c < "$build/expected.txt"))) bytes"
    exit 0
fi
echo "WA: la salida no es igual a lo esperado"
echo "  esperado: $(($(wc -c < "$build/expected.txt"))) bytes; salida: $(($(wc -c < "$build/output.txt"))) bytes"
where=$(cmp "$build/output.txt" "$build/expected.txt" 2> /dev/null | sed 's/^.*differ: //; s/line/línea/')
if [ -n "$where" ]; then
    echo "  primera diferencia: $where"
else
    echo "  una es el comienzo de la otra: sobra o falta texto al final"
fi
echo "  para verla: diff $build/output.txt $build/expected.txt | head"
exit 1
lab/quine/MakefileDescargar lab/quine/Makefile
# Laboratorio opcional de la semana 11: un quine en C++.
# Este problema no usa el juez: la respuesta esperada es el propio fuente.
#
#   make               compila solution.cpp en build/
#   make test          paso 2: revisa el fuente, lo compila, lo ejecuta y compara la salida con él
#   make test-length   paso 3: lo mismo con length.cpp, que además imprime cuántos bytes tiene
#   make clean         borra lo generado

CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -O2
SOURCE ?= solution.cpp
LENGTH ?= length.cpp
BUILD ?= build

.PHONY: all test test-length clean

all: $(BUILD)/solution

$(BUILD)/solution: $(SOURCE) | $(BUILD)
	$(CXX) $(CXXFLAGS) $< -o $@

$(BUILD):
	mkdir -p $@

test:
	@CXX="$(CXX)" CXXFLAGS="$(CXXFLAGS)" sh check.sh quine $(SOURCE) $(BUILD)

test-length:
	@CXX="$(CXX)" CXXFLAGS="$(CXXFLAGS)" sh check.sh length $(LENGTH) $(BUILD)

clean:
	rm -rf build
lab/quine/README.mdDescargar lab/quine/README.md
# Un quine en C++

Un **quine** es un programa que imprime exactamente su propio código fuente, sin leerlo de ningún lado. Esta
semana vieron por qué existe: el programa se parte en datos y código, los datos describen al código, y el
código imprime los datos dos veces, una como texto y otra como literal. En este problema escriben el suyo.

Es el ejercicio opcional de la semana 11. No tiene casos de prueba con archivos `.in` y `.out`, porque la
respuesta esperada es su propio programa: `make test` compara la salida con el fuente.

## Entrada

Ninguna. El programa no lee nada: ni la entrada estándar, ni argumentos, ni archivos.

## Salida

El contenido de `solution.cpp`, byte por byte: los mismos espacios, los mismos saltos de línea, los mismos
comentarios, el mismo salto de línea final si lo hay. Ni un byte más ni uno menos.

## Reglas

El programa tiene que **contener** lo necesario para reproducirse. No puede pedirle su texto a nadie:

- No abre archivos: nada de `<fstream>`, `fopen`, `freopen` ni `<filesystem>`.
- No le pide su texto al compilador: nada de `__FILE__`, `#embed`, `std::source_location`, ni un `#include`
  de un archivo propio (solo se incluyen cabeceras de la biblioteca estándar, entre `<` y `>`).
- No ejecuta otros programas ni mira sus argumentos: nada de `system`, `popen` ni `argv`.
- **No usa raw string literals** (`R"(...)"`). El quine de los apuntes, `quine.cpp`, usa uno, y con eso se
  ahorra la parte más interesante del problema: escribir un texto que tiene comillas, barras invertidas y saltos
  de línea dentro de un literal común. Aquí la resuelven ustedes.
- Las reglas de C++ del curso siguen valiendo: C++20, sin advertencias con `-Wall -Wextra`, solo biblioteca
  estándar, sin variables globales, sin `using namespace std`.

`make test` rechaza un fuente que contenga alguna de esas palabras, con una búsqueda de texto simple. La
búsqueda es una ayuda, no la regla: **la regla es el espíritu**. Un programa que consigue su propio texto por
un camino que la búsqueda no conoce sigue sin ser un quine. Y la búsqueda es tosca: rechaza también una letra
`R` pegada a una comilla dentro de un mensaje, porque así empieza un raw string literal. Si les pasa, cambien
el mensaje.

Un programa vacío no cuenta: en C++ un archivo vacío no compila, porque le falta `main`.

## Paso 1: escribir el quine

Trabajen en `solution.cpp`. El esqueleto es el intento ingenuo: imprime un texto fijo que no es el suyo.

Un plan que funciona, en el orden en que conviene escribirlo:

1. Escriban primero el programa **sin** los datos, con un hueco: una variable `text` cuyo valor todavía no
   conocen, y el código que la usa. Marquen el hueco con un carácter que no aparezca antes en el programa.
2. El código tiene que imprimir tres cosas seguidas: lo que hay en `text` antes de la marca; `text` completo,
   **escrito como aparece en el fuente** (con sus comillas, y con una barra invertida delante de cada comilla y
   de cada barra invertida, y `\n` en lugar de cada salto de línea); y lo que hay en `text` después de la marca.
3. Para lo segundo necesitan una función que reciba un texto y devuelva el literal que lo denota. Es la única
   parte delicada. Decidan de entrada cómo va a quedar escrito el literal en el archivo (¿en una sola línea?,
   ¿un literal por línea?), porque la función tiene que escribirlo exactamente igual.
4. Recién al final llenen el hueco: el valor de `text` es el programa del paso 1, tal cual, con la marca.
   Pueden hacerlo a mano o escribir un programa aparte que lo haga por ustedes. Ese programa auxiliar sí
   puede abrir archivos: no es el quine.

Cada vez que cambien una coma del código tienen que actualizar los datos. Por eso conviene dejar los datos
para el final.

## Paso 2: comprobarlo

```sh
make test
```

`make test` hace cuatro cosas: revisa que el fuente no use nada prohibido, lo compila con
`g++ -Wall -Wextra -std=c++20 -O2`, lo ejecuta sin entrada (con un límite de 5 segundos) y compara la salida
con `solution.cpp` byte por byte, con `cmp`. Con el esqueleto responde:

```text
$ make test
WA: la salida no es igual a lo esperado
  esperado: 508 bytes; salida: 38 bytes
  primera diferencia: byte 1, línea 1
  para verla: diff build/output.txt build/expected.txt | head
make: *** [Makefile:26: test] Error 1
```

Un programa que abre su propio archivo ni siquiera se compila:

```text
$ make test SOURCE=reads_file.cpp
RECHAZADO: reads_file.cpp usa algo que el problema no permite:
  línea 3: fstream
  línea 7: fstream
  línea 7: __FILE__
Un quine no abre archivos ni le pide su texto al compilador, y en este problema
tampoco se usan raw string literals. Lean las reglas en README.md.
make: *** [Makefile:26: test] Error 1
```

Cuando el quine está bien:

```text
$ make test
AC: la salida es igual a lo esperado, 2190 bytes
```

La cantidad de bytes es la del programa de referencia; la de ustedes será otra.

Los errores más frecuentes, y cómo se ven:

| Lo que dice `make test` | Lo que suele pasar |
|---|---|
| La salida tiene un byte más que lo esperado | Un `std::endl` o un `"\n"` de más al final |
| La primera diferencia está en la línea del literal | La función que escribe el literal no lo escribe como está en el archivo: revisen la sangría y los escapes |
| La primera diferencia está después del literal | Cambiaron el código y no actualizaron los datos |
| La diferencia está en un comentario | Los comentarios también son parte del fuente, y tienen que estar en los datos |

## Paso 3: el quine que sabe cuánto mide

Copien su quine a `length.cpp` y modifíquenlo para que imprima su código y, después, una línea con la cantidad
de bytes del archivo `length.cpp`, en decimal.

```sh
cp solution.cpp length.cpp
make test-length
```

`make test-length` hace lo mismo que `make test`, pero espera el fuente seguido de esa línea. Con la referencia:

```text
$ make test-length
AC: la salida es igual a lo esperado, 2206 bytes
```

El archivo de referencia tiene 2201 bytes y la línea agregada, `2201` y un salto de línea, tiene 5.

Se cuentan bytes, que es lo que cuenta `wc -c` y lo que devuelve `size()` en un `std::string`. Una letra con
tilde ocupa 2 bytes en UTF-8, así que el número puede ser mayor que la cantidad de caracteres que ven.

Piensen antes de programar: el número no puede estar escrito en el fuente. Si lo escribieran, al cambiar
cualquier cosa habría que corregirlo, y al corregirlo podría cambiar la longitud. El programa tiene que
**calcularlo**, y para eso necesita tener su propio código en una variable antes de imprimir nada. Ese es el
contenido del teorema de recursión: un programa puede obtener su propia descripción y después seguir
calculando con ella.

## Para pensar

- ¿Dónde está, en su programa, la parte $A$ y dónde la parte $B$ de la construcción de los apuntes?
- Si le quitan todos los comentarios, ¿cuántas líneas tienen que cambiar? ¿Por qué son el doble de las que
  esperaban?
- Su quine, ¿sigue siendo un quine si lo compilan con otro compilador? ¿Y si alguien guarda el archivo con
  saltos de línea de Windows?
lab/quine/solution.cppDescargar lab/quine/solution.cpp
// Un quine: al terminar, este programa debe imprimir exactamente su propio código fuente,
// incluidos estos comentarios, sin abrir ningún archivo.
#include <iostream>
#include <string>

int main() {
    // Por hacer. El esqueleto es el intento ingenuo: imprime un texto fijo, que no es el suyo.
    // Sigan los pasos del enunciado: los datos en text, y el código que los imprime dos veces.
    const std::string text = "#include <iostream>\n#include <string>\n";
    std::cout << text;
    return 0;
}

Compilación

Cómo se compilan y ejecutan los ejemplos.

MakefileDescargar Makefile
# Semana 11: autorreferencia. Quines, el teorema de recursión y la complejidad de Kolmogorov.
# Se usa dentro del entorno del curso.
#
#   make           compila los programas de la clase en build/
#   make test      corre las pruebas: cada quine se compila, se ejecuta y se compara con su fuente
#   make compress  la tabla de tamaños comprimidos de la sección de Kolmogorov
#   make clean     borra lo generado
#
# quine.cpp, quine_payload.cpp y self_check.cpp se construyeron con make_self a partir de las
# moldes de templates/. Las pruebas comprueban que siguen siendo iguales a lo que da su
# molde. El laboratorio está en lab/quine 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 = make_self naive_growth gen_string quine quine_payload self_check
TESTS = test_self
HEADERS = self.h

.PHONY: all test compress clean

all: $(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%)

$(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
	$(CXX) $(CXXFLAGS) $< -o $@

$(BUILD):
	mkdir -p $@

test: all
	@for t in $(TESTS); do $(BUILD)/$$t || exit 1; done
	@CXX="$(CXX)" CXXFLAGS="$(CXXFLAGS)" BUILD="$(BUILD)" sh test_quines.sh
	@echo "Todas las pruebas pasaron."

compress: $(BUILD)/gen_string
	@sh compress.sh

clean:
	rm -rf $(BUILD)