Beschäftigter Biber – Wikipedia

Posted on by

Eine anhaltende Turing-Maschine mit binärem Alphabet, die die meisten Einsen auf das Band schreibt und nur einen begrenzten Satz von Zuständen verwendet

Informationen zum Online-Bildungsprogramm für Kinder finden Sie unter Busy Beavers.

In der theoretischen Informatik ist die beschäftigt Biber Spiel zielt darauf ab, ein Abschlussprogramm einer bestimmten Größe zu finden, das die größtmögliche Ausgabe erzeugt.[1]

Genauer gesagt, die beschäftigt Biber Spiel besteht darin, eine anhaltende Turing-Maschine mit binärem Alphabet zu entwerfen, die die meisten Einsen auf das Band schreibt und nur einen bestimmten Satz von Zuständen verwendet. Die Regeln für das 2-Staaten-Spiel lauten wie folgt:

  1. Die Maschine muss zusätzlich zum Haltezustand zwei Zustände haben, und
  2. Das Band enthält zunächst nur Nullen.

Ein Spieler sollte sich eine Übergangstabelle vorstellen, die auf die längste Ausgabe von 1s auf dem Band abzielt und gleichzeitig sicherstellt, dass die Maschine irgendwann anhält.

Ein nDer beschäftigte Biber, BB-n oder einfach “vielbeschäftigter Biber” ist eine Turingmaschine, die das gewinnt n-State Busy Beaver Game. Das heißt, es erreicht die größtmögliche Anzahl von Einsen unter allen anderen möglichen n-Staat konkurrierende Turingmaschinen. Die BB-2 Turing-Maschine erreicht beispielsweise vier Einsen in sechs Schritten.

Es ist unentscheidbar, ob eine beliebige Turing-Maschine ein beschäftigter Biber ist. Dies hat Auswirkungen auf die Berechenbarkeitstheorie, das Stoppproblem und die Komplexitätstheorie. Das Konzept wurde erstmals von Tibor Radó in seiner Arbeit von 1962 vorgestellt. “Über nicht berechenbare Funktionen”.

Das Spiel[edit]

Das n-State beschäftigt Biber Spiel (oder BB-n Spiel), das in Tibor Radós Papier von 1962 vorgestellt wurde, umfasst eine Klasse von Turing-Maschinen, von denen jedes Mitglied die folgenden Konstruktionsspezifikationen erfüllen muss:

  • Die Maschine hat n “betriebsbereit” Staaten plus einen Halt Zustand, wo n ist eine positive ganze Zahl und eine der n Zustände wird als Ausgangszustand unterschieden. (Normalerweise sind die Zustände mit 1, 2, …, nmit Zustand 1 als Startzustand oder von EIN, B., C., …, mit Staat EIN als Ausgangszustand.)
  • Die Maschine verwendet ein einzelnes unendliches (oder unbegrenztes) Zweiwegeband.
  • Das Bandalphabet ist {0, 1}, wobei 0 als leeres Symbol dient.
  • Die Maschinen Übergangsfunktion nimmt zwei Eingaben:
  1. der aktuelle Nicht-Halt-Zustand,
  2. das Symbol in der aktuellen Bandzelle,
und erzeugt drei Ausgänge:
  1. ein Symbol zum Überschreiben des Symbols in der aktuellen Bandzelle (es kann dasselbe Symbol sein wie das überschriebene Symbol),
  2. eine Bewegungsrichtung (links oder rechts; das heißt, eine Stelle links oder rechts von der aktuellen Zelle in die Bandzelle verschieben) und
  3. ein Zustand, in den übergegangen werden soll (der möglicherweise der Halt-Zustand ist).
