💻 computer science

Determination of the fifth Busy Beaver value

Este artículo presenta la primera verificación formal, realizada con el asistente de pruebas Coq y mediante un esfuerzo colaborativo masivo, de que el valor del quinto número Busy Beaver es $S(5) = 47,176,870$ , tras analizar exhaustivamente más de 181 millones de máquinas de Turing de 5 estados.

Autores originales: The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev, Matthew L. House, Rachel Hunter, Iijil, Maja Kądziołka, Pavel Kropitz, Sha

Publicado 2026-03-24

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev, Matthew L. House, Rachel Hunter, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, Théo Zimmermann

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

¡Hola! Imagina que el universo de las matemáticas tiene un "juego de la vida" donde las máquinas son pequeñas hormigas que caminan sobre una cinta infinita de papel. Este artículo es la crónica de cómo un equipo gigante de personas, desde estudiantes hasta expertos, logró resolver uno de los acertijos más antiguos y difíciles de la informática: el problema del "Pájaro Ocupado" (Busy Beaver) de 5 estados.

Aquí te lo explico como si fuera una historia de exploración:

1. ¿Qué es el "Pájaro Ocupado"?

Imagina que tienes una cinta de papel infinita llena de ceros (0) y una pequeña hormiga (la máquina) que puede escribir unos (1), moverse a la izquierda o derecha, y cambiar de "estado de ánimo".

El juego consiste en crear la hormiga más "ocupada" posible. La regla es simple: ¿Cuántos pasos puede dar tu hormiga antes de detenerse?

Si la hormiga se detiene, gana.
Si se queda caminando para siempre (un bucle infinito), pierde.
El objetivo es encontrar la hormiga que camina más pasos sin detenerse, pero que eventualmente se detenga.

Este número máximo de pasos se llama S(n). Para 5 estados (5 "modos" de comportamiento), nadie sabía cuál era el número exacto durante más de 40 años. Era como intentar adivinar cuántas veces puede saltar un grillo antes de cansarse, pero el número es tan enorme que ni las supercomputadoras podían simularlo paso a paso.

2. El Equipo: "La Colmena"

En lugar de un solo genio trabajando en una torre de marfil, este logro fue obra de bbchallenge, una comunidad masiva de internet.

La analogía: Imagina que necesitas construir un rascacielos. En lugar de un solo arquitecto, tienes 1,300 personas en un chat de Discord trabajando 24/7. Algunos dibujan planos, otros ponen ladrillos, otros verifican que la estructura no se caiga.
El resultado: Crearon cientos de "detectives" (algoritmos) para analizar a las hormigas.

3. El Problema: Demasiadas Hormigas

Hay billones de formas posibles de programar estas hormigas de 5 estados. Analizarlas una por una sería como intentar contar cada grano de arena de un desierto a mano.

La solución: Usaron un filtro inteligente llamado Forma Normal de Árbol (TNF).
La analogía: Imagina que tienes un árbol genealógico gigante. En lugar de estudiar a todos los parientes lejanos, el filtro les dice: "Oye, esa rama es idéntica a esta otra, solo que con nombres diferentes. ¡No la estudies, es un duplicado!". Esto redujo el problema de 16 billones de máquinas a "solo" 181 millones. ¡Una reducción increíble!

4. Los Detectives (Deciders)

Para saber si una hormiga se detiene o no, el equipo creó una "línea de montaje" de detectives. Cada máquina pasaba por varios filtros:

El Detective de Bucle: Si la hormiga empieza a repetir el mismo patrón de pasos (como un disco rayado), el detective grita: "¡No se detendrá nunca!".
El Detective de Patrones (NGramCPS): Si la hormiga crea un patrón en la cinta que se cierra sobre sí mismo, el detective sabe que está atrapada en un bucle.
El Detective de Reducción (FAR/WFAR): Estos son detectives muy avanzados que usan "gafas mágicas" (automatas finitos) para ver el futuro de la hormiga sin tener que caminar con ella. Si el patrón futuro es seguro, el detective confirma que no se detendrá.

El resultado: Estos detectives resolvieron el 99.99% de las máquinas.

5. Los "Monstruos" Especiales (Máquinas Esporádicas)

Quedaron 13 hormigas que eran tan extrañas que ningún detective estándar pudo entenderlas. Eran como criaturas mitológicas que se escondían en la selva.

La analogía: Imagina que tienes un reloj que parece funcionar normal, pero en realidad está contando hasta un número tan grande que el universo se habría enfriado antes de que terminara.
El caso "Skelet #17": Esta fue la "jefa final". Llevaba una lista de números y hacía trucos de magia con códigos grises. Requería un argumento matemático tan complejo que tuvo que ser escrito a mano y verificado por un "juez" digital.

6. El Juez Infalible: Coq

Aquí entra la parte más impresionante. Normalmente, en matemáticas, confiamos en que los autores no se equivocaron. Pero aquí, usaron un asistente de pruebas llamado Coq.

La analogía: Imagina que escribes un libro de recetas. En lugar de confiar en que el chef no se equivocó en las cantidades, tienes un robot que lee cada palabra, verifica cada gramo de azúcar y te dice: "¡Error! Si haces esto, la torta explota".
El logro: Coq ejecutó el programa, verificó cada uno de los 181 millones de casos y confirmó que ninguna hormiga de 5 estados puede dar más pasos que la ganadora actual.

7. El Veredicto Final

Después de dos años de trabajo colaborativo y millones de líneas de código, el equipo anunció:

El número máximo de pasos para una máquina de 5 estados es: 47,176,870.

La hormiga ganadora (descubierta en 1989) es, de hecho, la campeona. Nadie puede hacer mejor.

¿Por qué importa esto?

Este artículo no solo nos da un número. Demuestra que:

La colaboración masiva funciona: Gente de todo el mundo, sin conocerse en persona, puede resolver problemas que aterrorizan a los matemáticos.
La inteligencia artificial y la verificación formal son el futuro: Usamos computadoras no solo para calcular, sino para probar que nuestras ideas son correctas sin errores humanos.
El misterio continúa: Aunque resolvimos el de 5 estados, el de 6 estados ya es tan difícil que probablemente nunca lo resolveremos. Es como si acabáramos de llegar a la cima de una montaña, pero nos dimos cuenta de que hay una montaña mucho más alta justo detrás, que toca las nubes.

En resumen: Un ejército de voluntarios, ayudado por un juez robótico infalible, logró atrapar a la hormiga más rápida del mundo de 5 pasos y decirnos exactamente cuándo se detiene. ¡Una hazaña matemática histórica!

Aquí presento un resumen técnico detallado del artículo "Determination of the fifth Busy Beaver value" (Determinación del quinto valor del Pájaro Ajetreado), realizado por la colaboración bbchallenge.

1. El Problema: El Juego del Pájaro Ajetreado (Busy Beaver)

El problema central de este trabajo es determinar el valor de la función $S(n)$ , definida por Tibor Radó en 1962. $S(n)$ representa el número máximo de pasos que una Máquina de Turing con $n$ estados y 2 símbolos (0 y 1) puede ejecutar partiendo de una cinta completamente en cero antes de detenerse.

Contexto: La función $S(n)$ es no computable. Determinar su valor para un $n$ específico implica resolver el problema de la parada para todas las máquinas de $n$ estados.
Estado previo: Antes de este trabajo, solo se conocían los valores para $n=1$ $n = 1$ a $n=4$ $n = 4$ :
- $S(1) = 1$
- $S(2) = 6$
- $S(3) = 21$
- $S(4) = 107$
El desafío de $S(5)$ : Desde 1989, se sabía que existía una máquina de 5 estados que realizaba 47,176,870 pasos (descubierta por Marxen y Buntrock), estableciendo una cota inferior ( $S(5) \ge 47,176,870$ ). Sin embargo, durante más de 30 años, no se pudo probar que ninguna otra máquina de 5 estados pudiera superar este número. La conjetura de Scott Aaronson (2020) sugería que este era el valor exacto, pero faltaba una demostración formal de que todas las demás máquinas de 5 estados o bien se detenían antes o nunca se detenían.

2. Metodología y Enfoque Técnico

La solución se logró mediante una colaboración masiva en línea (bbchallenge.org) y la formalización rigurosa utilizando el asistente de pruebas Coq.

A. Enumeración en Forma Normal de Árbol (TNF)

El espacio de búsqueda de máquinas de 5 estados es inmenso (aprox. $1.67 \times 10^{13}$ máquinas sintácticas). Para hacer el problema tratable, se utilizó la Forma Normal de Árbol (Tree Normal Form - TNF):

Reducción del espacio: La TNF elimina máquinas con transiciones inalcanzables y permutaciones redundantes de estados/símbolos.
Resultado: Reduce el número de máquinas a analizar de 16 billones a 181,385,789 máquinas únicas.
Implementación: La enumeración TNF se implementó y ejecutó directamente dentro de Coq, lo cual fue una innovación sorprendente dado el costo computacional.

B. Pipelines de Decisores (Deciders)

Dado que el problema de la parada es indecidible, no existe un algoritmo universal. En su lugar, se diseñó un "pipeline" (tubería) de múltiples algoritmos de decisión (decisores) que se aplican secuencialmente a cada máquina. Si un decisor determina que una máquina no se detiene, se descarta; si determina que se detiene, se cuenta el número de pasos.
Los decisores principales utilizados son:

