BB(3, 3) es difícil

• El artículo analiza una máquina de Turing de 3 estados y 3 símbolos cuya detención no puede demostrarse sin resolver un problema similar a Collatz, y por eso afirma que el problema BB(3,3) es tan difícil como resolver ese problema análogo a Collatz.
• El autor menciona una familia de máquinas de Turing (TMs) que requieren una simulación eficiente o una solución completa de un problema similar a Collatz para demostrar si son "quasihalt".
• El autor tomó ejemplos del juego general de Busy Beaver y encontró muchas TMs que aportaban resultados al juego Busy Beaver.
• El autor presenta una TM llamada "Bigfoot", que es una de las 160 resistentes no oficiales que quedan para BB(3,3).
• El comportamiento de Bigfoot se describe como la iteración de una función similar a Collatz sobre b y c, mientras que a mantiene la suma acumulada.
• El autor usa la teoría de cadenas de Markov para describir el comportamiento de Bigfoot y concluye que Bigfoot "probviously" nunca se detiene.
• El autor propone que vivimos en uno de dos mundos: uno donde Bigfoot se detiene y otro donde corre para siempre, y cree que vivimos en el segundo.
• El autor propone llamar a este tipo de máquinas "Cryptids", trazando una analogía con criaturas legendarias como el monstruo del Lago Ness o el Chupacabra.
• El autor invita ideas sobre cómo atacar este problema y expresa la esperanza de que una prueba de BB(3,3) siga siendo posible.
• El autor concluye que, según su experiencia, las preguntas que pueden hacerse sobre problemas similares a Collatz caen en dos tipos: las relativamente fáciles de demostrar y aquellas que ni los matemáticos saben cómo demostrar.

[GN⁺]

Comentarios en Hacker News

• Debate sobre la complejidad de BB(3, 3), conocido como un problema tipo Collatz, pero con el argumento de que quizá no necesariamente sea difícil debido a que hay que considerar un comportamiento sesgado y solo una trayectoria.
• Discusión sobre una máquina de Turing de 748 estados que se detiene si ZFC (teoría de conjuntos de Zermelo-Fraenkel con el axioma de elección) es inconsistente. Se expresa confusión sobre las implicaciones de ejecutar esta máquina en el paso BB(748) y una posible contradicción con el segundo teorema de incompletitud de Gödel.
• Elogio al estilo de escritura del autor por ser claro y conciso, lo que ayuda a los lectores a entender el tema sin volverse verboso.
• Se plantea una pregunta sobre qué significa que BB (Busy Beaver) sea no computable y si, a medida que BB crece, eso implica que habría que demostrarlo todo.
• Sugerencia de que todos los problemas BB(x, y) pueden reducirse a problemas como Collatz y, por lo tanto, encontrar BB(x, y) para cualquier valor de x e y también puede reducirse a un problema tipo Collatz.
• Pregunta sobre por qué los Beeping Busy Beavers (BBB) pueden cuasi-detenerse mucho antes de ejecutar por mucho más tiempo, con la sugerencia de que podría deberse a que no necesitan usar un estado de detención.
• Duda sobre el impacto del problema de la detención en la inducción del mundo real, con un escenario hipotético que incluye un oráculo capaz de decidir si una máquina de Turing dada imprimirá algo distinto en la cinta de salida.
• Pregunta sobre los conocimientos previos necesarios para entender estos temas, con una solicitud de temas o materias específicas que den una buena base.
• Pregunta sobre cómo debe leerse la cadena específica 1RB2RA1LC_2LC1RB2RB_---2LA1LA.