Máquina Busy Beaver n1 supera récord BB(10) con verificación Coq

Fuentes: Busy Beaver machine n1 beats BB(10) record with Coq verification

La máquina Busy Beaver n1, desarrollada por jeff87654, ha establecido un nuevo récord en la jerarquía de crecimiento rápido al superar la marca BB(10). A diferencia del récord anterior, que operaba en el nivel ω, esta nueva máquina alcanza el nivel ω+1. Su halting (detención) desde una cinta vacía ha sido verificado formalmente en el sistema de pruebas Coq, sin recurrir a axiomas adicionales, lo que garantiza la exactitud de sus resultados.

El valor exacto calculado por n1, denotado como T, es T = 2↑^37 3. La máquina utiliza una configuración de 10 estados, donde los estados A a H forman una máquina base de 8 estados que coincide con el récord BB(8). Los estados I y J son nuevos y definen la transición de detención. La verificación matemática demuestra que el número de ceros en la cinta (ones) es mayor que el número de Graham y menor que f_(ω+1)(6T), donde f_(ω+1) es la función de la jerarquía de crecimiento rápido.

El funcionamiento de n1 se basa en reglas de limpieza (clearing rules) que transforman valores mediante la operación de potencias de 2. El proceso incluye ciclos de 'park' (estacionar), 'unpack' (desempacar) y 'jump' (saltar), que permiten aumentar la profundidad de los tokens de manera exponencial. La máquina detiene su ejecución cuando el contador de ceros alcanza un valor específico, lo que permite calcular la puntuación exacta. Este avance técnico es significativo para la investigación en límites de la computabilidad, ya que proporciona una prueba formal de que la jerarquía de crecimiento rápido puede alcanzar niveles superiores a ω mediante máquinas de Turing de tamaño finito.