Warum BB(3, 3) schwierig ist: Bigfoot
(sligocki.com)- Die 3-Zustands-3-Symbol-Turingmaschine Bigfoot ist ein Fall, bei dem man zur Beweisführung über das Halten auf leerem Band ein Collatz-ähnliches Problem lösen muss, und zeigt damit, dass auch (BB(3, 3)) entsprechend schwierig sein könnte
- Diese Maschine ist einer der 160 ungelösten Kandidaten für (BB(3, 3)) auf bbchallenge.org und wird durch die Übergangstabelle
1RB2RA1LC_2LC1RB2RB_---2LA1LAdefiniert - Ihr Verhalten reduziert sich auf iterative Regeln der Konfiguration (A(a,b,c)), wobei a je nach (b \bmod 6) zu- oder abnimmt und nur dann anhält, wenn (a) unter 0 fallen würde
- Vom leeren Band aus erreicht sie nach 69 Schritten (A(2,1,2)) und wächst nach 24 Millionen Iterationen bis auf (a = 3,999,888), sodass die Wahrscheinlichkeit eines Haltens experimentell extrem gering erscheint
- Die Folge von (b \bmod 6) ist deterministisch, wirkt im großen Verlauf aber wie ein verzerrter Random Walk mit 2/3 nach rechts und 1/3 nach links; um ewiges Laufen zu beweisen, müsste man zeigen, dass diese Collatz-ähnliche Funktion den Halteübergang nie erreicht
Warum Bigfoot (BB(3, 3)) schwierig macht
- Um das Halten einer einzelnen 3-Zustands-3-Symbol-Turingmaschine zu beweisen, muss man ein Collatz-ähnliches Problem lösen
- Daher könnte das Lösen von (BB(3, 3)) genauso schwer sein wie das Lösen dieses Collatz-ähnlichen Problems
- Paul Erdős sagte über Collatz-artige Probleme einmal: “Mathematics may not be ready for such problems”
- Im früheren Artikel Mother of Giants ging es um eine Familie von Turingmaschinen, die bei der „Beeping“-Busy-Beaver-Suche gefunden wurde
- Um bei dieser Familie Quasi-Halten (quasihalt) nachzuweisen, muss man entweder ein Collatz-ähnliches Problem effizient simulieren oder vollständig lösen
- Bigfoot ist kein Fall aus einem Variantenspiel, sondern wurde innerhalb des gewöhnlichen Busy Beaver-Spiels gefunden
Frühere Beispiele für die Schwierigkeit von Busy Beaver
- Mehrere von Menschen konstruierte Turingmaschinen liefern Beispiele, bei denen zum Beweis bestimmter Busy-Beaver-Werte andere schwierige mathematische Aussagen bewiesen werden müssen
- (BB(745)): Ein Beweis der Konsistenz von ZFC ist nötig
- (BB(27)): Ein Beweis der Goldbachschen Vermutung ist nötig
- (BB(15)) und (BB(5,4)): Ein Beweis der Erdős-Vermutung ist nötig, dass für (n > 8) die Darstellung von (2^n) zur Basis 3 mindestens eine Ziffer 2 enthält
- Solche Busy-Beaver-Werte liegen jedoch außerhalb des derzeit praktisch erreichbaren Bereichs
- In den vergangenen 60 Jahren wurden nur (BB(2), BB(3), BB(4), BB(2,3)) bewiesen, und es ist bekannt, dass (BB(6) > 10 \uparrow\uparrow 15) gilt
- Vor der Analyse von Bigfoot hielt man es für möglich, (BB(3, 3)) zu beweisen
Definition und Herkunft von Bigfoot
- Diese Turingmaschine trägt den Namen Bigfoot und ihre Übergangstabelle wird durch die folgende Zeichenkette definiert
1RB2RA1LC_2LC1RB2RB_---2LA1LA
- Es handelt sich um die bei bbchallenge registrierte Maschine
- Die Übergangstabelle lautet wie folgt
| Zustand | 0 | 1 | 2 |
|---|---|---|---|
| A | 1RB | 2RA | 1LC |
| B | 2LC | 1RB | 2RB |
| C | — | 2LA | 1LA |
- Bigfoot ist einer der 160 verbliebenen inoffiziellen Holdouts für (BB(3,3)), die im Discord-Kanal von bbchallenge.org geteilt wurden
- Diese spezielle Turingmaschine wurde am 14. Oktober 2023 erstmals im selben Discord-Kanal von @savask zusammen mit einer Beschreibung ihres Verhaltens auf niedriger Ebene geteilt
- Spätere Analysen legten die Collatz-ähnliche Struktur und den Charakter eines verzerrten Random Walk offen
Verhalten, das sich auf die Konfiguration (A(a,b,c)) reduziert
- Die allgemeine Konfiguration sei wie folgt definiert
[ A(a, b, c) = 0^\infty ; 12^a ; 11^b ; \text{ <A } ; 11^c ; 0^\infty ]
- Wenn Bigfoot in eine Konfiguration (A(a,b,c)) mit (c \ge 1) eintritt, beschreiben die folgenden Regeln das weitere Verhalten exakt, bis sie entweder anhält oder für immer weiterläuft
[ \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) ]
- Diese Regeln iterieren eine Collatz-ähnliche Funktion über die Parameter (b) und (c)
- (a) verhält sich dabei wie ein Akkumulator
- Wenn (b \equiv 1 \pmod{6}) oder (b \equiv 4 \pmod{6}), dann steigt (a)
- Wenn (b \equiv 2 \pmod{6}), dann fällt (a)
- Bigfoot hält nur dann an, wenn (a) unter 0 sinken würde
Beobachtete Trajektorie vom leeren Band aus
- Startet man vom leeren Band, erreicht Bigfoot nach 69 Schritten die Konfiguration (A(2,1,2))
- In anschließenden Simulationen scheint (a) dann stetig zu wachsen und erreicht nach 24 Millionen Iterationen den Wert (a = 3,999,888)
- Nimmt man an, dass die Restklassenfolge von (b \bmod 6) gleichverteilt zufällig ist, dann entspricht dieser Prozess einem verzerrten Random Walk auf der Zahlengeraden
- In jedem Schritt beträgt die Wahrscheinlichkeit für einen Schritt nach rechts (\frac{2}{3})
- Die Wahrscheinlichkeit für einen Schritt nach links beträgt (\frac{1}{3})
- Mit der Theorie der Markov-Ketten kann man beweisen, dass ausgehend von der aktuellen Position (a=n) die spätere Wahrscheinlichkeit, (a=-1) zu erreichen, gleich ((\frac{1}{2})^{n+1}) ist
- Die tatsächliche Folge von (b \bmod 6) ist nicht zufällig, sondern vollständig deterministisch und folgt konsequent dem Muster ungerade, ungerade, gerade, gerade
- Dennoch zeigt sie im großen Maßstab eine Trajektorie, die einer zufälligen Markov-Kette ähnelt
- Nach 24 Millionen Schritten würde man bei der Markov-Kette 8 Millionen Schritte nach rechts und 4 Millionen nach links erwarten
- Das liegt sehr nahe am tatsächlichen (a)-Wert von etwa 4 Millionen
Die Heuristik, dass sie „probviously“ nicht anhält
- Bei (a \approx 4{,}000{,}000) liegt die Wahrscheinlichkeit, dass die zufällige Markov-Kette jemals (a=-1) erreicht, ungefähr bei ((\frac{1}{2})^{4{,}000{,}000})
- Diese Zahl ist so klein, dass man wissenschaftlich fast von garantiertem Scheitern sprechen würde
- Wenn Bigfoot ähnlich wie die Markov-Kette arbeitet, scheint sie nicht anzuhalten
- Das ist jedoch keine strenge mathematische Aussage, sondern eine experimentelle Heuristik
- Es bleibt möglich, dass Bigfoot erst nach googolplex Iterationen anhält
- John Conway prägte diesen Ausdruck, um die Heuristik zu beschreiben, dass die Collatz-Vermutung „probviously“ wahr sei, doch ein Beweis ist weiterhin nicht in Sicht
Zwei mögliche Enden für Bigfoot
- Für Bigfoot gibt es nur zwei Möglichkeiten
- Sie hält an
- Sie läuft für immer weiter
- Falls sie anhält, könnte man das beweisen, indem man die Iteration der Collatz-ähnlichen Funktion ausreichend beschleunigt und bis zum Ende simuliert
- Falls sie für immer weiterläuft, muss man beweisen, dass diese Collatz-ähnliche Funktion den Halteübergang bei (a=0) niemals erreicht
- Nach der Markov-Ketten-Heuristik wirkt der zweite Fall plausibler, und genau dieser scheint viel schwerer zu beweisen zu sein
Der Name Cryptids
- Solche Maschinen lassen sich auf relativ einfache mathematische Regeln reduzieren, doch diese Regeln fallen in die Klasse offener mathematischer Probleme
- Das ähnelt legendären Kreaturen, von denen man nur Gerüchte hört, dass sie existieren oder nicht existieren, ohne dass eine Seite konkrete Belege vorlegen kann
- Als Bezeichnung für solche Maschinen wurde Cryptids vorgeschlagen
- Das ist eine Anspielung auf legendäre Kreaturen wie das Ungeheuer von Loch Ness oder den Chupacabra
- Diese Turingmaschine erhielt den Namen Bigfoot, weil sie wirkt, als würde sie zufällig umherlaufen
Ist dieses Collatz-ähnliche Verhalten wirklich schwer?
- Die Dynamik dieser speziellen Collatz-ähnlichen Funktion scheint ein Problem zu sein, das bisher kaum analysiert wurde
- Es bleibt möglich, mit etwas Zahlentheorie und Rechnerei geschickte mathematische Eigenschaften zu finden, die nur für dieses Problem gelten
- Würde man solche Eigenschaften entdecken, wüsste man, dass ein Beweis für (BB(3,3)) möglicherweise noch in einem erreichbaren Bereich liegt
- Fragen, die man über Collatz-ähnliche Probleme stellen kann, lassen sich empirisch in zwei Arten einteilen
- Fragen, die sich vergleichsweise trivial beweisen lassen
- Fragen, für die kein Mathematiker eine Beweismethode kennt
- Dass bei Bigfoot (b) das Muster ungerade, ungerade, gerade, gerade wiederholt, oder dass nach Anwendung der klassischen (3n+1)-Collatz-Regel immer eine gerade Zahl entsteht, die im nächsten Schritt durch 2 geteilt wird, gehört zur ersten Kategorie
- Fast alle anderen Fragen zum Verhalten von Collatz-Systemen lassen sich als Beispiele der zweiten Kategorie betrachten
Alternative Darstellung mit 81 Fällen
- Eine am 18. Oktober 2023 ergänzte alternative Darstellung reduziert einige Unbequemlichkeiten der bisherigen Beschreibung mit (A(a,b,c))
- Die bisherige Beschreibung hat drei Unbequemlichkeiten
- Die Parameter (b) und (c) sind miteinander verknüpft
- Der Eingabemodulo 6 und der Ausgabemodulo 8 haben den gemeinsamen Faktor 2
- (b) folgt dem wiederholten Muster ungerade, ungerade, gerade, gerade
- Matthew House wies darauf hin, dass sich diese Probleme vermeiden lassen, wenn man die neue Konfiguration wie folgt definiert
[ B(a,b)=A(a,2b+1,2) ]
- Setzt man (b=81k+r) und fasst die vier ursprünglichen Übergänge zu einem einzigen zusammen, lässt sich Bigfoots Collatz-ähnliches Verhalten als Regelwerk mit 81 Fällen ausdrücken
- Diese Darstellung löst die drei Eigenschaften der bisherigen (A)-Darstellung und wirkt dem klassischen Collatz-Problem ähnlicher
- Allerdings ist sie etwas unhandlich, weil man alle 81 Fälle behandeln muss
- Einige Regeln hängen von der Bedingung (a \ge 2) ab
1 Kommentare
Meinungen auf Hacker News
Es scheint treffender zu sagen, dass BB(3, 3) nicht an sich schwierig ist, sondern ein Collatz-artiges Problem kodiert und dass solche Probleme im Allgemeinen als sehr schwierig gelten.
Ob diese konkrete Instanz unbedingt schwierig ist, ist allerdings eine andere Frage. Ihr Verhalten wirkt ziemlich einseitig, und anders als beim klassischen Collatz-Problem muss man nicht die Bahnen aller ganzen Zahlen betrachten, sondern nur eine einzelne Bahn.
Dem Punkt einzelne Bahn versus viele Bahnen stimme ich bis zu einem gewissen Grad ebenfalls zu. Wenn man jedoch annimmt, dass diese Turingmaschine in einer Welt läuft, in der sie nicht anhält, kann der Beweis für die einzelne Bahn dieses Systems als „schwieriger“ gelten als eine einzelne Bahn bei der klassischen Collatz-Vermutung. Wenn die Collatz-Vermutung wahr ist, genügt für den Beweis einer beliebigen einzelnen Bahn letztlich eine endliche Berechnung; bei der einzelnen Bahn aus dem Artikel muss man dagegen zeigen, dass sie für immer nicht anhält, wofür ausgefeiltere Mathematik nötig ist.
Ich möchte nicht übertreiben. Das bedeutet nicht, dass man zum Lösen von BB(3, 3) zwingend die Collatz-Vermutung oder ein bereits gut untersuchtes offenes Problem der Mathematik beweisen müsste. Trotzdem halte ich es zumindest für ein sinnvolles „zweitbestes“ Ergebnis, dass es sich um ein schwieriges Problem handelt, das einem gut erforschten Problem ähnelt. Wie schwierig dieses Collatz-ähnliche Problem wirklich ist, wird man wohl daran sehen, wer es lösen kann.
Ich möchte das hier besser verstehen. Es gibt eine Turingmaschine mit 748 Zuständen [0], und ich verstehe es so, dass diese Maschine nur dann anhält, wenn ZFC widersprüchlich ist.
Diese Maschine ist ein „physisches“ Objekt, das man auf einem Computer implementieren und ausführen kann. Die heutige Rechenleistung reicht zwar nicht aus, aber prinzipiell hindert nichts daran, diese Maschine für BB(748) Schritte laufen zu lassen. Hält sie an, hat man nach Satz 1 bewiesen, dass ZFC widersprüchlich ist; hält sie nicht an, scheint man bewiesen zu haben, dass ZFC konsistent ist.
Das ist der Kern meiner Verwirrung. Es wirkt nicht wie ein abstraktes Resultat, sondern wie eine Berechnung, die man tatsächlich ausführen und deren Wert man erhalten kann.
Natürlich kann nach Gödels zweitem Unvollständigkeitssatz ZFC innerhalb von ZFC seine eigene Konsistenz nicht beweisen. Wenn die obige Turingmaschine aber nicht anhält, hätte man damit scheinbar die Konsistenz von ZFC bewiesen, was wie ein Widerspruch aussieht.
Wo liegt der Fehler? Meine derzeitige Vermutung ist, dass im Beweis von Satz 1 eine Metatheorie, die stärker als ZFC ist, verwendet wurde, um zu zeigen, dass die Turingmaschine mit 748 Zuständen nur dann anhält, wenn ZFC widersprüchlich ist. Dann wäre es kein Widerspruch. Selbst wenn man sie BB(748) Schritte laufen lassen könnte, würde das nur zeigen, dass ZFC+ die Konsistenz von ZFC beweist, was bereits bekannt ist. Zum Beispiel kann ZFC + „es existiert eine unerreichbare Kardinalzahl“ eine solche Rolle spielen.
Ich habe die Arbeit nicht im Detail gelesen, daher weiß ich nicht, ob das tatsächlich der Fall ist. Kann jemand, der sich intensiver mit diesem Problem beschäftigt hat, dazu Einsichten geben?
[0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...
Wenn der Busy-Beaver-Gott uns diesen Wert verriete, könnten wir die Turingmaschine theoretisch so lange laufen lassen und, wie gesagt, die Frage der Konsistenz von ZFC entscheiden. Aber damit ein Mensch BB(748) berechnen kann, müsste er im Grunde herausfinden, ob genau diese Turingmaschine mit 748 Zuständen irgendwann anhält – und ob alle anderen Turingmaschinen mit 748 Zuständen anhalten.
Selbst wenn wir aus aller Materie und Energie des Universums einen Computer bauen würden und dieser Computer nur diese eine Aufgabe mit der physikalisch höchstmöglichen Effizienz ausführte, würde er die Berechnung nicht beenden können.
An diesem Punkt trennen sich Mathematik und physikalische Realität. Man kann über solche Objekte sprechen und über sie folgern, aber sie haben keine physikalische Bedeutung mehr.
Aber zu beweisen, dass sie nicht anhält, ist viel schwieriger. Selbst wenn man sie TREE(3) Schritte lang ausführt, ist das kein Beweis dafür, dass sie nicht bei Schritt TREE(3)+1 anhält.
Deshalb kann man leider nicht sagen: „Einfach laufen lassen.“
Mir gefiel der Stil des Autors. Er half dabei, das Thema zu verstehen, ohne weitschweifig zu wirken, und diesen Balancepunkt zu treffen ist nicht leicht.
Verwandte Ressourcen: https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.... und https://googology.fandom.com/wiki/Googology_Wiki
Bedeutet die Aussage, dass BB nicht berechenbar ist, so etwas? Dass BB, je größer es wird, die gesamte Mathematik in sich aufnimmt und man am Ende alles beweisen müsste?
Der Rest der gesamten Mathematik wird über das Halteproblem in BB hineingeschmuggelt. Man kann ein Programm schreiben, das nur dann anhält, wenn eine beliebige mathematische Vermutung wahr oder falsch ist; daher muss man die gesamte Mathematik kennen, wenn man das Halteproblem oder BB lösen will[0]. Das ist möglich, weil Turing-Vollständigkeit die Grenze der Berechenbarkeit markiert. Was einen Computer enthalten kann, ist selbst ein Computer.
[0] Genau genommen ist das an sich nicht der Grund, warum das Halten unentscheidbar ist. Die Unentscheidbarkeit entsteht daraus, dass ein Programm „sich selbst in das Halteproblem hineinzieht“, etwa indem ein hypothetischer Halteentscheider genau dann anhält, wenn er sagt, dass es nicht anhalten wird.
Es gibt mathematische Probleme, von denen wir „wissen“, dass wir sie weder beweisen noch widerlegen können. Sofern nicht jeder Satz sowohl als wahr als auch als falsch beweisbar ist, ist genau das der Inhalt von Gödels erstem Unvollständigkeitssatz. Wenn man jeden Satz sowohl als wahr als auch als falsch beweisen könnte, wäre dieses Beweissystem nutzlos, und Beweisen hätte keinerlei Bedeutung; dann müsste man ein anderes Beweissystem wählen, in dem das nicht passiert. Deshalb nimmt man normalerweise den ersten Fall an: dass es also Probleme gibt, die sich weder beweisen noch widerlegen lassen. Zusätzlich besagt Gödels zweiter Unvollständigkeitssatz, dass wir niemals beweisen können, dass wir uns tatsächlich im ersten Fall befinden.
Und dass BB nicht berechenbar ist, bedeutet: Wenn BB groß genug wird, kann es irgendwann ein Programm kodieren, das genau dann anhält, wenn ein Problem wahr ist, das weder bewiesen noch widerlegt werden kann. Daher kann man nicht beweisen, ob dieses Programm anhält oder nicht.
Streng genommen liefe es darauf hinaus, Falsches zu beweisen, wenn man etwas beweisen oder widerlegen würde, das weder beweisbar noch widerlegbar ist; und das ließe sich letztlich dazu verwenden, jede Aussage zu „beweisen“. Insofern stimmt die Aussage, dass es „die gesamte Mathematik umfasst“, in gewissem Sinn. Allerdings ist das eine Schwellenbedingung und greift schon lange bevor eine Turingmaschine groß genug ist, um „alle“ mathematischen Probleme zu kodieren. Tatsächlich gibt es keine endliche Zahl von Zuständen, die ausreichen würde, um alle mathematischen Probleme zu kodieren, weil arithmetische Zeichenketten immer weiter verlängert werden können.
Danach ist es nicht überraschend, dass es BB-Werte gibt, die wir nicht lösen können; interessant wird dann die Untersuchung, welche BB-Werte lösbar sind und welche nicht.
Ich verstehe nicht, warum die Stelle „Daher ist das Lösen des Problems BB(3, 3) mindestens so schwer wie das Lösen dieses Collatz-ähnlichen Problems“ überraschend sein soll. Eigentlich wirkt das fast trivial beweisbar. Lassen sich nicht alle BB(x, y)-Probleme auf Collatz-artige Probleme reduzieren?
BB(x, y) lässt sich leicht in ein Halteproblem umwandeln. Man findet unter allen Maschinen mit x Zuständen und y Symbolen diejenigen, die anhalten, und legt die nicht haltenden beiseite. Dann führt man alle haltenden Maschinen gemeinsam jeweils einen Schritt weiter aus, bis alle angehalten haben; die Zahl der ausgeführten Schritte ist dann der Wert von BB(x, y).
Soweit ich weiß, hat Conway eine Methode angegeben, das Halteproblem auf Collatz-artige Probleme zu reduzieren. Dann scheint man mit einer zweistufigen Reduktion von BB zum Halteproblem und weiter zum Collatz-Problem BB(x, y) für beliebige x, y auf Collatz-artige Probleme reduzieren zu können.
Benötigt wird eine Reduktion von Collatz zum Halteproblem und dann weiter zu B(x,y). Von Collatz zum Halteproblem zu gehen ist trivial, aber vom Halteproblem zu B(x,y) ist weniger trivial. Man muss genau definieren, welche Teilmenge des Halteproblems sich von Collatz aus reduzieren lässt und trotzdem nicht schwieriger als B(3,3) ist.
Das Halteproblem scheint viele Ansätze der algorithmischen Informationstheorie und der Induktion, die auf berechenbaren Programmen beruhen, häufig zu „blockieren“. Ich frage mich aber, ob es Forschung dazu gibt, ob das Halteproblem die Induktionsfähigkeit in der realen Welt materiell beeinflusst.
Angenommen etwa, ein Orakel sagt uns, ob eine beliebige monotone universelle Turingmaschine während ihrer Ausführung einen Punkt erreicht hat, ab dem sie nie wieder etwas auf das Ausgabeband schreibt. Würden sich die Induktionsergebnisse mit diesem Orakel stark von einem Ansatz unterscheiden, der den Programmraum vollständig durchsucht und einfach zum nächsten Programm „überspringt“, wenn ein Programm für hinreichend viele n Schritte keine Ausgabe erzeugt?
Ich meine Induktion über „gewöhnliche“ komprimierbare Daten, nicht absichtlich konstruierte Grenzfälle oder adversariale Beispiele wie BB(3,3).
Als Sicherheitsforscher schreibe ich selbst Fuzzer. Ein Fuzzer ist ein Werkzeug, das automatisch sicherheitsrelevante Eingaben für das zu testende Programm findet. Er erzeugt und verändert Eingaben algorithmisch, gibt sie an das Programm weiter und beobachtet dutzende, hunderte oder tausende Male pro Sekunde, was passiert.
Wenn eine Eingabe ein Programm zum Absturz bringt, kann man das als „Anhalten“ des Programms betrachten. Um einen Fuzzer zu bauen, der für jedes Programm in realistischer Zeit alle Bugs findet, müsste man vermutlich das Halteproblem lösen. Tatsächlich finden Leute selbst nach Milliarden von Tests noch Bugs in Image-Decodern, also sind unsere Fuzzer offensichtlich nicht perfekt.
Gleichzeitig habe ich in der Praxis gesehen, dass Fuzzer, wenn man ihnen genug Zeit gibt, überraschend tief in komplexe Programme vordringen. Die Eingabevalidierung des Testziels sowie der begrenzte Speicher und Massenspeicher moderner PCs bringen den Fuzzer gewissermaßen auf eine Bahn. Kryptografie ist allerdings eine Ausnahme; für einen Fuzzer ist sie wie ein rechnerischer Teersumpf. Gut abgesicherte und gut spezifizierte Programme wirken als eigene Leitplanken, sodass der Fuzzer das Halteproblem nicht lösen muss.
Daher sehe ich es bei der Suche nach Sicherheitsbugs in Programmen so: Abgesehen von Kryptografie sind Fuzzer stark darin, Programme mit strenger Eingabevalidierung anzugreifen. Umgekehrt braucht man für Programme ohne strenge Eingabevalidierung nicht unbedingt einen Fuzzer, und dort funktioniert ein Fuzzer auch nicht zwangsläufig gut.
BBB, also der piepsende Busy Beaver, warum kann er intuitiv viel länger laufen, bevor er quasi anhält?
Eine Sache, die auffällt: Man muss den Haltezustand praktisch gar nicht verwenden. In diesem Sinne könnte ein BBB mit 3 Zuständen einem BB mit 4 Zuständen ähneln. Ich frage mich, ob es darüber hinaus noch mehr gibt.
Deshalb kann man ein Programm bzw. eine Turingmaschine der Größe X so bauen, dass sie die Ausführung aller Programme der Größe Y simuliert, wobei Y >> X gilt. Wenn man sie jedes Mal piepsen lässt, wenn eines dieser Programme anhält, tritt der letzte Piepton auf, wenn simuliert wird, dass BB(Y) nach mehr als BB(Y) Schritten anhält. Daher gilt BBB(X) > BB(Y) >> BB(X).
Wenn ich mich richtig erinnere, kann man wegen im Grunde derselben Konstruktion, wenn man BB(N) kennt, das Halteproblem für Programme der Größe höchstens N sehr langsam berechnen; kennt man dagegen BBB(N), kann man das Halteproblem für Turingmaschinen mit gegebenem Halte-Orakel bis zu dieser Größe noch viel langsamer berechnen.
Das ist mir zu nerdig.
Ich frage mich, welches Vorwissen man braucht, um so etwas zu verstehen. Reicht einfache Analysis? Welche konkreten Themen oder Kurse wären eine gute Grundlage?
[1] https://www.scottaaronson.com/writings/bignumbers.html
Wenn man einem Einführungslehrbuch zur theoretischen Informatik folgt, hilft das, den Großteil zu verstehen. Informatikstudierende lernen das normalerweise im 1. oder 2. Studienjahr, und es ist nicht leicht. An unserer Uni war das eine der gefürchtetsten Prüfungen.
Das Einführungsbuch von Hopcroft & Ullmann ist gut. Allerdings gibt es sehr viel damit zusammenhängenden Stoff, daher ist es eher als Ausgangspunkt zu sehen.
Zu vielen Informatik-Bachelorveranstaltungen dürfte es öffentlich verfügbare Materialien geben.
Wie soll man
1RB2RA1LC_2LC1RB2RB_---2LA1LAlesen?https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA
Wenn man zum Beispiel im Zustand B ist und der Bandwert an der aktuellen Kopfposition 0 ist, schreibt man eine 2, bewegt den Kopf um ein Feld nach links und wechselt in Zustand C.
Die 3 Zeichen bedeuten das zu schreibende Symbol, den neuen Zustand und die Bewegungsrichtung. Der Zustand
---bedeutet Anhalten.(Zustand, Bandwert)wird auf ein Tripel(neuer Bandwert, Bewegungsrichtung des Bandkopfs, neuer Zustand)abgebildet.[0] https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA