El "Busy Beaver" se salió de control: una máquina de Turing de 10 estados superó al número de Graham.
El valor exacto de BB(10) sigue sin conocerse, pero las posibilidades de un récord futuro se han vuelto aún más enormes.
Una nueva máquina de Turing con diez estados batió el récord anterior en el problema del castor ocupado y elevó drásticamente la conocida cota inferior para la función BB(10). La máquina deja en la cinta más unos que el número de Graham, aunque consta de solo diez estados. El valor exacto de BB(10) sigue sin ser conocido por los matemáticos.
Jeff Ketchersid encontró una nueva máquina por búsqueda por fuerza bruta el 8 de octubre. Luego Ketchersid verificó su comportamiento en el sistema de pruebas formales Coq. La verificación confirma que el programa efectivamente se detiene, supera al anterior campeón de BB(10) y deja en la cinta un número de unos que excede al número de Graham.
Castor ocupado es un juego matemático con reglas muy simples y consecuencias casi absurdamente complejas. Los investigadores toman una máquina de Turing con un número fijo de estados, la ejecutan sobre una cinta vacía y buscan la variante que haga la mayor cantidad de trabajo posible antes de detenerse. Cuantos más estados se permita usar, más difícil es probar qué máquina ostenta realmente el récord absoluto.
Para diez estados la tarea aún no está resuelta. Por tanto, la máquina encontrada no revela BB(10), sino que solo eleva la marca por debajo de la cual la respuesta ya no puede encontrarse. El campeón anterior, hallado en 2024, alcanzaba el nivel fω(fω(25)) en la jerarquía de funciones de crecimiento rápido. La nueva construcción dio el salto al nivel fω+1, donde los números crecen de forma incomparablemente más rápida.
Intentar expresar el resultado en cifras habituales carece de sentido. Incluso el número de Graham, que se hizo famoso precisamente por su tamaño monstruoso, resulta menor que el resultado demostrado por la nueva máquina. Además, la verificación formal no se limita a una estimación aproximada: Coq confirma el número exacto de unos que la máquina deja antes de detenerse y luego demuestra que ese resultado supera al número de Graham.
Ketchersid aún no ha calculado el número exacto de pasos realizados. Sin embargo, la máquina no puede dejar en la cinta más unos que el número de Graham haciendo menos pasos, por lo que la duración de la ejecución también supera al número de Graham. El resumen del proyecto Castor ocupado denomina a la construcción de diez estados la máquina de Turing de dos símbolos más pequeña conocida que ha superado este umbral. Antes, para un resultado similar se necesitaban al menos 13 estados.
El propio récord creció a partir de una máquina de ocho estados. Ketchersid conservó la parte computacional principal y añadió dos estados que interceptan el momento de la parada anterior e inician ciclos posteriores. Cada ciclo sucesivo toma ya un número gigantesco y lo hincha aún más. Por tanto, una pequeña adición al programa desplaza el cómputo a un nuevo nivel en la jerarquía de crecimiento rápido.
La prueba formal se reunió sin axiomas adicionales y verifica por separado la detención de la máquina, el resultado final, las cotas inferiores y la superioridad sobre el anterior campeón de BB(10). No obstante, la comunidad del Castor ocupado marca por ahora el análisis como no verificado de forma independiente. Por tanto, es más correcto hablar de un nuevo campeón publicado y de una cota conocida más alta para BB(10), en lugar del valor definitivo de la función.