¿Cuánto vale BB(5), el quinto castor afanoso, y por qué costó 62 años demostrarlo?

Un colaborador que firma como mxdys subió el 2 de julio de 2024 el archivo que cerraba una pregunta abierta desde 1962. El quinto castor afanoso vale 47.176.870 pasos: ninguna máquina de Turing de cinco estados y dos símbolos puede dar más pasos que esos y después pararse. La demostración está escrita y verificada en el asistente de pruebas Coq.

¿Qué es exactamente el castor afanoso?

El matemático húngaro Tibor Radó lo definió en 1962, en un artículo del Bell System Technical Journal titulado «On non-computable functions». La idea es una competición: se toman todas las máquinas de Turing con n estados y dos símbolos, se ponen a funcionar sobre una cinta en blanco, se descartan las que no se paran nunca y se mira cuál de las que sí se paran ha durado más. Ese récord es BB(n). Hay una variante, Σ(n), que cuenta unos escritos en la cinta en vez de pasos.

Radó demostró en el mismo artículo que la función no es computable: crece más deprisa que cualquier programa capaz de calcularla. Eso no impide fijar valores sueltos a mano, uno por uno, y eso es lo que se lleva haciendo sesenta años.

¿Qué valores se conocen?

n	BB(n), en pasos	Σ(n), unos escritos	Cuándo se cerró
1	1	1	Años sesenta (Radó)
2	6	4	Años sesenta (Radó)
3	21	6	1965 (Lin y Radó)
4	107	13	1983 (Brady)
5	47.176.870	4.098	2024 (bbchallenge)
6	mayor que 2↑↑↑5	—	Abierto

El salto entre 107 y 47 millones ocurre al añadir un solo estado. El salto siguiente es mucho peor, y ahí está el problema.

¿Por qué costó 62 años un número de ocho cifras?

La máquina campeona se conocía desde hacía tiempo: Heiner Marxen y Jürgen Buntrock la encontraron en 1989. Sabían que existía una máquina de cinco estados que escribía 4.098 unos y se detenía en el paso 47.176.870. Lo que faltaba era lo contrario: probar que ninguna otra la superaba.

Ahí aparece el obstáculo. Se pueden simular todas las máquinas durante 47 millones de pasos y ver cuáles se paran antes. Las que siguen corriendo al final de la simulación no dicen nada por sí solas: una máquina que lleva 47 millones de pasos sin parar puede pararse en el 48 millones, o no pararse jamás. Distinguir «no ha parado todavía» de «no va a parar nunca» exige una demostración específica para cada máquina superviviente.

La versión final enumera 181.385.789 máquinas de cinco estados en forma normal y decide para cada una si se para o no. La mayoría cae con criterios genéricos —máquinas que entran en un bucle exacto, o en un bucle que se repite desplazado por la cinta—, pero siempre quedaba un residuo duro. En 2003, el búlgaro Georgi Georgiev, conocido como Skelet, había reducido el problema a 43 máquinas que ni su programa ni él a mano lograban resolver. Esas 43 fueron las últimas en caer; se sabe ahora que ninguna se para.

¿Qué tiene que ver con el problema de la parada?

El resultado de Turing de 1936 dice que no existe ningún método general que, dado un programa, decida si termina. BB(5) es esa imposibilidad reducida a un tamaño manejable: con cinco estados y dos símbolos —diez instrucciones en total— ya hacen falta técnicas distintas para cada caso difícil, sin un procedimiento único que valga para todos. Cada una de las 43 máquinas de Skelet necesitó su propio argumento.

¿Quién firma la demostración?

El proyecto bbchallenge.org, arrancado en 2022 por Tristan Stérin, con colaboradores repartidos por foros y en su mayoría sin adscripción académica. La prueba formal, Coq-BB5, la ensambló mxdys sobre el trabajo de más de una decena de participantes. El artículo que la describe, firmado por «The bbchallenge Collaboration» con veinte nombres, se envió a arXiv el 15 de septiembre de 2025 y se revisó en marzo de 2026. Es el primer valor nuevo de la función en más de cuarenta años y el primero verificado formalmente.

¿Se sabrá alguna vez BB(6)?

Con seis estados solo hay cotas inferiores, y crecen a base de notaciones que ya no admiten dígitos: en junio de 2025 mxdys probó que BB(6) supera 2↑↑↑5, una torre de exponentes de altura definida por otra torre de exponentes.

Hay un obstáculo más concreto. En junio de 2024 apareció Antihydra, una máquina de seis estados que se para si y solo si se cumple cierta afirmación sobre la sucesión que empieza en 8 y va multiplicando por 3/2 redondeando hacia abajo. Es un problema del mismo linaje que la conjetura de Collatz, y nadie sabe atacarlo. Determinar BB(6) pasa por resolverlo.

Más arriba el terreno está formalmente cerrado: Scott Aaronson y Adam Yedidia construyeron en 2016 una máquina de 7.910 estados cuyo comportamiento la teoría de conjuntos ZFC no puede decidir. Stefan O’Rear bajó ese umbral a 748 estados y Johannes Riebel lo dejó en 745. A partir de ahí, los valores de la función son independientes de los axiomas habituales de las matemáticas.

¿Qué queda por confirmar?

Nada sobre BB(5) en sí: la prueba está verificada por máquina, que es la garantía más fuerte disponible. Lo abierto es todo lo que viene después. No se sabe si BB(6) es alcanzable con las herramientas actuales, no hay ninguna cota superior para él, y no se sabe dónde exactamente empieza el tramo indemostrable: entre 6 y 745 estados hay un hueco enorme sin explorar.

Fuentes: anuncio del 2 de julio de 2024 en el foro de bbchallenge, «Determination of the fifth Busy Beaver value» (arXiv 2509.12337) y las fichas de BB(6) e independencia de ZFC en el wiki del proyecto.