Resultado de BB(3, 4) > Ack(14)

• Se descubrió una nueva TM campeona de Busy Beaver de 3 estados y 4 símbolos, y se calculó que al detenerse deja ((2 \uparrow^{15} 5) + 14) símbolos no cero
• Este número es tan grande incluso en notación de flechas de Knuth, que se resume como la cota inferior (BB(3,4) > Ack(14)), donde el 14.º número de Ackermann se define como (Ack(n)=n \uparrow^n n)
• La operación central de la TM puede comprimirse aproximadamente como (B(k,n,m) \to B(k,0,g_{k-1}^n(m))), pero demostrarlo requiere inducción doble
• Gracias a la fórmula cerrada de evaluación de Matthew House, (g_k^n(0)=\frac{2 \uparrow^k (n+2)}{2}-2), se puede escribir con exactitud la puntuación final (\sigma=(2 \uparrow^{15}5)+14)
• Esta TM simula funciones de nivel Ackermann sin ramas por residuos al estilo Collatz, y también se usa como caso de validación para el Inductive Proof Validator en desarrollo

---

La magnitud del nuevo campeón de Busy Beaver

• Pavel Kropitz descubrió una nueva TM campeona de Busy Beaver de 3 estados y 4 símbolos
• Esta TM puede calcular funciones de “nivel Ackermann” y, al detenerse, deja en la cinta la siguiente cantidad de símbolos no cero
  • ((2 \uparrow^{15} 5) + 14)
• Es un valor enorme incluso en notación de flechas de Knuth, por lo que la cota inferior se resume así
  • (BB(3,4) > Ack(14))
• Aquí, (Ack(14)) es el 14.º número de Ackermann, definido como (Ack(n)=n \uparrow^n n)
• Dentro del rango conocido, es el primer caso encontrado en una búsqueda real de una TM capaz de simular una función de nivel Ackermann

Definición de la TM y configuración final

• La cadena de transiciones de la TM es la siguiente
  • 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC
• La tabla de transiciones se define para los estados A, B, C y los símbolos 0, 1, 2, 3
  • A: 1RB, 3LB, 1RZ, 2RA
  • B: 2LC, 3RB, 1LC, 2RA
  • C: 3RB, 1LB, 3LC, 2RC
• La configuración final es la siguiente
  • (0^\infty ;; 3^{2 g_{15}^{3}(0) + 1} ;; 2^{16} ;; 1 ;; \text{ Z> } ;; 0^\infty)
• En esta configuración, la puntuación (\sigma) se calcula exactamente
  • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

Proceso de descubrimiento y validación

• Pavel Kropitz compartió esta TM el 25 de abril de 2024 en Discord
• En ese momento, el código no podía asignar una cota inferior de puntuación legible para humanos y mostraba el resultado como Halt(SuperPowers(13))
  • Esto significa que la demostración requería 13 niveles de reglas inductivas
• Después comenzó la validación usando el nuevo Inductive Proof Validator
• El 20 de mayo de 2024 se completó la validación, se extrajo la definición exacta de (g_k^n(m)), y con eso se obtuvo la cota inferior (\sigma > 2 \uparrow^{15} 3)
• Matthew House descubrió el 22 de mayo de 2024 la siguiente fórmula cerrada simple
  • (g_k^n(0) = \frac{ 2 \uparrow^k (n+2) }{2} - 2)
• Con esta fórmula ya fue posible expresar el valor exacto de (\sigma)

Análisis del funcionamiento y prueba por inducción doble

• Se define la siguiente configuración
  • (B(k, n, m) = 0^\infty ;; 3^{2m+1} ;; 2^k ;; \text{ A> } ;; 1^n)
• La configuración inicial alcanza el siguiente estado tras 241 pasos
  • (0^\infty ;; \text{A>} ;; 0^\infty \xrightarrow{241} B(16,3,0);;2;;0^\infty)
• La regla central es la siguiente
  • (B(k,n,m) \to B(k,0,g_{k-1}^n(m))), con (k \ge 1)
• (g_k) se define mediante la siguiente recursión
  • (g_0(m)=m+1)
  • (g_{k+1}(m)=g_k^{2m+2}(0))
• El funcionamiento completo es tan simple que casi puede comprimirse en una sola regla, pero esa regla en sí debe demostrarse con inducción doble
• Los lemas y corolarios tratan el proceso por el cual el estado B procesa el bloque 3 y 2^k para producir 1
  • (3;;2^k;;\text{<B} \xrightarrow{2k+1} 2^k;;\text{<B};;1)
  • (3^m;;2^k;;\text{<B} \xrightarrow{(2k+1)m} 2^k;;\text{<B};;1^m)
• El teorema 3 muestra que la regla central se cumple para todo (k \ge 1, n \ge 0, m \ge 0)
  • El caso base (k=1) se trata por inducción sobre (n)
  • El paso inductivo usa a la vez la hipótesis sobre (k) y la hipótesis inductiva sobre (n)

Cálculo del valor exacto

• (g_k) tiene una evaluación cerrada relativamente simple que usa solo flechas de Knuth y aritmética
• Para todo (k \ge 0, m \ge 0), se cumple lo siguiente
  • (2 g_{k+1}(m) + 4 = 2 \uparrow^k (2m+4))
  • donde (a \uparrow^0 b = ab)
• Este resultado se demuestra por inducción sobre (k)
  • En el caso base (k=0), se obtiene (g_1(m)=2m+2)
  • En el paso inductivo se usa la aplicación repetida de ((2 \uparrow^k)^n)
• La forma cerrada depende de la coincidencia de que (2 \uparrow^k 2 = 4) se cumple para todo (k)
  • Si el parámetro hubiera variado un poco y hubiera tomado la forma ((2 \uparrow^k)^{2m+2}5), probablemente habría sido difícil obtener una expresión cerrada
• Como corolario, para todo (k \ge 0, n \ge 0) se cumple lo siguiente
  • (2 g_k^n(0) + 4 = 2 \uparrow^k (n+2))
• La puntuación final se deriva directamente así
  • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

Resultado de las permutaciones al cambiar el estado inicial

• Si se cambia el estado inicial a B o C, aparecen resultados relacionados pero más pequeños
  • (0^\infty ;; \text{B>} ;; 0^\infty \xrightarrow{86} B(7,3,0);;2;;0^\infty)
  • (0^\infty ;; \text{C>} ;; 0^\infty \xrightarrow{20} B(1,3,0);;2;;0^\infty)
• La puntuación cuando el estado inicial es B es la siguiente
  • (\sigma_B = 2 g_6^3(0) + 9 = (2 \uparrow^6 5) + 5)
• Cuando el estado inicial es C, se detiene en 72 pasos y la puntuación es la siguiente
  • (\sigma_C = 2 g_0^3(0) + 3 = (2 \uparrow^0 5) - 1 = 9)
• La primera permutación que comienza en B también es otra TM BB(3,4) de alto rango
• Al convertirla a TNF, la cadena de transición queda así
  • 1RB3RB1LC2LA_2LA2RB1LB3RA_3LA1RZ1LC2RA

La simplicidad de no tener reglas tipo Collatz

• Uno de los puntos interesantes de esta TM es que es más simple de lo esperado
• No tiene reglas tipo Collatz que cambien su comportamiento según el residuo del valor
• Todavía es demasiado pronto para decir si ya terminó el dominio de las TM tipo Collatz
• Puede que aún existan TM tipo Collatz de nivel Ackermann, pero se especula que podrían no verse de inmediato por sesgo de selección
• Una posible razón por la que esta TM fue encontrada como la primera TM de nivel Ackermann es que era lo bastante simple como para demostrar su detención sin tener que implementar aritmética modular sobre funciones de nivel Ackermann

Inductive Proof Validator

• Esta TM resultó adecuada como caso de prueba para el Inductive Proof Validator en desarrollo
• El objetivo del proyecto es crear un formato estandarizado de certificados para “pruebas inductivas”
• Aquí, “prueba inductiva” se usa como un término amplio que abarca inferencia hacia adelante y análisis basado en reglas en general
• La idea es que cualquiera con un “inductive decider” pueda escribir la regla en ese formato y que el validador pueda comprobar la demostración
• El sistema sigue siendo muy tosco y no está listo para uso real, pero con algo de trabajo manual ya se ha usado para demostrar el comportamiento de varias TM, incluida esta TM

[GN⁺]

Opiniones en Hacker News

• Es fácil pensar que un programa de máquina de Turing que corre durante muchísimo tiempo será profundamente complejo o código espagueti, pero el nuevo campeón es casi un contraejemplo.
  Solo tiene tres estados, A, B y C; B cede el control a A y C, pero A y C no se “conocen” entre sí y solo regresan a B.
  Si fuera verdadero código espagueti, cada estado podría saltar a todos los demás, pero esto es una especie de composición modular.
  Además, nunca imprime una celda en blanco, y como todas las instrucciones cambian el estado o el color, tampoco hay “instrucciones perezosas” que solo muevan la posición, como B1 -> 1LB.

  • Incluso dentro del proyecto bbchallenge hay debate sobre si las propiedades de los campeones actuales de larga ejecución son realmente las propiedades de las máquinas que más tiempo corren en ese tamaño, o si se trata de un efecto farola, donde solo se ven las propiedades fáciles de encontrar y demostrar con búsqueda automática.
    No se puede saber hasta descartar todo el espacio de búsqueda, ya sea de forma definitiva o heurística.
    Todos los tamaños por encima de BB(5, 2) contienen máquinas caóticas y seudorrandom que se espera que corran para siempre, pero que no pueden demostrarse sin grandes avances en teoría de números.
    Aun así, se considera que una máquina de larga ejecución no puede ser completamente caótica.
    Si arrojara símbolos aleatorios sobre la cinta, pronto llegaría a una configuración de parada, una configuración cíclica o un patrón simplificado.
    De todos modos, sí es posible una máquina que simule algo caótico a un nivel más alto y que, entre cada paso de alto nivel, gaste una cantidad absurda de tiempo antes de detenerse.
  • Una máquina de Turing de n estados y s símbolos solo puede transicionar como máximo a n estados distintos.
    Por eso, si s=4 o s=2, solo máquinas de Turing muy pequeñas pueden parecer código espagueti.

