BB(3, 3) ist schwierig

• Der Beitrag diskutiert eine Turing-Maschine mit 3 Zuständen und 3 Symbolen, für die sich ein Halten nur dann beweisen lässt, wenn man ein Collatz-ähnliches Problem löst, und sagt damit aus, dass das Problem BB(3,3) genauso schwierig ist wie die Lösung dieses Collatz-ähnlichen Problems.
• Der Autor erwähnt eine Familie von Turing-Maschinen (TMs), bei denen der Nachweis von „quasihalt“ eine effiziente Simulation oder eine vollständige Lösung eines Collatz-ähnlichen Problems erfordert.
• Der Autor hat Beispiele aus dem allgemeinen Busy-Beaver-Spiel herangezogen und viele TMs gefunden, die Ergebnisse für das Busy-Beaver-Spiel liefern.
• Der Autor stellt eine TM namens „Bigfoot“ vor, die zu den verbleibenden 160 inoffiziellen Widerständlern für BB(3,3) gehört.
• Das Verhalten von Bigfoot wird so beschrieben, dass eine Collatz-ähnliche Funktion auf b und c wiederholt angewendet wird, während a die kumulierte Summe festhält.
• Der Autor verwendet die Theorie der Markow-Ketten, um das Verhalten von Bigfoot zu beschreiben, und kommt zu dem Schluss, dass Bigfoot „probviously“ niemals anhält.
• Der Autor schlägt vor, dass wir in einer von zwei Welten leben: einer, in der Bigfoot anhält, oder einer, in der es für immer läuft, und er glaubt, dass wir in der zweiten Welt leben.
• Der Autor schlägt vor, Maschinen dieser Art „Cryptids“ zu nennen, als Anspielung auf legendäre Kreaturen wie das Ungeheuer von Loch Ness oder den Chupacabra.
• Der Autor lädt zu Ideen ein, wie man dieses Problem angehen kann, und äußert die Hoffnung, dass ein Beweis für BB(3,3) weiterhin möglich ist.
• Abschließend sagt der Autor, dass es seiner Erfahrung nach bei Collatz-ähnlichen Problemen nur zwei Arten von Fragen gibt: solche, die sich relativ leicht beweisen lassen, und solche, bei denen selbst Mathematiker nicht wissen, wie man sie beweist.

[GN⁺]

Hacker-News-Kommentare

• Diskussion über die Komplexität von BB(3, 3), das als Collatz-artiges Problem bekannt ist, mit der Behauptung, dass es nicht unbedingt schwer sein muss, weil nur verzerrtes Verhalten und eine einzige Trajektorie betrachtet werden müssen.
• Diskussion über eine Turing-Maschine mit 748 Zuständen, die anhält, wenn ZFC (Zermelo-Fraenkel-Mengenlehre mit Auswahlaxiom) inkonsistent ist. Ausdruck von Verwirrung über die Implikationen, diese Maschine für BB(748)-Schritte laufen zu lassen, und über einen möglichen Widerspruch zum zweiten Unvollständigkeitssatz von Gödel.
• Lob für den Schreibstil des Autors, der klar und prägnant ist und den Lesern hilft, das Thema zu verstehen, ohne weitschweifig zu werden.
• Aufgeworfene Frage, was es bedeutet, dass BB (Busy Beaver) nicht berechenbar ist, und ob man, während BB wächst, alles beweisen muss.
• Vorschlag, dass sich alle BB(x, y)-Probleme auf Probleme wie Collatz reduzieren lassen und dass sich daher auch das Finden von BB(x, y) für bestimmte Werte von x und y auf ein Collatz-artiges Problem reduzieren lässt.
• Frage, warum Beeping Busy Beavers (BBB) schon lange vor einer deutlich längeren Laufzeit quasi anhalten können, mit dem Vorschlag, dass das daran liegen könnte, dass kein Haltezustand verwendet werden muss.
• Frage nach den Auswirkungen des Halteproblems auf Induktion in der realen Welt, mit einem hypothetischen Szenario, das ein Orakel enthält, das entscheiden kann, ob eine gegebene Turing-Maschine etwas anderes auf dem Ausgabeband ausgeben wird.
• Frage nach dem Vorwissen, das nötig ist, um diese Themen zu verstehen, und Bitte um bestimmte Themen oder Fächer, die eine gute Grundlage bieten.
• Frage, wie man die bestimmte Zeichenfolge 1RB2RA1LC_2LC1RB2RB_---2LA1LA lesen soll.