Es gibt also (4n + 4)2nn-state Turing-Maschinen, die diese Definition erfüllen.
Eine aufgeschlüsselte Version derselben Formel ist (Symbole * * Richtungen * (Zustände + 1))((Symbole * * Zustände).
Die Übergangsfunktion kann als endliche Tabelle von 5 Tupeln jeder Form angesehen werden
(aktueller Zustand, aktuelles Symbol, zu schreibendes Symbol, Verschiebungsrichtung, nächster Zustand).

“Laufen” Die Maschine besteht darin, im Startzustand zu starten, wobei die aktuelle Bandzelle eine beliebige Zelle eines leeren Bandes (alle 0) ist, und dann die Übergangsfunktion zu wiederholen, bis der Halt-Zustand eingegeben wird (falls jemals). Wenn und nur wenn die Maschine irgendwann anhält, wird die Anzahl der 1s, die schließlich auf dem Band verbleiben, als die der Maschine bezeichnet Ergebnis.

Das n-State beschäftigt Biber (BB-n) Spiel ist ein Wettbewerb, um eine solche zu finden n-State Turing-Maschine mit der größtmöglichen Punktzahl – die größte Anzahl von Einsen auf dem Band nach dem Anhalten. Eine Maschine, die die größtmögliche Punktzahl unter allen erreicht n-state Turing Maschinen heißt ein n-State beschäftigt Biber, und eine Maschine, deren Punktzahl nur die höchste bisher erreichte (vielleicht nicht die größtmögliche) ist, wird als a bezeichnet Champion n-Zustandsmaschine.

Radó verlangte, dass jeder am Wettbewerb teilnehmenden Maschine eine genaue Angabe der Anzahl der Schritte beigefügt wird, die erforderlich sind, um den Halt-Zustand zu erreichen. Auf diese Weise konnte die Punktzahl jedes Beitrags (im Prinzip) überprüft werden, indem die Maschine für die angegebene Anzahl ausgeführt wurde von Schritten. (Wenn Einträge nur aus Maschinenbeschreibungen bestehen sollten, ist das Problem der Überprüfung jedes potenziellen Eintrags unentscheidbar, da es dem bekannten Stoppproblem entspricht. Es gibt keine effektive Möglichkeit, zu entscheiden, ob eine beliebige Maschine irgendwann anhält.)

Verwandte Funktionen[edit]

Die beschäftigte Biberfunktion Σ[edit]

Das Besetzte Biberfunktion quantifiziert die maximale Punktzahl, die ein Busy Beaver mit einem bestimmten Maß erreichen kann. Dies ist eine nicht berechenbare Funktion. Es kann auch gezeigt werden, dass eine beschäftigte Biberfunktion asymptotisch schneller wächst als jede berechenbare Funktion.

Die beschäftigte Biberfunktion, Σ: N. → N.ist so definiert, dass Σ (n) ist die maximal erreichbare Punktzahl (die maximale Anzahl von 1s, die schließlich auf dem Band sind) unter allen anhaltenden 2-Symbolen n-State Turing-Maschinen des oben beschriebenen Typs, wenn sie auf einem leeren Band gestartet werden.

Es ist klar, dass Σ eine genau definierte Funktion ist: für jeden ngibt es höchstens endlich viele n-Zustand Turingmaschinen wie oben, bis zum Isomorphismus, also höchstens endlich viele mögliche Laufzeiten.

Diese unendliche Folge Σ ist der Besetzte Biberfunktionund alle n-Zustand 2-Symbol Turingmaschine M. für welche σ((M.) = Σ (n) (dh die maximale Punktzahl erreicht) heißt a vielbeschäftigter Biber. Beachten Sie, dass für jeden ngibt es mindestens vier n-State beschäftigt Biber (weil gegeben, keine n-State Busy Beaver, ein anderer wird erhalten, indem lediglich die Verschiebungsrichtung in einem Halteübergang geändert wird, ein anderer durch Verschieben aller Richtungsänderungen in die entgegengesetzte Richtung und der letzte durch Verschieben der Stopprichtung des all-getauschten Busy Biber).

Nicht berechenbar[edit]

Radós Papier von 1962 bewies, dass wenn f: ℕ → ℕ ist eine berechenbare Funktion, dann Σ (n)> f (n) für alle ausreichend groß nund daher ist Σ keine berechenbare Funktion.

Darüber hinaus impliziert dies, dass durch einen allgemeinen Algorithmus nicht entschieden werden kann, ob eine beliebige Turing-Maschine ein beschäftigter Biber ist. (Ein solcher Algorithmus kann nicht existieren, da seine Existenz die Berechnung von Σ ermöglichen würde, was eine nachgewiesene Unmöglichkeit darstellt. Insbesondere könnte ein solcher Algorithmus verwendet werden, um einen anderen Algorithmus zu konstruieren, der Σ wie folgt berechnet: für jeden gegebenen n, jeder der endlich vielen n-State 2-Symbol Turing-Maschinen würden getestet, bis ein n-Status beschäftigt Biber gefunden; Diese beschäftigte Bibermaschine würde dann simuliert, um ihre Punktzahl zu bestimmen, die per Definition Σ (n).)

Obwohl Σ (n) ist eine nicht berechenbare Funktion, es gibt einige kleine n für die es möglich ist, seine Werte zu erhalten und zu beweisen, dass sie korrekt sind. Es ist nicht schwer zu zeigen, dass Σ (0) = 0, Σ (1) = 1, Σ (2) = 4, und mit zunehmend größerer Schwierigkeit kann gezeigt werden, dass Σ (3) = 6 und Σ (4) = 13 (Sequenz A028444 in der OEIS). Σ (n) wurde noch für keinen Fall von bestimmt n > 4, obwohl Untergrenzen festgelegt wurden (siehe Abschnitt Bekannte Werte unten).

Im Jahr 2016 erhielten Adam Yedidia und Scott Aaronson die erste (explizite) Obergrenze für das Minimum n für welche Σ (n) ist in ZFC nicht beweisbar. Dazu bauten sie einen 7910-Staat[2] Turingmaschine, deren Verhalten nicht anhand der üblichen Axiome der Mengenlehre (Zermelo-Fraenkel-Mengenlehre mit dem Axiom der Wahl) unter vernünftigen Konsistenzhypothesen (stationäre Ramsey-Eigenschaft) nachgewiesen werden kann.[3][4] Dies wurde später auf 1919 Staaten reduziert, wobei die Abhängigkeit von der stationären Ramsey-Liegenschaft beseitigt wurde.[5][6] und später zu 748 Staaten.[7]

Komplexität und Unbeweisbarkeit von Σ[edit]

Eine Variante der Kolmogorov-Komplexität ist wie folgt definiert [cf. Boolos, Burgess & Jeffrey, 2007]: Das Komplexität einer Zahl n ist die kleinste Anzahl von Zuständen, die für eine Turing-Maschine der BB-Klasse benötigt werden, die mit einem einzelnen Block von angehalten wird n aufeinanderfolgende 1s auf einem anfänglich leeren Band. Die entsprechende Variante des Unvollständigkeitssatzes von Chaitin besagt, dass es im Kontext eines gegebenen axiomatischen Systems für die natürlichen Zahlen eine Zahl gibt k so dass nachgewiesen werden kann, dass keine bestimmte Zahl eine größere Komplexität aufweist als kund daher kann für Σ (keine spezifische Obergrenze nachgewiesen werden)k) (Letzteres liegt daran “die Komplexität von n ist größer als k” wäre bewiesen wenn “n > Σ (k)” wurden bewiesen). Wie in der zitierten Referenz erwähnt, gilt für jedes axiomatische System von “gewöhnliche Mathematik” der kleinste Wert k für die dies zutrifft, ist weit weniger als 10 ↑↑ 10; Folglich kann im Kontext der gewöhnlichen Mathematik weder der Wert noch eine Obergrenze von Σ (10 ↑↑ 10) bewiesen werden. (Gödels erster Unvollständigkeitssatz wird durch dieses Ergebnis veranschaulicht: In einem axiomatischen System der gewöhnlichen Mathematik gibt es einen wahren, aber nicht beweisbaren Satz der Form “Σ (10 ↑↑ 10) = n“und es gibt unendlich viele wahre, aber unbeweisbare Sätze der Form “Σ (10 ↑↑ 10) n“.)

Maximale Schichtfunktion S.[edit]

Neben der Funktion Σ ist Radó [1962] führte eine weitere extreme Funktion für die BB-Klasse der Turing-Maschinen ein, die maximale Schaltfunktion, S., wie folgt definiert:

  • s((M.) = Anzahl der Schichten M. macht vor dem Anhalten, für jeden M. im E.n,
  • S.((n) = max { s((M.) | M. ∈ E.n } = die größte Anzahl von Schichten, die durch ein Anhalten gemacht wurden n-Zustand 2-Symbol Turingmaschine.

Weil diese Turing-Maschinen bei jedem Übergang eine Verschiebung haben müssen oder “Schritt” (einschließlich eines Übergangs in einen Halt-Zustand) ist die Max-Shifts-Funktion gleichzeitig eine Max-Steps-Funktion.

Radó hat das gezeigt S. ist aus demselben Grund nicht berechenbar wie Σ nicht berechenbar – es wächst schneller als jede berechenbare Funktion. Er bewies dies einfach, indem er das für jeden notierte n, S.((n) ≥ Σ (n). Jede Schicht kann eine 0 oder eine 1 auf das Band schreiben, während Σ eine Teilmenge der Schichten zählt, die eine 1 geschrieben haben, nämlich diejenigen, die zum Zeitpunkt des Anhaltens der Turing-Maschine nicht überschrieben worden waren; Folglich, S. wächst mindestens so schnell wie Σ, von dem bereits nachgewiesen wurde, dass es schneller wächst als jede berechenbare Funktion.

Die folgende Verbindung zwischen Σ und S. wurde von Lin & Radó verwendet [Computer Studies of Turing Machine Problems, 1965] um zu beweisen, dass Σ (3) = 6: Für eine gegebene n, wenn S.((n) ist dann allen bekannt n-State Turing-Maschinen können (grundsätzlich) bis zu betrieben werden S.((n) Schritte, an denen eine Maschine, die noch nicht angehalten hat, niemals anhält. An diesem Punkt erhält man durch Beobachten, welche Maschinen mit den meisten Einsen auf dem Band angehalten haben (dh die beschäftigten Biber), von ihren Bändern den Wert von Σ (n). Der von Lin & Radó für den Fall von n = 3 sollte das vermuten S.(3) = 21, um dann alle wesentlich unterschiedlichen 3-Zustands-Maschinen für bis zu 21 Schritte zu simulieren. Durch die Analyse des Verhaltens der Maschinen, die nicht innerhalb von 21 Schritten angehalten hatten, gelang es ihnen zu zeigen, dass keine dieser Maschinen jemals anhalten würde, was die Vermutung beweist, dass S.(3) = 21 und Bestimmen von Σ (3) = 6 durch das gerade beschriebene Verfahren.

Ungleichungen in Bezug auf Σ und S. umfassen die folgenden (von [Ben-Amram, et al., 1996]), die für alle gültig sind n ≥ 1::

S.((n)≥Σ((n)S.((n)≤((2n– –1)Σ((3n+3)S.((n)<Σ((3n+6);;{ displaystyle { begin {align} S (n) & geq Sigma (n) \ S (n) & leq (2n-1) Sigma (3n + 3) \ S (n) & < Sigma (3n + 6); end {align}}}

und eine asymptotisch verbesserte Bindung (von [Ben-Amram, Petersen, 2002]): Es existiert eine Konstante c, so dass für alle n ≥ 2,

S.((n)≤Σ((n+⌈8nLog2⁡n⌉+c).{ displaystyle S (n) leq Sigma left (n + left lceil { frac {8n} { log _ {2} n}} right rceil + c right).}

S.((n){ displaystyle S (n)}

neigt dazu, nahe am Quadrat von zu sein

Σ((n){ displaystyle Sigma (n)}

und in der Tat geben viele Maschinen

S.((n){ displaystyle S (n)}

weniger als

Σ2((n){ displaystyle Sigma ^ {2} (n)}

.

Bekannte Werte für Σ und S.[edit]

Ab 2016 sind die Funktionswerte für Σ (n) und S.((n) sind nur genau bekannt für n <5.[4]

Der aktuelle (Stand 2018) 5-Staaten-Biber-Champion produziert 4098 1s, mit 47176870 Schritte (entdeckt von Heiner Marxen und Jürgen Buntrock im Jahr 1989), aber es bleiben 18 oder 19 (möglicherweise unter 10, siehe unten) Maschinen mit unregelmäßigem Verhalten, von denen angenommen wird, dass sie niemals anhalten, von denen jedoch nicht nachgewiesen wurde, dass sie unendlich laufen. Skelett listet 42 oder 43 unbewiesene Maschinen auf, aber 24 sind bereits bewiesen.[8] Die verbleibenden Maschinen wurden auf 81,8 Milliarden Schritte simuliert, aber keine wurde angehalten. Daniel Briggs bewies auch einige Maschinen.[9] Eine andere Quelle sagt, dass 98 Maschinen unbewiesen bleiben. Es gibt eine Analyse der Holdouts.[10] Es ist also wahrscheinlich, dass Σ (5) = 4098 und S (5) = 47176870, aber dies bleibt unbewiesen, und es ist nicht bekannt, ob noch Holdouts vorhanden sind (Stand 2018). Im Moment produziert der Rekord-6-State-Champion über 3.515×1018267 1s (genau (25 * 430341+23) / 9) mit over 7.412×1036534 Schritte (gefunden von Pavel Kropitz im Jahr 2010). Wie oben erwähnt, handelt es sich hierbei um Turing-Maschinen mit zwei Symbolen.

Eine einfache Erweiterung der 6-Zustandsmaschine führt zu einer 7-Zustandsmaschine, die mehr als 10 schreibt10101018705353 1s auf das Band, aber es gibt zweifellos viel beschäftigtere 7-Zustands-Maschinen. Andere beschäftigte Biberjäger haben jedoch andere Maschinensätze.

Milton Green, in seiner Arbeit von 1964 “Eine Untergrenze für Rados Sigma-Funktion für binäre Turingmaschinen”konstruierte eine Reihe von Turing-Maschinen, die dies demonstrieren

Σ((2k)>3↑k– –23>EIN((k– –2,k– –2)zum k≥2,{ displaystyle Sigma (2k)> 3 uparrow ^ {k-2} 3> A (k-2, k-2) qquad { mbox {for}} k geq 2,}

Σ((10)>3↑↑↑3=3↑↑333=333...3{ displaystyle Sigma (10)> 3 uparrow uparrow uparrow 3 = 3 uparrow uparrow 3 ^ {3 ^ {3}} = 3 ^ {3 ^ {3 ^ {. ^ {. ^ {. ^ {3}}}}}}}

7625597484987 Begriffe im Exponentialturm) und
Σ((12)>3↑↑↑↑3=G1,{ displaystyle Sigma (12)> 3 uparrow uparrow uparrow uparrow 3 = g_ {1},}

Σ((2k+1)>3↑k– –231>EIN((k– –2,k– –2)zum k≥2,{ displaystyle Sigma (2k + 1)> 3 uparrow ^ {k-2} 31> A (k-2, k-2) qquad { mbox {for}} k geq 2,}

1018267, die größer ist als die durch die Greensche Formel gegebene Untergrenze, 33 = 27 (was im Vergleich winzig ist). Tatsächlich ist es viel größer als die Untergrenze: 3 ↑↑ 3 = 333 = 7625597484987Dies ist die erste Untergrenze von Green für Σ (8) und auch viel größer als die zweite Untergrenze: 3 * (7 * 3)92-1) / 2.

Σ (7) ist auf die gleiche Weise viel, viel größer als die derzeitige gemeinsame Untergrenze 331 (fast 618 Billionen), daher ist auch die zweite Untergrenze sehr, sehr schwach.

Beweis für die Unberechenbarkeit von S.((n) und Σ (n)[edit]

Nehme an, dass S.((n) ist eine berechenbare Funktion und lassen EvalS bezeichnen ein TM, auswertend S.((n). Gegeben ein Band mit n 1s wird es produzieren S.((n) 1s auf dem Band und dann anhalten. Lassen Reinigen bezeichnen eine Turing-Maschine, die die ursprünglich auf das Band geschriebene Folge von 1s reinigt. Lassen Doppelt bezeichnen eine Turing-Maschinenauswertungsfunktion n + n. Gegeben ein Band mit n 1s wird es 2 produzierenn 1s auf dem Band und dann anhalten. Lassen Sie uns die Komposition erstellen Doppelt | EvalS | Reinigen und lass n0 sei die Anzahl der Zustände dieser Maschine. Lassen Create_n0 bezeichnen eine Turingmaschine, die erstellt n0 1s auf einem anfangs leeren Band. Diese Maschine kann auf triviale Weise konstruiert sein n0 Staaten (der Staat ich schreibt 1, bewegt den Kopf nach rechts und wechselt in den Status ich + 1, außer dem Staat n0, die anhält). Lassen N. bezeichnen die Summe n0 + n0.

Lassen BadS bezeichnen die Zusammensetzung Create_n0 | Doppelt | EvalS | Reinigen. Beachten Sie, dass diese Maschine hat N. Zustände. Beginnend mit einem anfangs leeren Band wird zunächst eine Folge von erstellt n0 1s und verdoppelt es dann, wodurch eine Folge von erzeugt wird N. 1s. Dann BadS wird herstellen S.((N.) 1s auf Band, und schließlich werden alle 1s gelöscht und dann angehalten. Aber die Reinigungsphase wird zumindest fortgesetzt S.((N.) Schritte, also die Arbeitszeit von BadS ist streng größer als S.((N.), was der Definition der Funktion widerspricht S.((n).

Die Unberechnbarkeit von Σ (n) kann auf ähnliche Weise nachgewiesen werden. Im obigen Beweis muss man die Maschine austauschen EvalS mit EvalΣ und Reinigen mit Zuwachs – ein einfaches TM, das nach einer ersten 0 auf dem Band sucht und diese durch 1 ersetzt.

Die Unberechenbarkeit von S.((n) kann auch unter Bezugnahme auf das Problem des Anhaltens des leeren Bandes festgestellt werden. Das Problem beim Anhalten des leeren Bandes besteht darin, dass für jede Turing-Maschine entschieden wird, ob sie beim Starten auf einem leeren Band angehalten wird oder nicht. Das Problem des Anhaltens des leeren Bandes entspricht dem Standardproblem des Anhaltens und ist daher auch nicht berechenbar. Wenn S.((n) war berechenbar, dann konnten wir das Problem des Anhaltens des leeren Bandes lösen, indem wir einfach eine bestimmte Turing-Maschine mit ausführten n Staaten für S.((n) Schritte; Wenn es immer noch nicht angehalten hat, wird es nie. Da das Problem des Anhaltens des leeren Bandes nicht berechenbar ist, folgt daraus S.((n) muss ebenfalls nicht berechenbar sein.

Verallgemeinerungen[edit]

Für jedes Berechnungsmodell gibt es einfache Analoga des beschäftigten Bibers. Zum Beispiel die Verallgemeinerung auf Turingmaschinen mit n Staaten und m Symbole definiert Folgendes verallgemeinerte Besetztbiberfunktionen::

  1. Σ (n, m): Die größte Anzahl von Nicht-Nullen, die von einem gedruckt werden können n-Zustand, m-Symbolmaschine startete auf einem anfangs leeren Band vor dem Anhalten, und
  2. S.((n, m): die größte Anzahl von Schritten, die von einem n-Zustand, m-Symbolmaschine startete auf einem anfangs leeren Band, bevor sie anhielt.

Beispielsweise läuft die bisher am längsten laufende 3-Status-3-Symbol-Maschine 119112334170342540 Schritte vor dem Anhalten. Die am längsten laufende Maschine mit 6 Zuständen und 2 Symbolen, die die zusätzliche Eigenschaft hat, den Bandwert bei jedem Schritt umzukehren, erzeugt 6147 1s nach 47339970 Schritte. Damit S.RTM(6) ≥ 47339970 und ΣRTM(6) ≥ 6147.

Es ist möglich, die Funktion des beschäftigten Bibers weiter zu verallgemeinern, indem sie auf mehr als eine Dimension ausgedehnt wird.

Ebenso könnten wir für eine gegebene Anzahl von Anweisungen ein Analogon zur Σ-Funktion für Registermaschinen als die größte Zahl definieren, die beim Anhalten in jedem Register vorhanden sein kann.

Genaue Werte und Untergrenzen[edit]

In der folgenden Tabelle sind die genauen Werte und einige bekannte Untergrenzen für aufgeführt S.((n, m) und Σ (n, m) für die allgemeinen Probleme mit beschäftigten Bibern. Hinweis: Einträge aufgelistet als “?” werden von unten durch das Maximum aller Einträge nach links und oben begrenzt. Diese Maschinen wurden entweder nicht untersucht oder später von einer kleineren Maschine übertroffen.

Die Turing-Maschinen, die diese Werte erreichen, sind auf verfügbar Pascal Michel Website. Jede dieser Websites enthält auch eine Analyse der Turing-Maschinen und Verweise auf die Nachweise der genauen Werte.

Werte von S (n, m)

n

m

 2-Zustand 3-Zustand 4-Zustand 5-Zustand 6-Zustand 7-Zustand
2-Symbol 6 21 107 47176870? > 7.4×1036534 > 1010101018705353
3-Symbol 38 ≥ 119112334170342540 > 1.0×1014072 ? ? ?
4-Symbol ≥ 3932964 > 5.2×1013036 ? ? ? ?
5-Symbol > 1.9×10704 ? ? ? ? ?
6-Symbol > 2.4×109866 ? ? ? ? ?
Werte von Σ (n, m)

n

m

 2-Zustand 3-Zustand 4-Zustand 5-Zustand 6-Zustand 7-Zustand
2-Symbol 4 6 13 4098? > 3.5×1018267 > 1010101018705353
3-Symbol 9 ≥ 374676383 > 1.3×107036 ? ? ?
4-Symbol ≥ 2050 > 3.7×106518 ? ? ? ?
5-Symbol > 1.7×10352 ? ? ? ? ?
6-Symbol > 1.9×104933 ? ? ? ? ?

Anwendungen[edit]

Die vielbeschäftigten Biberfunktionen stellen nicht nur ein ziemlich herausforderndes mathematisches Spiel dar, sondern bieten auch einen völlig neuen Ansatz zur Lösung rein mathematischer Probleme. Viele offene Probleme in der Mathematik könnten theoretisch, aber nicht in der Praxis systematisch gelöst werden, wenn man den Wert von berücksichtigt S.((n) für eine ausreichend große n.[11]

Betrachten Sie jede Vermutung, die durch ein Gegenbeispiel aus einer zählbaren Anzahl von Fällen widerlegt werden könnte (z. B. Goldbachs Vermutung). Schreiben Sie ein Computerprogramm, das diese Vermutung nacheinander auf steigende Werte testet. Im Fall von Goldbachs Vermutung würden wir jede gerade Zahl ≥ 4 nacheinander betrachten und testen, ob es sich um die Summe zweier Primzahlen handelt oder nicht. Angenommen, dieses Programm wird auf einem simuliert n-State Turing Maschine. Wenn es ein Gegenbeispiel findet (eine gerade Zahl ≥ 4, die in unserem Beispiel nicht die Summe zweier Primzahlen ist), wird es angehalten und zeigt dies an. Wenn die Vermutung jedoch wahr ist, wird unser Programm niemals anhalten. (Dieses Programm wird angehalten nur wenn es ein Gegenbeispiel findet.)

Jetzt wird dieses Programm von einem simuliert n-State Turing Maschine, wenn wir wissen S.((n) Wir können (in endlicher Zeit) entscheiden, ob es jemals anhalten wird oder nicht, indem wir die Maschine einfach so viele Schritte laufen lassen. Und wenn nach S.((n) Schritte, die Maschine hält nicht an, wir wissen, dass dies niemals der Fall sein wird und dass es daher keine Gegenbeispiele zu der gegebenen Vermutung gibt (dh keine geraden Zahlen, die nicht die Summe zweier Primzahlen sind). Dies würde beweisen, dass die Vermutung wahr ist.

Somit sind bestimmte Werte (oder Obergrenzen) für S.((n) könnte verwendet werden, um viele offene Probleme in der Mathematik (theoretisch) systematisch zu lösen. Aktuelle Ergebnisse zum Problem der vielbeschäftigten Biber legen jedoch nahe, dass dies aus zwei Gründen nicht praktikabel ist:

  • Es ist äußerst schwierig, Werte für die Busy-Beaver-Funktion (und die Max-Shift-Funktion) nachzuweisen. Es wurde nur für extrem kleine Maschinen mit weniger als fünf Zuständen bewiesen, während man vermutlich mindestens 20-50 Zustände benötigen würde, um eine nützliche Maschine herzustellen. Weiterhin ist jeder bekannte exakte Wert von S.((n) wurde durch Aufzählung aller bewiesen n-State Turing Maschine und zu beweisen, ob jeder anhält oder nicht. Man müsste rechnen S.((n) durch eine weniger direkte Methode, damit es tatsächlich nützlich ist.
  • Aber selbst wenn man einen besseren Weg gefunden hätte, um zu rechnen S.((n) werden die Werte der Busy-Beaver-Funktion (und der Max-Shift-Funktion) sehr schnell sehr groß. S.(6)> 1036534 erfordert bereits eine spezielle musterbasierte Beschleunigung, um vollständig simulieren zu können. Ebenso wissen wir das S.(10)> Σ (10)> 3 ↑↑↑ 3 ist eine gigantische Zahl und S.(17)> Σ (17)> G, wobei G Grahams Zahl ist – eine enorme Zahl. Selbst wenn wir es wüssten, sagen wir: S.(30) ist es völlig unvernünftig, eine Maschine mit dieser Anzahl von Schritten auszuführen. Im bekannten Teil des Universums ist nicht genügend Rechenkapazität vorhanden, um eine gleichmäßige Leistung zu erbringen S.(6) Operationen direkt.[12]

Bemerkenswerte Instanzen[edit]

Es wurde eine binäre Turing-Maschine mit 748 Zuständen konstruiert, die anhält, wenn ZFC inkonsistent ist.[13] Es wurde eine Turingmaschine mit 744 Zuständen konstruiert, die anhält, wenn die Riemann-Hypothese falsch ist.[5][13] Es wurde eine Turing-Maschine mit 43 Zuständen konstruiert, die anhält, wenn Goldbachs Vermutung falsch ist, und eine Maschine mit 27 Zuständen für diese Vermutung wurde vorgeschlagen, aber noch nicht verifiziert.[5][13]

Beispiele[edit]

Lauf eines Busy Beaver mit 4 Zuständen und 2 Symbolen. Blau: Band (“0” gedruckt als “_”), rot: Zustand (unmittelbar vor der aktuellen Kopfposition angezeigt).

Dies sind Regeltabellen für die Turing-Maschinen, die Σ (1) und erzeugen S.(1), Σ (2) und S.(2), Σ (3) (aber nicht S.(3)), Σ (4) und S.(4) und die bekannteste Untergrenze für Σ (5) und S.(5) und Σ (6) und S.(6).

In den Tabellen repräsentieren Spalten den aktuellen Status und Zeilen das aktuelle Symbol, das vom Band gelesen wurde. Jeder Tabelleneintrag besteht aus drei Zeichen und gibt das Symbol an, das auf das Band geschrieben werden soll, die Bewegungsrichtung und den neuen Status (in dieser Reihenfolge). Der Haltezustand wird als angezeigt H..

Jede Maschine beginnt im Zustand EIN mit einem unendlichen Band, das alle Nullen enthält. Somit ist das vom Band gelesene Anfangssymbol eine 0.

Ergebnisschlüssel: (beginnt an der Position überstrichenhält an der Position an unterstrichen)

1-Zustand, 2-Symbol beschäftigt Biber
EIN
0 1RH.
1 (nicht benutzt)

Ergebnis: 0 0 1 0 0 (1 Schritt, eins “1” gesamt)

Beschäftigter Biber mit 2 Zuständen und 2 Symbolen
EIN B.
0 1RB. 1LEIN
1 1LB. 1RH.

Ergebnis: 0 0 1 1 1 1 0 0 (6 Schritte, vier “1”s gesamt)

Beschäftigter Biber mit 3 Zuständen und 2 Symbolen
EIN B. C.
0 1RB. 0RC. 1LC.
1 1RH. 1RB. 1LEIN

Ergebnis: 0 0 1 1 1 1 1 1 0 0 (14 Schritte, sechs “1”s total).

Im Gegensatz zu den vorherigen Maschinen ist diese eine beschäftigte Biber nur für Σ, aber nicht für S.. ((S.(3) = 21.)

Beschäftigter Biber mit 4 Zuständen und 2 Symbolen
EIN B. C. D.
0 1RB. 1LEIN 1RH. 1RD.
1 1LB. 0LC. 1LD. 0REIN

Ergebnis: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 Schritte, dreizehn “1”s total, siehe Bild)

aktueller bester Anwärter mit 5 Zuständen und 2 Symbolen (möglicherweise beschäftigter Biber)
EIN B. C. D. E.
0 1RB. 1RC. 1RD. 1LEIN 1RH.
1 1LC. 1RB. 0LE. 1LD. 0LEIN

Ergebnis: 4098 “1”s mit 8191 “0”s in 47.176.870 Schritten eingestreut.

aktueller bester Anwärter mit 6 Zuständen und 2 Symbolen
EIN B. C. D. E. F.
0 1RB. 1RC. 1LD. 1RE. 1LEIN 1LH.
1 1LE. 1RF. 0RB. 0LC. 0RD. 1RC.

Ergebnis: ~ 3,515 × 1018267 “1”s in ~ 7,412 × 1036534 Schritte.

Siehe auch[edit]

Verweise[edit]

  • Radó, Tibor (Mai 1962). “Bei nicht berechenbaren Funktionen” (PDF). Bell System Technical Journal. 41 (3): 877–884. doi:10.1002 / j.1538-7305.1962.tb00480.x.
    Hier definierte Radó zuerst das Problem der beschäftigten Biber und bewies, dass es nicht berechenbar war und schneller wuchs als jede berechenbare Funktion.
  • Lin, Shen; Radó, Tibor (April 1965). “Computerstudien zu Turingmaschinenproblemen”. Zeitschrift der ACM. 12 (2): 196–212. doi:10.1145 / 321264.321270.
    Die Ergebnisse dieser Arbeit waren bereits teilweise in Lins Dissertation von 1963 unter Radós Anleitung erschienen. Lin & Radó beweisen, dass Σ (3) = 6 und S.(3) = 21 durch den Nachweis, dass alle 3-Zustands-Turing-Maschinen mit 2 Symbolen, die nicht innerhalb von 21 Schritten anhalten, niemals anhalten werden. (Die meisten werden automatisch von einem Computerprogramm geprüft, 40 jedoch durch menschliche Inspektion.)
  • Brady, Allen H. (April 1983). “Die Bestimmung des Wertes der nicht berechenbaren Funktion von Rado Σ (k) für Turingmaschinen mit vier Zuständen”. Mathematik der Berechnung. 40 (162): 647–665. doi:10.1090 / S0025-5718-1983-0689479-6. JSTOR 2007539.
    Brady beweist, dass Σ (4) = 13 und S.(4) = 107. Brady definiert zwei neue Kategorien für nicht anhaltende 3-Zustands-Turing-Maschinen mit 2 Symbolen: Weihnachtsbäume und -zähler. Er verwendet ein Computerprogramm, um zu beweisen, dass alle außer 27 Maschinen, die über 107 Schritte laufen, Varianten von Weihnachtsbäumen und -zählern sind, von denen nachgewiesen werden kann, dass sie unendlich laufen. Die letzten 27 Maschinen (als Holdouts bezeichnet) haben durch persönliche Inspektion durch Brady selbst bewiesen, dass sie nicht anhalten.
  • Machlin, Rona; Stout, Quentin F. (Juni 1990). “Das komplexe Verhalten einfacher Maschinen”. Physica D: Nichtlineare Phänomene. 42 (1-3): 85-98. Bibcode:1990PhyD … 42 … 85M. doi:10.1016 / 0167-2789 (90) 90068-Z. hdl:2027.42 / 28528.
    Machlin und Stout beschreiben das Problem der beschäftigten Biber und viele Techniken, die zum Auffinden beschäftigter Biber verwendet werden (die sie auf Turingmaschinen mit 4 Zuständen und 2 Symbolen anwenden, um Bradys Beweis zu überprüfen). Sie schlagen vor, wie eine Variante der Chaitin-Stoppwahrscheinlichkeit (Ω) geschätzt werden kann.
  • Marxen, Heiner; Buntrock, Jürgen (Februar 1990). “Den geschäftigen Biber angreifen 5”. Bulletin des EATCS. 40: 247–251. Archiviert vom Original am 09.10.2006. Abgerufen 2020-01-19.
    Marxen und Buntrock zeigen, dass Σ (5) ≥ 4098 und S.(5) ≥ 47176870 und beschreiben Sie detailliert die Methode, mit der sie diese Maschinen gefunden haben, und beweisen Sie, dass viele andere niemals aufhören werden.
  • Green, Milton W. (1964). Eine Untergrenze für Rados Sigma-Funktion für binäre Turingmaschinen. 1964 Vorträge des fünften jährlichen Symposiums über Schaltkreistheorie und logisches Design. S. 91–94. doi:10.1109 / SWCT.1964.3.
    Grün konstruiert rekursiv Maschinen für eine beliebige Anzahl von Zuständen und stellt die rekursive Funktion bereit, die ihre Punktzahl berechnet (berechnet σ), wodurch eine Untergrenze für Σ bereitgestellt wird. Das Wachstum dieser Funktion ist vergleichbar mit dem der Ackermann-Funktion.
  • Dewdney, Alexander K. (1984). “Eine Computerfalle für den vielbeschäftigten Biber, die am härtesten arbeitende Turingmaschine”. Wissenschaftlicher Amerikaner. 251 (2): 10–17.
    Beschäftigte Biberprogramme werden von Alexander Dewdney in beschrieben Wissenschaftlicher AmerikanerAugust 1984, Seiten 19–23, ebenfalls März 1985 p. 23 und April 1985 p. 30.
  • Chaitin, Gregory J. (1987). “Berechnung der Busy Beaver-Funktion” (PDF). In Deckung, TM; Gopinath, B. (Hrsg.). Offene Probleme in Kommunikation und Berechnung. Springer. S. 108–112. ISBN 978-0-387-96621-2.
  • Brady, Allen H. (1995). “Das geschäftige Biberspiel und der Sinn des Lebens”. In Herken, Rolf (Hrsg.). Die universelle Turingmaschine: Ein halbes Jahrhundert Umfrage (2. Aufl.). Wien, New York: Springer-Verlag. S. 237–254. ISBN 978-3-211-82637-9.
    Wobei Brady (von 4-Staaten-Ruhm) einige Geschichte des Tieres beschreibt und seine Verfolgung nennt “Das geschäftige Biberspiel”. Er beschreibt andere Spiele (z. B. zellulare Automaten und Conways Spiel des Lebens). Von besonderem Interesse ist “Das geschäftige Biberspiel in zwei Dimensionen” (S. 247). Mit 19 Referenzen.
  • Booth, Taylor L. (1967). Sequentielle Maschinen und Automatentheorie. New York: Wiley. ISBN 978-0-471-08848-6.
    Vgl. Kapitel 9, Turingmaschinen. Ein schwieriges Buch für Elektrotechniker und technische Spezialisten. Erläutert die Rekursion, Teilrekursion unter Bezugnahme auf Turing-Maschinen und das Anhalten des Problems. Eine Referenz in Booth schreibt Rado den beschäftigten Biber zu. Booth definiert auch Rados beschäftigtes Biberproblem in “Probleme zu Hause” 3, 4, 5, 6 von Kapitel 9, p. 396. Problem 3 ist zu “zeigen, dass das Problem mit dem beschäftigten Biber unlösbar ist … für alle Werte von n.”
  • Ben-Amram, AM; Julstrom, BA; Zwick, U. (1996). “Ein Hinweis zu Busy Beavers und anderen Kreaturen”. Mathematische Systemtheorie. 29 (4): 375–386. CiteSeerX 10.1.1.75.1297. doi:10.1007 / BF01192693.
    Grenzen zwischen Funktionen Σ und S..
  • Ben-Amram, AM; Petersen, H. (2002). “Verbesserte Grenzen für Funktionen im Zusammenhang mit beschäftigten Bibern”. Theorie der Computersysteme. 35: 1–11. CiteSeerX 10.1.1.136.5997. doi:10.1007 / s00224-001-1052-0.
    Verbesserte Grenzen.
  • Lafitte, G.; Papazian, C. (Juni 2007). “Der Stoff kleiner Turingmaschinen”. Berechnung und Logik in der realen Welt, Vorträge der dritten Konferenz über Berechenbarkeit in Europa. S. 219–227. CiteSeerX 10.1.1.104.3021.
    Dieser Artikel enthält eine vollständige Klassifizierung der Turing-Maschinen mit 2 Zuständen und 3 Symbolen und damit einen Beweis für den (2, 3) beschäftigten Biber: Σ (2, 3) = 9 und S (2, 3) = 38.
  • Boolos, George S.; Burgess, John P.; Jeffrey, Richard C. (2007). Berechenbarkeit und Logik (Fünfte Ausgabe). Cambridge University Press. ISBN 978-0-521-87752-7.
  • Kropitz, Pavel (2010). Problém Busy Beaver (Bachelorarbeit) (auf Slowakisch). Karlsuniversität in Prag.
    Dies ist die Beschreibung der Ideen, der Algorithmen und ihrer Implementierung, mit der Beschreibung der Experimente, bei denen 5-Zustands- und 6-Zustands-Turing-Maschinen durch parallelen Lauf auf 31 4-Kern-Computern untersucht wurden, und schließlich die besten Ergebnisse für 6-Zustands-TM.

Externe Links[edit]