Loops (Bucles): Detecta máquinas que entran en ciclos infinitos (Cyclers) o ciclos traslados (Translated Cyclers), analizando la historia de estados y posiciones de la cabeza sin necesidad de simular toda la cinta.
NGramCPS (Conjunto de Posiciones Cerradas n-grama): Una técnica basada en la interpretación abstracta (Closed Tape Language - CTL) que rastrea configuraciones locales (n-gramas) para probar que el conjunto de configuraciones es cerrado y no contiene estados de parada. Se usaron variantes con historiales de cinta aumentados (LRU y longitud fija).
RepWL (Lista de Palabras Repetidas): Utiliza expresiones regulares para simular la cinta, asumiendo que bloques de símbolos que se repiten muchas veces continuarán haciéndolo indefinidamente.
FAR y WFAR (Reducción a Autómatas Finitos):
- FAR: Utiliza autómatas finitos no deterministas (NFA) para definir un lenguaje regular que contiene todas las configuraciones que llevarían a la parada, excluyendo la configuración inicial.
- WFAR (Weighted FAR): Una extensión no regular que utiliza autómatas ponderados (con pesos enteros en las transiciones) para manejar máquinas más complejas que no pueden ser capturadas por autómatas finitos estándar.

C. Máquinas Esporádicas (Sporadic Machines)

De las 181 millones de máquinas, 13 no pudieron ser resueltas por los decisores automatizados. Estas requieren pruebas individuales de no-parada (proposiciones matemáticas complejas y específicas para cada máquina).

Ejemplos notables incluyen "Skelet #1" (un ciclo traslado con un pre-período de $5.41 \times 10^{51}$ pasos) y "Skelet #17" (que gestiona una lista de enteros relacionada con códigos Gray).
Estas 13 máquinas fueron probadas formalmente en Coq por miembros individuales de la colaboración.

3. Contribuciones Clave

Primera determinación formal de un nuevo valor de Busy Beaver en 40 años: Se ha probado rigurosamente que $S(5) = 47,176,870$ .
Verificación Formal Completa: Es el primer valor de Busy Beaver verificado formalmente. El código fuente (Coq-BB5) contiene 27,274 líneas de código Coq y 638 lemas, ejecutando la enumeración y la verificación de los decisores dentro del mismo asistente de pruebas.
Colaboración Masiva Abierta: El proyecto demostró la eficacia de la investigación científica colaborativa en línea, involucrando a cientos de contribuyentes (muchos sin afiliación académica) que desarrollaron algoritmos en múltiples lenguajes (C++, Rust, Python, Haskell, Coq, etc.).
Nuevos Resultados: Además de $S(5)$ $S (5)$ , el trabajo también probó formalmente:
- $S(2, 4) = 3,932,964$ (2 estados, 4 símbolos).
- Reconfirmó $S(4) = 107$ y $S(2, 3) = 38$ .
- Calculó $\Sigma(5) = 4,098$ (máximo número de 1s en la cinta).
- Calculó $space(5) = 12,289$ (máximo número de celdas visitadas).

4. Resultados Principales

Teorema 1.1: $S(5) = 47,176,870$ . La máquina ganadora es la descubierta por Marxen y Buntrock en 1989.
Proceso de decisión:
- Se analizaron 181,385,789 máquinas.
- 175,373,810 fueron decididas como "No Parada" por el decisor de bucles.
- 6,005,142 por NGramCPS.
- 6,577 por RepWL.
- 23 por FAR y 17 por WFAR.
- 183 máquinas se detuvieron (halting), siendo la máxima 47,176,870 pasos.
- 13 máquinas requirieron pruebas manuales individualizadas.
Rendimiento: La compilación del proof en Coq tomó aproximadamente 45 minutos utilizando 13 núcleos de CPU, gracias a la optimización native_compute y la paralelización de la enumeración del árbol.

5. Significado e Implicaciones

Límites de la Matemática y la Computación: El trabajo ilustra la frontera entre lo computable y lo no computable. Mientras que $S(5)$ ha sido resuelto, el artículo sugiere que $S(6)$ es probablemente imposible de probar con los sistemas axiomáticos actuales (como ZF o PA), ya que podría requerir resolver conjeturas matemáticas abiertas extremadamente difíciles (como la conjetura de Collatz) o estar fuera de los límites de la consistencia de ZF.
Criptidos (Cryptids): El artículo introduce el concepto de "Criptidos": máquinas de Turing cuyo problema de parada es matemáticamente difícil pero no se sabe si son halting o no. Se identificaron varios Criptidos de 6 estados (como "Antihydra") que representan problemas abiertos en matemáticas.
Validación de la Investigación Colaborativa: El proyecto valida el modelo de "ciencia abierta" y "construcción pública", donde la comunidad global puede contribuir a problemas matemáticos complejos sin necesidad de una estructura académica tradicional.
Herramientas para IA: Los problemas generados por el juego del Pájaro Ajetreado se están utilizando como benchmarks para probar la capacidad de razonamiento de sistemas de Inteligencia Artificial.

En resumen, este artículo marca un hito histórico al cerrar el capítulo de 40 años sobre $S(5)$ , combinando la potencia de la verificación formal moderna con una colaboración científica sin precedentes.