BB(3, 3) est difficile

• L’article traite de machines de Turing à 3 états et 3 symboles dont il est impossible de prouver l’arrêt sans résoudre un problème analogue à celui de Collatz, ce qui signifie que le problème BB(3,3) est aussi difficile que la résolution de ce problème de type Collatz.
• L’auteur mentionne une famille de machines de Turing (TM) qui exigent une simulation efficace ou une résolution complète d’un problème analogue à Collatz pour prouver leur caractère de « quasihalt ».
• L’auteur a trouvé des exemples dans le jeu classique du Busy Beaver et a découvert de nombreuses TM qui apportent des résultats à ce jeu.
• L’auteur présente une TM appelée « Bigfoot », qui fait partie des 160 résistants informels restants de BB(3,3).
• Le comportement de Bigfoot est décrit comme l’itération d’une fonction de type Collatz sur b et c, tandis que a conserve la somme cumulée.
• L’auteur utilise la théorie des chaînes de Markov pour décrire le comportement de Bigfoot et conclut qu’il est « probviously » qu’elle ne s’arrête jamais.
• L’auteur suggère que nous vivons dans l’un de deux mondes possibles : un monde où Bigfoot s’arrête, ou un monde où elle s’exécute pour toujours, et il pense que nous vivons dans le second.
• L’auteur propose d’appeler ce type de machines des « Cryptids », en référence à des créatures légendaires comme le monstre du Loch Ness ou le Chupacabra.
• L’auteur invite à proposer des idées sur la manière d’attaquer ce problème et exprime l’espoir qu’une preuve de BB(3,3) reste possible.
• L’auteur conclut qu’à son expérience, les questions qu’on peut poser sur les problèmes de type Collatz se répartissent en deux catégories : celles qui sont relativement faciles à prouver, et celles que même les mathématiciens ne savent pas démontrer.

[GN⁺]

Commentaires sur Hacker News

• Discussion sur la complexité de BB(3, 3), présenté comme un problème de type Collatz, mais avec l’argument qu’il n’est pas nécessairement difficile en raison de son comportement biaisé et du fait qu’il suffit de considérer une seule trajectoire.
• Discussion autour d’une machine de Turing à 748 états, qui s’arrête si ZFC (théorie des ensembles de Zermelo-Fraenkel avec l’axiome du choix) est incohérente. Expression d’une confusion quant aux implications de l’exécution de cette machine pendant BB(748) étapes et à une contradiction potentielle avec le deuxième théorème d’incomplétude de Gödel.
• Éloges sur le style d’écriture de l’auteur, jugé clair et concis, aidant les lecteurs à comprendre le sujet sans longueurs.
• Question sur le sens du fait que BB (Busy Beaver) soit non calculable, et sur la nécessité de tout démontrer à mesure que BB croît.
• Suggestion selon laquelle tous les problèmes BB(x, y) peuvent être réduits à des problèmes de type Collatz, et que, par conséquent, trouver BB(x, y) pour certaines valeurs de x et y peut lui aussi se réduire à un problème de type Collatz.
• Question sur la raison pour laquelle les Beeping Busy Beavers (BBB) peuvent quasi-s’arrêter bien avant de s’exécuter beaucoup plus longtemps, avec l’hypothèse que cela pourrait venir du fait qu’ils n’ont pas besoin d’utiliser un état d’arrêt.
• Interrogation sur l’impact du problème de l’arrêt sur l’induction dans le monde réel, avec un scénario hypothétique incluant un oracle capable de déterminer si une machine de Turing donnée produira autre chose sur sa bande de sortie.
• Question sur les connaissances préalables nécessaires pour comprendre ces sujets, avec une demande de thèmes ou de matières spécifiques offrant de bonnes bases.
• Question sur la manière de lire la chaîne spécifique 1RB2RA1LC_2LC1RB2RB_---2LA1LA.