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

(sligocki.com)

1 puntos por GN⁺ 2024-05-25 | 1 comentarios | Compartir por WhatsApp

BB(3, 4) > Ack(14)

22 de mayo de 2024
- Pavel descubrió una máquina de Turing (Turing Machine, TM) de 3 estados y 4 símbolos
- Esta máquina calcula una función de "nivel Ackermann" y se detiene con exactamente (2↑155)+14 símbolos no cero
- Como la notación de flechas ascendentes de Knuth se vuelve algo incómoda, esto puede aproximarse así: BB(3,4)>Ack(14)
- Aquí Ack(14) se define como el 14.º número de Ackermann: Ack(n)=n↑nn
- Esta es la primera TM encontrada "en estado salvaje" que puede simular una función de nivel Ackermann

Máquina

Tabla de transición de estados

| 0   | 1   | 2   | 3   |
| --- | --- | --- | --- |
| A   | 1RB | 3LB | 1RZ | 2RA |
| B   | 2LC | 3RB | 1LC | 2RA |
| C   | 3RB | 1LB | 3LC | 2RC |

Configuración final
- 0∞32g153(0)+12161 Z> 0∞
- Exactamente σ=2g153(0)+18=(2↑155)+14 símbolos no cero permanecen en la cinta

Attribution

Descubridor
- Esta TM fue descubierta por Pavel Kropitz(@uni) y compartida en Discord el 25 de abril de 2024
- Su código no podía especificar un límite legible por humanos para la puntuación de la TM, y simplemente se indicó como Halt(SuperPowers(13))
- Comenzó a verificar este resultado usando un nuevo "validador de pruebas inductivas"
- El 20 de mayo de 2024 extrajo la definición exacta de gkn(m) y obtuvo el límite σ>2↑153
- Matthew House(@LegionMammal978) encontró el 22 de mayo de 2024 una forma cerrada simple para gkn(0)=2↑k(n+2)2−2

Análisis

Definición de B(k,n,m)
```
B(k,n,m)=0∞32m+12k A> 1n
```

Prueba

0∞A>0∞→241B(16,3,0)20∞
B(k,n,m)→B(k,0,gk−1n(m)) if k≥1
B(k,0,m)2→10∞32m+12k1Z>

Definición de gk(m)
```
g0(m)=m+1
gk+1(m)=gk2m+2(0)
```

Prueba por doble inducción

Regla principal
```
B(k,n,m)→B(k,0,gk−1n(m))
```
Lema 1
```
For all k≥1: 32k<B→2k+12k<B1
```

Corolario 2

For all k≥1,m≥0: 3m2k<B→(2k+1)m2k<B1m

Teorema 3

For all k≥1,n≥0,m≥0: B(k,n,m)→B(k,0,gk−1n(m))

Valor exacto

Teorema

For all k≥0,m≥0: 2gk+1(m)+4=2↑k(2m+4)

Corolario

For all k≥0,n≥0: 2gkn(0)+4=2↑k(n+2)

Conclusión
```
σ=2g153(0)+18=(2↑155)+14
```

Permutations

Comenzando desde el estado B
```
σB=2g63(0)+9=(2↑65)+5
```

Comenzando desde el estado C

σC=2g03(0)+3=(2↑05)−1=9 (se detiene en 72 pasos)

TNF transformada

| 0   | 1   | 2   | 3   |
| --- | --- | --- | --- |
| A   | 1RB | 3RB | 1LC | 2LA |
| B   | 2LA | 2RB | 1LB | 3RA |
| C   | 3LA | 1RZ | 1LC | 2RA |

Not Collatz

Puntos interesantes
- Esta TM es sorprendentemente simple
- No tiene reglas tipo Collatz
- Esto no descarta la posibilidad de que exista una TM de nivel Ackermann tipo Collatz

Inductive Proof Validator

Objetivo del proyecto
- Está desarrollando un validador de "pruebas inductivas"
- Está desarrollando un formato de certificado estandarizado para poder verificar varias pruebas inductivas
- Aún está en una etapa temprana, pero ya logró demostrar el comportamiento de varias TM

Opinión de GN⁺

Puntos interesantes
- Este artículo ayuda mucho a entender la complejidad de las máquinas de Turing y de la función de Ackermann
- Resulta atractivo que reglas simples puedan realizar cálculos complejos
Perspectiva crítica
- Para entender la complejidad de esta máquina se necesita base matemática
- Está más enfocada en el interés teórico que en aplicaciones prácticas
Tecnologías relacionadas
- El validador de pruebas inductivas podría contribuir mucho al desarrollo de sistemas automatizados de demostración matemática
- También podría aplicarse a otros problemas de cálculo complejos
Consideraciones
- Al adoptar esta tecnología, hay que considerar la precisión y la eficiencia del proceso de verificación
- Entender y aplicar conceptos matemáticos complejos requiere tiempo

1 comentarios

GN⁺ 2024-05-25

Comentarios de Hacker News

Resumen de comentarios de Hacker News

Programa simple de máquina de Turing
A diferencia de la idea de que un programa de máquina de Turing sería un código espagueti complejo, este nuevo programa es relativamente simple. Tiene tres estados (A, B, C), y el estado B transfiere el control a A y C, pero A y C no se conocen entre sí y solo transfieren el control a B. Esta es una estructura modular; en un verdadero código espagueti, cada estado podría transferir el control a todos los demás estados.
Características interesantes
Este programa no imprime espacios en blanco, y todas las instrucciones cambian el estado o el color. El nuevo poseedor del récord BB(3,4) tiene aproximadamente 64 bits de información. BBλ(49) con 49 bits supera por mucho al número de Graham.
Ejemplo de implementación
Tras implementarlo directamente, el estado B cambia 0 a 2 y 1 a 1, luego cambia a C, mientras que el estado C cambia 3 a 2 y luego cambia a A. Esto hace que las secuencias de 3 crezcan exponencialmente en longitud.
Similitud con el code golf
Todo esto parece code golf extremo. Un proyecto personal llamado BitGrid solo tiene un estado de 4 bits por celda, y una cuadrícula de 4x4 puede contar hasta un máximo de 2^64. En cuadrículas pequeñas, la conexión de los bordes tiene un gran impacto en el resultado.
Solicitud de material para interpretar la máquina de Turing
Se solicita material sobre cómo interpretar la tabla. Parece ser una descripción de una máquina de Turing.
Límites de la máquina de Turing
La cantidad de máquinas de Turing que pueden describirse con un número limitado de símbolos es finita. Resulta sorprendente que algunas máquinas de Turing puedan ejecutar una cantidad enorme de pasos antes de detenerse.
Solicitud de explicación sobre qué tiene de especial
Se pide una explicación de por qué este conjunto específico de instrucciones es impresionante. También hay curiosidad sobre qué es una función del nivel de la función de Ackermann y qué calcula realmente.
Interés por las verdades matemáticas
Un resultado que parece inútil resulta más interesante que avances muy útiles en LLM, porque existe una atracción natural por las verdades matemáticas simples.
Comparación entre BB(5) y BB(3,4)
Se pregunta si BB(5) es mayor que BB(3,4). En el sitio bbchallenge.org, BB(5) figura como alrededor de 47 millones, pero se dice que BB(3,4) es mucho mayor.
Contexto aportado por el autor
Se valora que el autor haya aportado algo de contexto.