• El nuevo poseedor del récord de BB(3,4) es el siguiente:
  0 1 2 3
A 1RB 3LB 1RZ 2RA
B 2LC 3RB 1LC 2RA
C 3RB 1LB 3LC 2RC
(t', d, s') en la fila s y la columna t representa la transición cuando el símbolo bajo el cabezal de la cinta es t en el estado s.
  Sobrescribe el símbolo t con t', se mueve a la izquierda/derecha según la dirección d y luego cambia el estado a s'; si s' == Z, se detiene.
  Esto equivale a 3*4*log2(4*2*log2(4+1)), es decir, alrededor de 64 bits de información.
  En cambio, BBλ(49), de solo 49 bits, supera por mucho el número de Graham https://oeis.org/A333479

  • Contar la cantidad de máquinas de Turing distintas no es sencillo.
    El cálculo anterior es el enfoque más amplio, que considera que cada celda puede tener cualquier combinación de (símbolo, dirección, estado), por lo que sobreestima bastante los bits necesarios para describir una máquina de Turing arbitraria.
    En el caso de BB(3, 4), si se usa Tree Normal Form, es decir, el algoritmo de Brady (https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html), hay solo alrededor de 600 mil millones de máquinas de Turing distintas, lo que da menos de 40 bits.
  • En este programa, el 1R de 1RZ parece un valor elegido arbitrariamente.
    Como se detiene ahí, no importa qué quede en la cinta ni hacia dónde se mueva el cabezal.
    De hecho, escribir 1 tampoco es importante, aunque escribir 0 probablemente no habría sido óptimo.
    En esa posición ya había un 2, que cambia a 1, pero según la cantidad de símbolos en la cinta, el 2 también se habría contado igual.
  • No entiendo bien de dónde sale el término log2(4+1).
    Si se calcula 3*4*log2(4*2*log2(4+1)), da alrededor de 51, y desde la perspectiva de un no especialista habría pensado que sería 3*4*log2(4*2*4) = 60.
    Me pregunto si acaso es 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64.

• Me dio curiosidad el funcionamiento, así que lo implementé aquí: turingmachine.io/?import-gist=c862f28918f3d889f964797694d28fcc
  Si lo ejecutas un momento, se ve qué está pasando.
  El estado B cambia 0 a 2 y 1 a 1, y transiciona a C; el estado C cambia 3 a 2 y transiciona a A.
  Por eso, para arreglar 2 -> 1, tiene que pasar una vez por todos los 3, lo que hace crecer repetidamente de forma exponencial el tramo continuo de 3.

  • Crear una máquina de Turing que crezca exponencialmente para siempre es bastante fácil.
    La parte realmente difícil de entender es por qué finalmente se detiene después de una cantidad inimaginable de pasos.

• Todo suena como code golf extremo.
  En otra dirección, se puede mirar algo llamado BitGrid.
  En BitGrid, cada celda tiene apenas 4 bits de estado, así que una cuadrícula de 4x4 celdas no puede contar más allá de 2^64 pase lo que pase.
  Sería interesante encontrar hasta dónde puede contar realmente, y en cuadrículas pequeñas las conexiones de los bordes dominarán el resultado.
  https://esolangs.org/wiki/Bitgrid
  https://github.com/mikewarot/Bitgrid

• Esta tabla probablemente sea la descripción de una máquina de Turing; estaría bueno tener algún material para ver cómo interpretarla.

  • Los estados A, B, C corresponden a destinos de goto, y los colores 0, 1, 2, 3 son los datos durante la ejecución.
    En cada estado se lee el color actual y, según ese color, se ejecuta la instrucción de “qué color escribir, si moverse a la izquierda/derecha y a qué estado ir”.
    Si se pasa a C, se puede expresar tal cual con switch (SCAN), WRITE, RIGHT/LEFT y goto.
    Me da curiosidad si hay margen para reescribir esta lógica en un estilo más estructurado o aplicar otras optimizaciones.
  • Cada fila es un estado, y cada columna es el símbolo que se acaba de leer de la cinta.
    Por ejemplo, la primera fila y primera columna significa “se leyó el símbolo 0 y el estado actual es A”.
    La celda de la tabla indica la acción a realizar; 1RB significa “cambia el símbolo de la cinta a 1, muévete una celda a la derecha y luego cambia al estado B”.
    El estado Z corresponde al estado de detención.
  • En Python, basta con tener funciones L() y R() que muevan el índice de la cinta a la izquierda/derecha, crear una tabla que mapee (estado, símbolo actual) a (símbolo a escribir, función de movimiento, siguiente estado), y repetir mientras state != 'Z'.
  • Hay una explicación sencilla en https://bbchallenge.org/story#turing-machines.
    1RZ se puede entender como una transición de detención, ya que no hay reglas para el estado Z.
    En Wikipedia también hay ejemplos más detallados de tablas de estados de máquinas de Turing https://en.wikipedia.org/wiki/Turing_machine#Formal_definition, y el seguimiento de ejecución de esta máquina de Turing específica se puede ver en https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC.
  • Hice un pequeño repositorio que reúne a los actuales poseedores de récords y también muestra ejemplos de ejecución con Wolfram Language: https://datarepository.wolframcloud.com/resources/The-Busy-Beaver-Competition/.
    Parece que ahora también tendré que actualizarlo.

• Que la cita de un resultado importante de ciencias de la computación básica sea un enlace de Discord...

  • No veo por qué no debería serlo.
    La idea de que la única forma válida de anunciar resultados científicos son las llamadas revistas con revisión por pares es una reliquia de hace 200 años, cuando la comunidad científica era lo bastante pequeña como para caber dentro del número de Dunbar.
    Si todavía se sostiene es porque algunos académicos y editoriales poderosos se benefician de ello, no porque tenga ventajas reales para el avance de la ciencia.
    De hecho, es muy posible que tenga bastante responsabilidad en la crisis moderna de reproducibilidad.
    Apoyo firmemente el método científico, pero creo que la revisión por pares tradicional ya pasó hace mucho su fecha de caducidad.
    https://en.wikipedia.org/wiki/Dunbar%27s_number
  • Aun así, es un servidor público de Discord, y se puede encontrar el enlace de invitación en la esquina superior derecha de https://bbchallenge.org.
    Creo que esto se parece más a una atribución de fuente que a una cita.
    El argumento principal que respalda el resultado está reproducido en el post del blog de forma más rigurosa, así que se sostiene de manera independiente; el enlace de Discord solo aporta contexto histórico para quien tenga interés.
  • Si participas en estos chats, se siente parecido a tener una idea en el pizarrón de la sala de descanso y desarrollarla en conjunto, con la diferencia de que se puede citar la interacción.
    Si se puede reforzar con literatura en el momento adecuado, es un cambio positivo.
  • Entiendo la queja, pero buena parte de los avances impresionantes recientes en matemáticas surgieron de colaboración e iteración rápidas.
    Por ejemplo, el proyecto que mejoró la cota superior de los intervalos entre primos de Zhang; en este aspecto, puede que otras herramientas de comunicación no reemplacen fácilmente a Discord.
    Hay que ir a donde están las personas reales.
  • Encontrar números de castor afanoso más grandes se acerca más a la matemática recreativa que a algo exactamente fundacional.
    Si fuera realmente fundamental, habría pasado por revisión por pares como artículo de revista en vez de publicarse en un blog.

• Las máquinas de Turing que pueden describirse con una cantidad no demasiado grande de símbolos, como 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC, son un número limitado.
  Pero es realmente asombroso que algunas de ellas puedan ejecutar una cantidad tan absurda de pasos antes de detenerse.

  • Hay 2^60 de estas máquinas de Turing de 3 estados y 4 símbolos.
    Debería ser aún más sorprendente un término lambda de 49 bits cuya salida, es decir, su forma normal, supera el número de Graham.

• Sinceramente no entiendo esto al 100% y probablemente sean resultados con muy poca utilidad, pero me atraen más que los avances increíblemente útiles de los LLM.
  Supongo que es porque, de forma natural, me atraen más las verdades matemáticas simples que los resultados de ingeniería “complejos”.

• ¿No debería ser BB(5) > BB(3,4)?
  En https://bbchallenge.org dicen que buscan demostrar o refutar la conjetura de que BB(5) es de unos 47 millones, pero BB(3,4) parece ser mucho mayor que eso.

  • Correcto, parece que BB(3, 4) >>> BB(5, 2).
    BB(5) = BB(5, 2), y BB(3, 4) tiene 12 transiciones (3*4) en la tabla, mientras que BB(5, 2) solo tiene 10, así que no es tan sorprendente.
    Pero también parece que BB(3, 4) >> BB(6, 2).
    Como ambos tienen la misma cantidad de transiciones, en estas máquinas de Turing pequeñas parece que tener más símbolos vale bastante.