Por qué BB(3, 3) es difícil: Bigfoot
(sligocki.com)- La máquina de Turing de 3 estados y 3 símbolos Bigfoot es un caso en el que, para demostrar si se detiene o no en una cinta vacía, hay que resolver un problema tipo Collatz, lo que muestra que (BB(3, 3)) podría ser así de difícil
- Esta máquina es una de las 160 candidatas no resueltas de (BB(3, 3)) en bbchallenge.org, y está definida por la tabla de transición
1RB2RA1LC_2LC1RB2RB_---2LA1LA - Su comportamiento se reduce a reglas iterativas sobre la configuración (A(a,b,c)), donde a aumenta o disminuye según (b \bmod 6), y solo se detiene cuando (a) intentaría bajar de 0
- Desde la cinta vacía, llega a (A(2,1,2)) tras 69 pasos, y después de 24 millones de iteraciones crece hasta (a = 3,999,888), por lo que experimentalmente la posibilidad de que se detenga parece muy baja
- La secuencia de (b \bmod 6) es determinista, pero en gran escala parece una caminata aleatoria sesgada con sesgo de 2/3 hacia la derecha y 1/3 hacia la izquierda; para probar que corre para siempre, habría que demostrar que esta función tipo Collatz no alcanza la transición de parada
Por qué Bigfoot hace difícil a (BB(3, 3))
- Para demostrar si una máquina de Turing de 3 estados y 3 símbolos se detiene o no, hay que resolver un problema tipo Collatz
- Por lo tanto, resolver el problema de (BB(3, 3)) podría ser tan difícil como resolver ese problema tipo Collatz
- Paul Erdős dijo sobre los problemas tipo Collatz: “Mathematics may not be ready for such problems”
- En el texto anterior Mother of Giants se trató una familia de máquinas de Turing descubierta en la búsqueda de Busy Beaver “Beeping”
- Para esa familia, demostrar si entra en un estado similar a la detención (quasihalt) requiere simular eficientemente o resolver por completo un problema tipo Collatz
- Bigfoot es un caso encontrado no en una variante del juego, sino dentro del juego normal de Busy Beaver
Casos previos de dificultad en Busy Beaver
- Varias máquinas de Turing construidas por humanos ofrecen ejemplos en los que, para demostrar cierto valor de Busy Beaver, hay que probar otras afirmaciones matemáticas difíciles
- (BB(745)): requiere probar la consistencia de ZFC
- (BB(27)): requiere probar la Goldbach Conjecture
- (BB(15)) y (BB(5,4)): requieren probar la conjetura de Erdős de que para (n > 8), la representación en base 3 de (2^n) contiene al menos un dígito 2
- Pero esos valores de Busy Beaver están fuera del rango actualmente accesible
- En los últimos 60 años solo se han probado los valores (BB(2), BB(3), BB(4), BB(2,3)), y se sabe que (BB(6) > 10 \uparrow\uparrow 15)
- Antes de analizar Bigfoot, se pensaba que quizá (BB(3, 3)) sí podría demostrarse
Definición y origen de Bigfoot
- Esta máquina de Turing se llama Bigfoot, y su tabla de transición se define por la siguiente cadena
1RB2RA1LC_2LC1RB2RB_---2LA1LA
- Es una máquina registrada en bbchallenge
- La tabla de transición es la siguiente
| Estado | 0 | 1 | 2 |
|---|---|---|---|
| A | 1RB | 2RA | 1LC |
| B | 2LC | 1RB | 2RB |
| C | — | 2LA | 1LA |
- Bigfoot es una de las 160 holdouts informales restantes de (BB(3,3)) compartidas en el canal de Discord de bbchallenge.org
- Esta máquina de Turing en particular fue compartida por primera vez el 14 de octubre de 2023 en ese mismo canal de Discord por @savask, junto con una explicación de bajo nivel de su comportamiento
- Análisis posteriores revelaron una estructura tipo Collatz y un carácter de caminata aleatoria sesgada
Comportamiento reducido a la configuración (A(a,b,c))
- Definimos la configuración general de la siguiente manera
[ A(a, b, c) = 0^\infty ; 12^a ; 11^b ; \text{ <A } ; 11^c ; 0^\infty ]
- Si Bigfoot entra en una configuración (A(a,b,c)) con (c \ge 1), las siguientes reglas describen con precisión todo su comportamiento posterior hasta que se detenga o corra para siempre
[ \begin{array}{l} A(a, 6k, c) \to A(a, 8k+c-1, 2) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+1, c) \to A(a+1, 8k+c-1, 3) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+2, c) \to A(a-1, 8k+c+3, 2) \quad \text{if } a \ge 1 \ A(a, 6k+3, c) \to A(a, 8k+c+1, 5) \ A(a, 6k+4, c) \to A(a+1, 8k+c+3, 2) \ A(a, 6k+5, c) \to A(a, 8k+c+5, 3) \end{array} ]
[ A(0, 6k+2, c) \to \text{Halt}(16k+2c+7) ]
- Estas reglas iteran una función tipo Collatz sobre los parámetros (b) y (c)
- (a) se comporta como un valor acumulado
- si (b \equiv 1 \pmod{6}) o (b \equiv 4 \pmod{6}), (a) aumenta
- si (b \equiv 2 \pmod{6}), (a) disminuye
- Bigfoot solo se detiene cuando (a) intenta decrecer por debajo de 0
Trayectoria observada desde la cinta vacía
- Si empieza desde la cinta vacía, Bigfoot llega a la configuración (A(2,1,2)) después de 69 pasos
- En simulaciones posteriores, (a) parece aumentar de forma sostenida, y tras 24 millones de iteraciones llega a (a = 3,999,888)
- Si se asume que la secuencia de residuos de (b \bmod 6) es aleatoria uniforme, este proceso equivale a una caminata aleatoria sesgada sobre la recta numérica
- en cada paso, la probabilidad de ir a la derecha es (\frac{2}{3})
- la probabilidad de ir a la izquierda es (\frac{1}{3})
- En teoría de cadenas de Markov puede demostrarse que, si la posición actual es (a=n), la probabilidad de alcanzar (a=-1) en el futuro es ((\frac{1}{2})^{n+1})
- La secuencia real de (b \bmod 6) no es aleatoria, sino completamente determinista, y sigue de forma consistente el patrón impar·impar·par·par
- Aun así, a gran escala muestra una trayectoria parecida a la de una cadena de Markov aleatoria
- después de 24 millones de pasos, se esperaría que la cadena de Markov se moviera 8 millones de veces a la derecha y 4 millones a la izquierda
- eso queda muy cerca del valor real de (a), de alrededor de 4 millones
La heurística de que “probviously” no se detiene
- Cuando (a \approx 4,000,000), la probabilidad de que una cadena de Markov aleatoria alcance (a=-1) es aproximadamente ((\frac{1}{2})^{4,000,000})
- Ese valor es tan pequeño que, científicamente, puede tratarse como si garantizara el fracaso
- Si Bigfoot se comporta de forma similar a la cadena de Markov, parecería que no se detendrá
- Pero esto no es una afirmación matemática rigurosa, sino una heurística experimental
- No puede descartarse que Bigfoot se detenga después de un googolplex de iteraciones
- John Conway creó esta expresión para describir la heurística de que la conjetura de Collatz “probviously” debe ser cierta, aunque todavía no se ve una prueba de Collatz
Los dos posibles finales de Bigfoot
- Bigfoot es una de dos cosas
- se detiene
- corre para siempre
- Si se detiene, podría demostrarse acelerando lo suficiente la iteración de la función tipo Collatz y simulándola hasta el final
- Si corre para siempre, habría que demostrar que esta función tipo Collatz nunca alcanza la transición de parada en (a=0)
- Según la heurística de la cadena de Markov, el segundo caso parece más plausible, y también mucho más difícil de demostrar
El nombre Cryptids
- Este tipo de máquinas puede reducir su comportamiento a reglas matemáticas relativamente simples, pero esas reglas caen dentro de una clase de problemas matemáticos abiertos
- Se parecen a criaturas legendarias sobre las que solo hay rumores de que existen o no existen, sin evidencia concreta para ninguno de los dos lados
- Se propuso llamar a estas máquinas Cryptids
- Es una analogía con criaturas legendarias como Loch Ness Monster o Chupacabra
- Esta máquina de Turing recibió el nombre Bigfoot porque parece caminar al azar
¿Este comportamiento tipo Collatz realmente es difícil?
- La dinámica de esta función tipo Collatz en particular parece ser un problema que casi no se ha analizado antes
- Sigue existiendo la posibilidad de encontrar, con algo de teoría de números y cálculo, propiedades matemáticas ingeniosas que solo apliquen a este problema
- Si se descubrieran esas propiedades, sabríamos que la prueba de (BB(3,3)) todavía está dentro de un rango accesible
- Empíricamente, las preguntas que pueden hacerse sobre problemas tipo Collatz se dividen en dos clases
- preguntas que se prueban con relativa facilidad
- preguntas para las que ningún matemático conoce un método de demostración
- En Bigfoot, hechos como que (b) repite el patrón impar·impar·par·par, o que tras aplicar la regla tradicional de Collatz (3n+1) siempre se obtiene un número par que en el siguiente paso se divide entre 2, pertenecen a la primera categoría
- Casi cualquier otra pregunta sobre el comportamiento de sistemas de tipo Collatz puede verse como ejemplo de la segunda categoría
Una representación alternativa con 81 casos
- Una representación alternativa añadida el 18 de octubre de 2023 reduce la incomodidad de la descripción original con (A(a,b,c))
- La descripción original tiene tres inconvenientes
- los parámetros (b) y (c) están entrelazados
- el módulo 6 de entrada y el módulo 8 de salida comparten el factor 2
- (b) sigue un patrón repetitivo de impar·impar·par·par
- Matthew House señaló que estos problemas pueden evitarse si se define la nueva configuración así
[ B(a,b)=A(a,2b+1,2) ]
- Si se toma (b=81k+r) y se agrupan las 4 transiciones originales en una sola, el comportamiento tipo Collatz de Bigfoot puede expresarse como una regla de 81 casos
- Esta representación resuelve las tres características de la representación original con (A) y se parece más al problema clásico de Collatz
- Aun así, es algo difícil de manejar porque hay que tratar los 81 casos completos
- Algunas reglas dependen de la condición (a \ge 2)
1 comentarios
Opiniones en Hacker News
Más que decir que BB(3, 3) en sí sea difícil, parece más preciso decir que codifica problemas del estilo de Collatz, y que ese tipo de problemas en general se considera muy difícil.
Aunque que esta instancia en particular sea necesariamente difícil es otra cuestión. Su comportamiento parece bastante sesgado hacia un lado, y no hace falta revisar las trayectorias de todos los enteros como en el problema clásico de Collatz, sino solo una trayectoria única.
También estoy de acuerdo en cierta medida con lo de una sola trayectoria frente a muchas trayectorias. Pero si asumimos que esta máquina de Turing vive en un mundo donde no se detiene, demostrar la trayectoria única de este sistema puede verse como “más difícil” que una trayectoria única de la conjetura clásica de Collatz. Si la conjetura de Collatz es cierta, demostrar cualquier trayectoria única termina reduciéndose a un cálculo finito; en cambio, para la trayectoria única del artículo hay que mostrar que nunca se detiene, lo que requiere matemática más refinada.
No quiero exagerarlo. Esto no significa que para resolver BB(3, 3) haya que demostrar necesariamente la conjetura de Collatz o algún problema abierto de matemática ya muy estudiado. Aun así, me parece significativo como una especie de resultado “de segunda mejor opción”: es un problema difícil que se parece a uno muy estudiado. Qué tan difícil es este problema similar a Collatz se verá según quién pueda resolverlo.
Quiero ayudar a entender esto. Hay una máquina de Turing de 748 estados [0], y entiendo que esta máquina se detiene solo si ZFC es inconsistente.
Esta máquina es un objeto “físico” que puede implementarse y ejecutarse en una computadora. La capacidad de cómputo actual no alcanza, pero en principio no hay nada que impida ejecutar esta máquina durante BB(748) pasos. Si se detiene, por el teorema 1 habríamos demostrado que ZFC es inconsistente; si no se detiene, parecería que habríamos demostrado que ZFC es consistente.
Ese es el núcleo de mi confusión. No parece un resultado abstracto, sino un cálculo que realmente se puede realizar para obtener un valor.
Por supuesto, según el segundo teorema de incompletitud de Gödel, dentro de ZFC no se puede demostrar la consistencia de ZFC. Pero si la máquina de Turing anterior se detiene, eso parecería demostrar que ZFC es consistente, lo que suena a contradicción.
¿Dónde está el error? Mi conjetura actual es que, en la demostración del teorema 1, para mostrar que la máquina de Turing de 748 estados se detiene solo si ZFC es inconsistente, se usó una metateoría más fuerte que ZFC. En ese caso no habría contradicción. Aunque pudiéramos ejecutarla durante BB(748) pasos, eso solo mostraría que ZFC+ demuestra la consistencia de ZFC, algo ya conocido. Por ejemplo, ZFC + “existe un cardinal inaccesible” cumple ese papel.
No he leído el paper en detalle, así que no sé si realmente es así. ¿Alguien que haya pensado a fondo este problema podría aportar alguna idea?
[0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...
Si el dios de los castores afanosos nos dijera ese valor, en teoría podríamos correr la máquina de Turing durante esa cantidad de pasos y, como dices, demostrar si ZFC es consistente o no. Pero para que un humano calcule BB(748), en la práctica tendría que determinar si esta máquina de Turing específica de 748 estados se detendrá alguna vez, y también si se detienen todas las demás máquinas de Turing de 748 estados.
Incluso si construyéramos una computadora con toda la materia y energía del universo, y esa computadora hiciera solo esta tarea con la máxima eficiencia físicamente posible, no terminaría el cálculo.
Ahí aparece el punto en el que la matemática se separa de la física y de la realidad. Podemos hablar y razonar sobre esos objetos, pero ya no tienen significado físico.
Pero demostrar que no se detiene es mucho más difícil. Ejecutarla durante TREE(3) pasos no es una demostración de que no se vaya a detener en el paso TREE(3)+1.
Por eso, lamentablemente, no se puede decir “simplemente ejecútala”.
Me gustó el estilo del autor. Ayudó a entender el tema sin parecer demasiado verboso, y encontrar ese punto de equilibrio no es fácil.
Recursos relacionados: https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.... y https://googology.fandom.com/wiki/Googology_Wiki
¿Que BB sea incomputable significa algo así? Me pregunto si, a medida que BB crece, termina abarcando toda la matemática, y al final hay que demostrarlo todo.
El resto de toda la matemática se mete de contrabando dentro de BB a través del problema de la detención. Como se puede escribir un programa que se detenga solo si una conjetura matemática arbitraria es verdadera o falsa, intentar resolver el problema de la detención o BB implica tener que saber toda la matemática[0]. Esto es posible porque la completitud de Turing es la frontera de la computabilidad. Lo que puede contener una computadora es, en sí mismo, una computadora.
[0] En realidad, esto por sí solo no es lo que hace que la detención sea indecidible. La indecidibilidad viene de que un programa “se arrastra a sí mismo dentro del problema de la detención”, por ejemplo deteniéndose solo cuando un hipotético decisor de detención dice que él no se detendrá.
Hay problemas matemáticos que “sabemos” que no podemos ni demostrar ni refutar. Eso es lo que dice el primer teorema de incompletitud de Gödel, siempre que no estemos en el caso en que toda proposición pueda demostrarse tanto verdadera como falsa. Si se pudieran demostrar todas las proposiciones como verdaderas y falsas a la vez, ese sistema de demostración no serviría para nada, y demostrar algo no significaría nada, así que habría que elegir otro sistema de demostración en el que eso no ocurra. Por eso normalmente se asume el primer caso: que hay problemas que no pueden demostrarse ni refutarse. Además, el segundo teorema de incompletitud de Gödel dice que nunca podemos demostrar que estamos en ese primer caso.
Y que BB sea incomputable significa que, cuando BB crezca lo suficiente, en algún momento podrá codificar un programa que se detenga solo si es verdadero un problema que no puede demostrarse ni refutarse. Por eso no podemos demostrar si ese programa se detiene o no.
Estrictamente hablando, demostrar o refutar algo que no puede demostrarse ni refutarse equivale a demostrar una falsedad, y eso en última instancia podría usarse para “demostrar” cualquier proposición, así que decir que “abarca toda la matemática” es correcto en cierto sentido. Pero esto es una condición crítica, y entra en juego mucho antes de que aparezca una máquina de Turing lo bastante grande como para codificar “todos” los problemas matemáticos. De hecho, no existe un número finito de estados suficiente para codificar todos los problemas matemáticos, porque las cadenas aritméticas pueden seguir haciéndose cada vez más largas.
Después de eso, ya no sorprende que exista un BB que no podamos resolver; lo interesante pasa a ser investigar cuáles BB se pueden resolver y cuáles no.
No entiendo por qué es sorprendente la parte de “por lo tanto, resolver el problema BB(3, 3) es al menos tan difícil como resolver este problema similar a Collatz”. De hecho, parece demostrarse casi de manera trivial. ¿No se reducen todos los problemas BB(x, y) a problemas tipo Collatz?
BB(x, y) puede convertirse fácilmente en el problema de la detención. Se toman todas las máquinas con x estados y y símbolos, se identifican las que se detienen y se separan las que no. Luego se ejecutan juntas, un paso a la vez, todas las máquinas que se detienen hasta que todas hayan parado; el número de pasos ejecutados será el valor de BB(x, y).
Tengo entendido que Conway mostró cómo reducir el problema de la detención a problemas tipo Collatz. Entonces, con una reducción en dos pasos, de BB al problema de la detención y luego al problema de Collatz, parece que se puede reducir BB(x, y), para x e y arbitrarios, a un problema tipo Collatz.
Lo que se necesita es una reducción de Collatz al problema de la detención y luego a B(x,y). La parte de Collatz al problema de la detención es trivial, pero la del problema de la detención a B(x,y) es menos obvia. Hay que definir con precisión qué subconjunto del problema de la detención puede reducirse desde Collatz y, al mismo tiempo, no ser más difícil que B(3,3).
El problema de la detención parece “bloquear” a menudo muchas aproximaciones a la teoría algorítmica de la información y a la inducción basadas en programas computables. Pero me pregunto si hay investigación sobre si el problema de la detención tiene un impacto material en la capacidad de inducción del mundo real.
Por ejemplo, supongamos que un oráculo nos dice si una máquina de Turing universal monótona arbitraria llegó, durante su ejecución, a un punto en el que ya no escribirá nada más en la cinta de salida. ¿Los resultados de inducción usando ese oráculo serían muy distintos de los de hacer una búsqueda exhaustiva en el espacio de programas y, si un programa no produce salida durante un número n suficientemente grande de pasos, simplemente “pasar” al siguiente programa?
Hablo de inducción sobre datos comprimibles “normales”, no de casos límite fabricados a propósito como BB(3,3) ni de ejemplos adversariales.
Como investigador de seguridad, escribo fuzzers directamente. Un fuzzer es una herramienta que busca automáticamente entradas relevantes para la seguridad en el programa que se está probando. Genera y modifica entradas algorítmicamente, las pasa al programa y observa qué ocurre decenas, cientos o miles de veces por segundo.
Si una entrada hace que el programa crashee, se puede ver como que hizo que el programa “se detuviera”. Creo que, para crear un fuzzer que encuentre todos los bugs de cualquier programa en un tiempo realista, habría que resolver el problema de la detención. De hecho, incluso después de miles de millones de pruebas, sigue habiendo gente que encuentra bugs en decodificadores de imágenes, así que está claro que los fuzzers que tenemos no son perfectos.
Al mismo tiempo, en la práctica he visto que, si se les da suficiente tiempo, los fuzzers penetran más profundamente de lo esperado en programas complejos. La validación de entradas que realiza el objetivo de prueba, junto con la memoria y el almacenamiento limitados de las PCs modernas, encarrilan al fuzzer en cierta medida. La excepción es cuando entra la criptografía: para un fuzzer es como un pantano computacional. Los programas bien defendidos y bien especificados actúan como sus propias barreras de seguridad, de modo que el fuzzer no necesite resolver el problema de la detención.
Así que, en cuanto a encontrar bugs de seguridad en programas, lo veo así: salvo por la criptografía, los fuzzers son fuertes cuando apuntan a programas con validación estricta de entradas. En cambio, en programas que no tienen validación estricta de entradas, no hace tanta falta usar fuzzers, y ahí tampoco necesariamente funcionan bien.
¿Hay alguna intuición sobre por qué BBB, es decir, el castor ocupado que emite pitidos, puede ejecutarse durante mucho más tiempo antes de casi detenerse?
Algo que se ve es que, en la práctica, no necesita usar un estado de detención. En ese sentido, un BBB de 3 estados podría parecerse a un BB de 4 estados. Me pregunto si hay algo más.
Por eso se puede hacer que un programa o una máquina de Turing de tamaño X simule la ejecución de todos los programas de tamaño Y, con Y >> X. Si hacemos que emita un pitido cada vez que uno de esos programas se detiene, el último pitido ocurre al simular el caso en que BB(Y) se detiene después de más pasos que BB(Y). Por lo tanto, BBB(X) > BB(Y) >> BB(X).
Si mal no recuerdo, básicamente por la misma construcción, si se conoce BB(N) se puede calcular muy lentamente el problema de la detención para programas de tamaño menor o igual que N, mientras que si se conoce BBB(N) se puede calcular mucho más lentamente el problema de la detención para máquinas de Turing con un oráculo de detención de ese tamaño o menor.
Esto es demasiado nerd para mí.
Me pregunto qué conocimientos previos hacen falta para entender algo así. ¿Basta con saber cálculo básico? ¿Qué temas o materias concretas serían una buena base?
[1] https://www.scottaaronson.com/writings/bignumbers.html
Seguir un libro introductorio de informática teórica ayuda a entender la mayor parte. Los estudiantes de ciencias de la computación suelen verlo en primer o segundo año, y no es fácil. En mi universidad era uno de los exámenes más temidos.
El texto introductorio de Hopcroft & Ullmann es bueno. Eso sí, hay tanto contenido relacionado que conviene verlo más bien como un punto de partida.
Muchos cursos de grado de ciencias de la computación deben tener clases con materiales abiertos.
¿Cómo se debe leer
1RB2RA1LC_2LC1RB2RB_---2LA1LA?https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA
Por ejemplo, si está en el estado B y el valor de la cinta en la posición actual del cabezal es 0, escribe 2, mueve el cabezal una casilla a la izquierda y pasa al estado C.
Esos 3 caracteres indican el símbolo que se escribe, el nuevo estado y la dirección de movimiento. El estado
---es la detención.(estado, valor de la cinta)se mapea a una terna(nuevo valor de la cinta, dirección de movimiento del cabezal de la cinta, nuevo estado).[0] https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA