In der Berechenbarkeitstheorie ist ein beschäftigter Biber (vom umgangssprachlichen Ausdruck für eine fleißige Person) eine Maschine von Turing, die die maximale "betriebliche Betriebsamkeit" (solcher, wie gemessen, durch die Zahl von Schritten durchgeführt oder die Zahl von nichtleeren Symbolen schließlich auf dem Band) unter allen Maschinen von Turing in einer bestimmten Klasse erreicht. Die Turing Maschinen in dieser Klasse müssen bestimmte Gestaltungsvorschriften entsprechen und sind erforderlich, schließlich zu hinken, mit einem leeren Band angefangen.

Eine beschäftigte Biber-Funktion misst diese oberen Grenzen auf einem gegebenen Typ der "betrieblichen Betriebsamkeit", und ist eine nichtberechenbare Funktion. Tatsächlich, wie man zeigen kann, wächst eine beschäftigte Biber-Funktion schneller asymptotisch, als jede berechenbare Funktion tut. Das Konzept wurde zuerst von Tibor Radó als das "beschäftigte Biber-Spiel" in seiner 1962-Zeitung, "Auf Nichtberechenbaren Funktionen" eingeführt.

Das beschäftigte Biber-Spiel

Beschäftigtes Biber-Spiel des N-Staates' (oder BB-n Spiel), eingeführt in der 1962-Zeitung von Tibor Radó, sind mit einer Klasse von Maschinen von Turing verbunden, von denen jedes Mitglied erforderlich ist, die folgenden Gestaltungsvorschriften zu entsprechen:

• Die Maschine hat n "betriebliche" Staaten plus ein Halt-Staat, wo n eine positive ganze Zahl ist, und einer der N-Staaten als der Startstaat bemerkenswert ist. (Gewöhnlich werden die Staaten durch 1, 2..., n, mit staatlichem 1 als der Startstaat, oder durch A, B, C..., mit dem Staat als der Startstaat etikettiert.)
• Die Maschine verwendet ein einzelnes Zweiwegeunendliche (oder unbegrenzt) Band.
• Das Band-Alphabet ist {0, 1} mit 0 Portion als das leere Symbol.
• Die Übergang-Funktion der Maschine nimmt zwei Eingänge:

:#the Strom halten Staat, nicht

:#the Symbol in der aktuellen Band-Zelle,

:and erzeugt drei Produktionen:

:#a Symbol, um über dasjenige in der aktuellen Band-Zelle zu schreiben (kann es dasselbe Symbol wie ein überschriebener sein),

:#a Richtung, um sich (verlassen oder Recht zu bewegen; d. h. Verschiebung zur Band-Zelle ein Platz nach links oder Recht auf die aktuelle Zelle), und

:#a setzen zum Übergang in fest (der der Halt-Staat sein kann).

:The-Übergang-Funktion kann als ein begrenzter Tisch von 5 Tupeln, jede der Form gesehen werden

: (aktueller Staat, aktuelles Symbol, Symbol, um, Richtung der Verschiebung zu schreiben, setzt als nächstes fest).

"Das Laufen" der Maschine besteht aus dem Starten im Startstaat mit der aktuellen Band-Zelle, die jede Zelle eines Bandes des Formblattes (voll0) ist, und dann die Übergang-Funktion wiederholt, bis in den Halt-Staat (wenn jemals) eingegangen wird. Wenn, und nur wenn die Maschine schließlich hinkt, dann wird die Zahl 1s, schließlich auf dem Band bleibend, die Kerbe der Maschine genannt.

Der N-Staat beschäftigter Biber (BB-n) Spiel ist ein Streit, um solch eine Maschine von N-Staat Turing zu finden, die die größtmögliche Kerbe — die größte Zahl 1s auf seinem Band nach dem Halt hat. Eine Maschine, die die größtmögliche Kerbe unter allen Maschinen von N-Staat Turing erreicht, wird einen N-Staat beschäftigten Biber genannt, und eine Maschine, deren Kerbe bloß bis jetzt erreicht am höchsten ist (vielleicht nicht das größtmögliche) wird eine MeisterN-Zustandmaschine genannt.

Radó hat verlangt, dass jede im Streit eingegangene Maschine durch eine Behauptung der genauen Zahl von Schritten begleitet wird, die es macht, um den Halt-Staat zu erreichen, so der Kerbe jedes Zugangs erlaubend (im Prinzip) durch das Laufen der Maschine für die festgesetzte Zahl von Schritten nachgeprüft zu werden. (Wenn Einträge nur aus Maschinenbeschreibungen bestehen sollten, dann ist das Problem, jeden potenziellen Zugang nachzuprüfen, unentscheidbar, weil es zum wohl bekannten stockenden Problem gleichwertig ist — würde es keine wirksame Weise geben zu entscheiden, ob eine willkürliche Maschine schließlich hinkt.)

Der beschäftigte Biber fungiert Σ

Die beschäftigte Biber-Funktion, Σ: N  N, wird solch definiert, dass Σ (n) die maximale erreichbare Kerbe (die maximale Zahl 1s schließlich auf dem Band) unter allen stockenden 2-Symbole-Maschinen von N-Staat Turing des obengenannten - beschriebener Typ, wenn angefangen, auf einem leeren Band ist.

Es ist klar, dass Σ bestimmte Funktion ist: Für jeden n gibt es höchstens begrenzt viele Maschinen von N-Staat Turing als oben, bis zum Isomorphismus, folglich höchstens begrenzt viele mögliche Laufzeiten.

Diese unendliche Folge Σ ist die beschäftigte Biber-Funktion und jeder N-Staat 2-Symbole-Maschine von Turing M, nach der σ (M) = Σ (n) (d. h., der die maximale Kerbe erreicht) einen beschäftigten Biber genannt wird. Bemerken Sie, dass für jeden n, dort mindestens zwei N-Staat beschäftigte Biber bestehen Sie (weil, in Anbetracht jedes N-Staates beschäftigter Biber, ein anderer durch das bloße Ändern der Verschiebungsrichtung in einem stockenden Übergang erhalten wird).

Nichtberechenbarkeit von Σ

Das 1962-Papier von Radó hat dass wenn f bewiesen: N  ist N jede berechenbare Funktion, dann Σ (n)> f (n) für den ganzen genug großen n, und folglich, dass Σ nicht eine berechenbare Funktion ist.

Außerdem deutet das an, dass es durch einen allgemeinen Algorithmus unentscheidbar ist, ob eine willkürliche Maschine von Turing ein beschäftigter Biber ist. (Solch ein Algorithmus kann nicht bestehen, weil seine Existenz Σ erlauben würde, geschätzt zu werden, der eine bewiesene Unmöglichkeit ist. Insbesondere solch ein Algorithmus konnte verwendet werden, um einen anderen Algorithmus zu bauen, der Σ wie folgt schätzen würde: Für irgendwelchen gegeben n, jeder begrenzt vieler N-Staat würden 2-Symbole-Maschinen von Turing geprüft bis zu einem N-Staat wird beschäftigter Biber gefunden; diese beschäftigte Biber-Maschine würde dann vorgetäuscht, um seine Kerbe zu bestimmen, die definitionsgemäß Σ (n) ist.)

Wenn auch Σ (n) eine unberechenbare Funktion ist, gibt es einen kleinen n, für den es möglich ist, seine Werte zu erhalten und zu beweisen, dass sie richtig sind. Es ist nicht hart zu zeigen, dass Σ (0) = 0, Σ (1) = 1, Σ (2) = 4, und mit progressiv mehr Schwierigkeit es dass Σ (3) = 6 und Σ (4) = 13 (Folge A028444 in OEIS) gezeigt werden kann. Σ (n) ist für jedes Beispiel von n> 4 noch nicht bestimmt worden, obwohl niedrigere Grenzen gegründet worden sind (sieh die Bekannte Wertabteilung unten).

Σ, Kompliziertheit und unprovability

Eine Variante der Kompliziertheit von Kolmogorov wird wie folgt [vgl Boolos, Burgess & Jeffrey, 2007] definiert: Die Kompliziertheit einer Nummer n ist die kleinste Zahl von Staaten, die für eine BB-Klasse Turing Maschine erforderlich sind, die mit einem einzelnen Block von n aufeinander folgend 1s auf einem am Anfang leeren Band hinkt. Die entsprechende Variante des Unvollständigkeitslehrsatzes von Chaitin stellt fest, dass, im Zusammenhang eines gegebenen axiomatischen Systems für die natürlichen Zahlen, dort eine solche Nummer k besteht, dass, wie man beweisen kann, keine spezifische Zahl Kompliziertheit hat, die größer ist als k, und folglich dass nicht spezifisch ober gebunden für Σ (k) bewiesen werden kann (der Letztere ist, weil "die Kompliziertheit von n größer ist, als k" bewiesen würde, wenn "n> Σ (k)" bewiesen würden). Wie erwähnt, in der zitierten Verweisung für jedes axiomatische System der "gewöhnlichen Mathematik" ist kleinster Wert k, für den das wahr ist, weniger als 10  10 (das Verwenden der-Pfeil-Notation von Knuth) weit; folglich, im Zusammenhang der gewöhnlichen Mathematik, können weder der Wert noch irgendwelcher, der Σ (10  10) ober gebunden ist, bewiesen werden. (Der erste Unvollständigkeitslehrsatz von Gödel wird durch dieses Ergebnis illustriert: In einem axiomatischen System der gewöhnlichen Mathematik gibt es einen wahren-aber-unbeweisbaren Satz der Form "Σ (10  10) = n", und es gibt ungeheuer viele wahre-aber-unbeweisbare Sätze der Form "Σ (10  10) zwingt konsequente Bildübergabe von Formeln. Entfernen Sie bitte them.-> nicht

• die Anzahl der Schichten M macht vor dem Halt, für jede M in E,

• die größte Anzahl der Schichten, die durch jeden stockenden N-Staat 2-Symbole-Maschine von Turing gemacht ist.

Weil diese Maschinen von Turing erforderlich sind, eine Verschiebung in all und jedem Übergang oder "Schritt" zu haben (einschließlich jedes Übergangs zu einem Halt-Staat), ist die Max-Verschiebungsfunktion zur gleichen Zeit eine Max-Schritt-Funktion.

Radó hat gezeigt, dass S aus demselben Grund nichtberechenbar ist, dass Σ nichtberechenbar ist — wächst es schneller als jede berechenbare Funktion. Er hat das bewiesen, indem einfach er bemerkt hat, dass für jeden n, S (n)  Σ (n), weil eine Verschiebung erforderlich ist, 1 über das Band zu schreiben; folglich wächst S mindestens so schnell wie Σ, der, wie man bereits bewiesen hatte, schneller gewachsen war als jede berechenbare Funktion.

Die folgende Verbindung zwischen Σ und S wurde von Lin & Radó [Computerstudien von Turing Maschinenproblemen, 1965] verwendet, um dass Σ (3) = 6 zu beweisen: Für einen gegebenen n, wenn S (n) dann bekannt ist, können alle Maschinen von N-Staat Turing (im Prinzip) für bis zu S (n) Schritte geführt werden, an der Punkt jede Maschine ist die nicht noch gehinkt wird nie hinken. An diesem Punkt, indem man beobachtet, mit dem Maschinen meiste 1s auf dem Band (d. h., die beschäftigten Biber) gehinkt sind, erhält man von ihren Bändern den Wert von Σ (n). Die Annäherung, die von Lin & Radó für den Fall von n = 3 verwendet ist, sollte dass S (3) = 21 vermuten, um dann alle im Wesentlichen verschiedenen 3-Staaten-Maschinen für bis zu 21 Schritte vorzutäuschen. Indem sie das Verhalten der Maschinen analysiert haben, die innerhalb von 21 Schritten nicht gehinkt waren, haben sie geschafft zu zeigen, dass keine jener Maschinen jemals hinken würde, so die Vermutung dass S (3) = 21 beweisend, und dass Σ (3) = 6 durch das gerade beschriebene Verfahren beschließend.

Ungleichheit, die sich Σ und S bezieht, schließt das folgende ein (von [Ben-Amram, u. a. 1996]), die für den ganzen n  1 gültig sind:

:::

und asymptotisch verbessert gebunden (von [Ben-Amram, Petersen, 2002]): Dort besteht ein unveränderlicher c, solch das für den ganzen n  2,

:

Bekannte Werte

Die Funktionswerte für Σ (n) und S (n) sind nur genau für n Im Moment bekannt der beschäftigte Rekord-6-Staaten-Biber erzeugt mehr als 10 1s, mit mehr als 10 Schritten (gefunden von Pavel Kropitz 2010). Wie bemerkt, oben sind diese beschäftigten Biber 2-Symbole-Maschinen von Turing.

Milton Green, in seiner 1964-Zeitung "Ein Niedrigerer Gebundener die Sigma-Funktion von Rado für Binäre Turing Maschinen" hat eine Reihe von Maschinen von Turing gebaut, die das demonstriert

:

wo-Pfeil-Notation von Knuth ist und A die Funktion von Ackermann ist.

So

:

(mit 3 = 7,625,597,484,987 Begriffe im Exponentialturm), und

:

wo die Nummer g der enorme Startwert in der Folge ist, die die Zahl von Graham definiert.

Im Gegensatz hat der Strom zu Σ (6) gebunden ist 10, der größer ist als tiefer bestimmt 3=27 (der im Vergleich winzig ist). Tatsächlich ist es viel größer als tiefer bestimmt: der Green ist, hat dafür gebunden.

Generalisationen

Für jedes Modell der Berechnung dort bestehen einfache Analoga des beschäftigten Bibers. Zum Beispiel definiert die Generalisation zu Maschinen von Turing mit N-Staaten und M Symbole die folgenden verallgemeinerten beschäftigten Biber-Funktionen:

1. Σ (n, m): Die größte Zahl von durch einen N-Staat druckfähigen Nichtnullen, M Symbol-Maschine hat auf einem am Anfang leeren Band vor dem Halt und angefangen
2. S (n, m): Die größte Zahl von Schritten, die durch einen N-Staat, M Symbol-Maschine gemacht sind, hat auf einem am Anfang leeren Band vor dem Halt angefangen.

Zum Beispiel hat die längste laufende 3-Staaten-3-Symbole-Maschine so weite Läufe 119,112,334,170,342,540 Schritte vor dem Halt gefunden. Das längste Laufen 6-Staaten-, 2-Symbole-Maschine, die das zusätzliche Eigentum hat, den Band-Wert an jedem Schritt umzukehren, erzeugt 6,147 1s nach 47,339,970 Schritten. So S (6)  47,339,970 und Σ (6)  6,147.

Ebenfalls konnten wir ein Analogon zur Σ-Funktion für Register-Maschinen als die größte Zahl definieren, die in jedem Register auf dem Halt für eine gegebene Zahl von Instruktionen da sein kann.

Anwendungen

Zusätzlich zum Aufstellen eines ziemlich schwierigen mathematischen Spiels haben die beschäftigten Biber-Funktionen eine tiefe Anwendung. Viele offene Probleme in der Mathematik konnten auf eine systematische Weise gegeben der Wert von S (n) für einen genug großen n behoben werden.

Denken Sie jede Vermutung, die disproven über ein Gegenbeispiel unter einer zählbaren Zahl von Fällen (z.B die Vermutung von Goldbach) sein konnte. Schreiben Sie ein Computerprogramm, das folgend diese Vermutung prüft, um Werte zu vergrößern. Im Fall von der Vermutung von Goldbach würden wir jede gerade Zahl  4 folgend denken und prüfen, ob es die Summe von zwei Primzahlen ist. Nehmen Sie an, dass dieses Programm auf einer Maschine von N-Staat Turing vorgetäuscht wird. Wenn es ein Gegenbeispiel findet (eine gerade Zahl  4, der nicht die Summe von 2 Blüte in unserem Beispiel ist), hält es und benachrichtigt uns. Jedoch, wenn die Vermutung wahr ist, dann wird unser Programm nie hinken. (Dieses Programm hinkt nur, wenn es ein Gegenbeispiel findet.)

Jetzt wird dieses Programm durch eine Maschine von N-Staat Turing so vorgetäuscht, wenn wir S (n) wissen, können wir entscheiden (in einer begrenzten Zeitdauer), ob es jemals durch das einfache Laufen der Maschine dass viele Schritte hinken wird. Und wenn, danach S (n) Schritte, die Maschine nicht hinkt, wissen wir, dass sie nie wird, und so dass es keine Gegenbeispiele zur gegebenen Vermutung gibt (d. h., keine geraden Zahlen, die nicht die Summe von zwei Blüte sind). Das würde die Vermutung beweisen, um wahr zu sein.

So konnten spezifische Werte (oder obere Grenzen) für S (n) verwendet werden, um viele offene Probleme in der Mathematik (in der Theorie) systematisch zu beheben. Jedoch weisen aktuelle Ergebnisse auf dem beschäftigten Biber-Problem darauf hin, dass das aus zwei Gründen nicht praktisch sein wird:

• Es ist äußerst hart, Werte für die beschäftigte Biber-Funktion (und die Max-Verschiebungsfunktion) zu beweisen. Es ist nur für äußerst kleine Maschinen mit weniger als 5 Staaten bewiesen worden, während man vermutlich mindestens 20-50 Staaten brauchen würde, um eine nützliche Maschine zu machen. Außerdem wurde jeder bekannte genaue Wert von S (n) durch das Aufzählen jeder Maschine von N-Staat Turing und den Beweis bewiesen, ob jeder hinkt. Man würde S (n) durch eine weniger direkte Methode dafür berechnen müssen, um wirklich nützlich zu sein.
• Aber selbst wenn man wirklich eine bessere Weise gefunden hat, S (n) zu berechnen, werden die Werte der beschäftigten Biber-Funktion (und Max-Verschiebungsfunktion) sehr groß sehr schnell. S (6)> 10 verlangt bereits, dass spezielle Muster-basierte Beschleunigung im Stande ist, zur Vollziehung vorzutäuschen. Ebenfalls wissen wir, dass das eine riesige Zahl ist. So, selbst wenn wir, sagen wir, S (30) gewusst haben, ist es völlig unvernünftig, jede Maschine diese Zahl von Schritten zu führen. Es gibt nicht genug rechenbetonte Kapazität im bekannten Weltall, um sogar S (6) Operationen geleistet zu haben.

Beweis für die Unberechenbarkeit von S (n) und Σ (n)

Nehmen Sie an, dass S (n) eine berechenbare Funktion ist und lassen Sie EvalS einen TM anzeigen, S (n) bewertend. In Anbetracht eines Bandes mit n 1s wird es S (n) 1s auf dem Band erzeugen und dann hinken. Lassen Sie Sauber zeigen eine Maschine von Turing an, die Folge 1s am Anfang geschrieben über das Band reinigend. Lassen Sie Doppelt zeigen eine Maschinenauswerten-Funktion von Turing n + n an. In Anbetracht eines Bandes mit n 1s wird es 2n 1s auf dem Band erzeugen und dann hinken.

Lassen Sie uns die Zusammensetzung Doppelt | EvalS | Sauber schaffen und n die Zahl von Staaten dieser Maschine sein lassen. Lassen Sie Create_n eine Maschine von Turing anzeigen, die n 1s auf einem am Anfang leeren Band schafft. Diese Maschine kann auf eine triviale Weise gebaut werden, N-Staaten zu haben (der Staat i schreibt 1, bewegt das Hauptrecht und schaltet um, um i + 1 festzusetzen, außer dem Staat n, der hinkt). Lassen Sie N die Summe n + n anzeigen.

Lassen Sie BadS die Zusammensetzung Create_n | Doppelt | EvalS | Sauber anzeigen. Bemerken Sie, dass diese Maschine N-Staaten hat. Das Starten mit einem am Anfang leeren Band es schafft zuerst eine Folge von n 1s und verdoppelt es dann, eine Folge von N 1s erzeugend. Dann wird BadS S (N) 1s auf dem Band erzeugen, und schließlich wird es alle 1s klären und dann hinken. Aber die Phase der Reinigung wird mindestens S (N) Schritte weitergehen, so ist die Zeit des Arbeitens von BadS ausschließlich größer als S (N), der zur Definition der Funktion S (n) widerspricht.

Die Unberechenbarkeit von Σ (n) kann auf eine ähnliche Weise bewiesen werden. Im obengenannten Beweis muss man die Maschine EvalS mit EvalΣ austauschen und mit der Zunahme - ein einfacher TM Reinigen, nach dem ersten 0 auf dem Band suchend und es durch 1 ersetzend.

Die Unberechenbarkeit von S (n) kann auch bezüglich des leeren Bandes stockendes Problem gegründet werden. Stockendes Problem des leeren Bandes ist das Problem des Entscheidens für jede Maschine von Turing, ob es, wenn angefangen, auf einem leeren Band hinken wird. Stockendes Problem des leeren Bandes ist zum stockenden Standardproblem gleichwertig, und so ist es auch unberechenbar. Wenn S (n) berechenbar war, dann konnten wir das leere Band stockendes Problem beheben, indem einfach wir jede gegebene Maschine von Turing mit N-Staaten für S (n) Schritte geführt haben; wenn es noch immer nicht gehinkt ist, wird es nie. Also, da das leere Band stockendes Problem ist nicht berechenbar, hieraus folgt dass S (n) ebenfalls unberechenbar sein muss.

Beispiele des beschäftigten Bibers Maschinen von Turing

Weil ein Beispiel eines Zustandtisches eines beschäftigten 3-Staaten-Bibers und seines "Laufs" Maschinenbeispiele von Turing sieht.

Das sind Tische von Regeln für die Maschinen von Turing, die Σ (1) und S (1), Σ (2) und S (2), Σ (3) (aber nicht S (3)), Σ (4) und S (4), und das am besten bekannte erzeugen, das tiefer für Σ (5) und S (5) und Σ (6) und S (6) gebunden ist.

In den Tischen vertreten Säulen den aktuellen Staat, und Reihen vertreten das aktuelle vom Band gelesene Symbol. Jeder Tabellenzugang ist eine Reihe von drei Charakteren, das Symbol anzeigend, um auf das Band, die Richtung zu schreiben, um sich, und der neue Staat (in dieser Ordnung) zu bewegen. Der Halt-Staat wird als gezeigt.

Jede Maschine beginnt im Staat mit einem unendlichen Band, das den ganzen 0s enthält. So ist das anfängliche vom Band gelesene Symbol 0.

Ergebnis-Schlüssel: (Anfänge an der Position, Halte an der Position im kühnen)

1 Staat, beschäftigter 2-Symbole-Biber

:

Ergebnis: 0 0 0 0 (1 Schritt, ein "1" ganzes)

Beschäftigter 2-Staaten-2-Symbole-Biber

:

Ergebnis: 0 0 1 1 1 0 0 (6 Schritte, vier "1" s Summe)

Beschäftigter 3-Staaten-2-Symbole-Biber

:

Ergebnis: 0 0 1 1 1 1 1 0 0 (14 Schritte, sechs "1" s Summe).

Bemerken Sie, dass verschieden von den vorherigen Maschinen dieser ein beschäftigter Biber nur für Σ, aber nicht für S. ist (S (3) = 21.)

Beschäftigter 4-Staaten-2-Symbole-Biber

:

Ergebnis: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 Schritte, dreizehn "1" s Summe)

aktueller bester 5-Staaten-2-Symbole-Wettbewerber (möglicher beschäftigter Biber)

:

Ergebnis: 4098 "1" s mit 8191 "0" s in 47,176,870 Schritten eingestreut.

aktueller bester 6-Staaten-2-Symbole-Wettbewerber

:

Ergebnis: 3.515 × 10 "1" s in 7.412 × 10 Schritte.

Genaue Werte und niedrigere Grenzen für einen S (n, m) und Σ (n, m)

Der folgende Tisch verzeichnet die genauen Werte und einige bekannte niedrigere Grenzen für S (n, m) und Σ (n, m) für die verallgemeinerten beschäftigten Biber-Probleme. Bekannte genaue Werte werden als einfache ganze Zahlen gezeigt, und bekannten niedrigeren Grenzen wird durch größer oder gleich (dem ) Symbol vorangegangen. Bemerken Sie: Einträge hatten als Schlagseite"???" werden von unten durch das Maximum aller Einträge zum linken und oben begrenzt. Diese Maschinen entweder sind nicht untersucht worden oder wurden nachher durch eine Maschine übertroffen, die ihnen vorangeht.

Die Turing Maschinen, die diese Werte erreichen, sind sowohl auf dem webpages von Heiner Marxen als auch auf Pascal Michels verfügbar. Jede dieser Websites enthält auch etwas Analyse der Maschinen von Turing und Verweisungen auf die Beweise der genauen Werte.

Werte von S (n, m):

:

Werte von Σ (n, m):

:

Siehe auch

• Kompliziertheit von Kolmogorov
• Turmite

Referenzen

• Radó, Tibor (1962), Auf nichtberechenbaren Funktionen, Glockensystemfachzeitschrift, Vol. 41, Nr. 3 (Mai 1962), Seiten 877-884. Das ist, wo Radó zuerst das beschäftigte Biber-Problem definiert hat und bewiesen hat, dass es unberechenbar war und schneller gewachsen ist als jede berechenbare Funktion.
• Lin, Shen und Radó, Tibor (1965), Computerstudien von Turing Maschinenproblemen, Zeitschrift des ACM, Vol. 12, Nr. 2 (April 1965), Seiten 196-212. Die Ergebnisse dieses Papiers waren bereits teilweise in der 1963-Doktorarbeit von Lin unter der Leitung von Radó erschienen. Lin & Radó beweist, dass Σ (3) = 6 und S (3) = 21 durch den Beweis, dass alle Turing 3-Staaten-2-Symbole-Maschinen, die innerhalb von 21 Schritten nicht hinken, nie hinken werden. (Die meisten werden automatisch durch ein Computerprogramm bewiesen, jedoch 40 werden durch die menschliche Inspektion bewiesen.)
• Brady, Allen H. (1983), Der Entschluss vom Wert des nichtberechenbaren Funktionssigmas von Rado (k) für Vier-Staaten-Maschinen von Turing, Mathematik der Berechnung, Vol. 40, Nr. 162 (April 1983), Seiten 647-665. Brady beweist dass Σ (4) = 13 und S (4) = 107. Brady definiert zwei neue Kategorien, um Turing 3-Staaten-2-Symbole-Maschinen nichtzuhalten: Weihnachtsbäume und Schalter. Er verwendet ein Computerprogramm, um zu beweisen, dass alle außer 27 Maschinen, die 107 Schritte durchgehen, Varianten von Weihnachtsbäumen und Schaltern sind, die, wie man beweisen kann, ungeheuer laufen. Wie man beweist, hinken die letzten 27 Maschinen (verwiesen auf als holdouts) durch die persönliche Inspektion von Brady selbst nicht.
• Machlin, Rona und Stout, Quentin F. (1990), Das komplizierte Verhalten von einfachen Maschinen, Physica D, Nr. 42 (Juni 1990), Seiten 85-98. Machlin und Stout beschreiben das beschäftigte Biber-Problem und viele Techniken, die verwendet sind, um beschäftigte Biber zu finden (Den sie auf Turing Maschinen mit 4 Staaten und 2 Symbolen anwenden, so den Beweis von Brady nachprüfend). Sie schlagen vor, wie man eine Variante der stockenden Wahrscheinlichkeit von Chaitin (Ω) schätzt.
• Marxen, Heiner und Buntrock, Jürgen (1990), das Angreifen des Beschäftigten Bibers 5, Meldung des EATCS, Nr. 40 (Februar 1990), Seiten 247-251. Marxen und Buntrock demonstrieren, dass Σ (5)  4098 und S (5)  47,176,870 und im Detail die Methode beschreiben, haben sie gepflegt, diese Maschinen zu finden und zu beweisen, dass viele andere nie hinken werden.
• Grün, Milton W. (1964), Ein Niedrigerer Gebundener die Sigma-Funktion von Rado für Binäre Turing Maschinen, 1964 Verhandlungen des Fünften Jährlichen Symposiums auf der Umschaltenden Stromkreis-Theorie und dem Logischen Design, den Seiten 91-94. Grün baut rekursiv Maschinen für jede Zahl von Staaten und stellt die rekursive Funktion zur Verfügung, die rechnet, ihre Kerbe (schätzt σ), so einen für Σ gebundenen niedrigeren zur Verfügung stellend. Das Wachstum dieser Funktion ist mit dieser der Funktion von Ackermann vergleichbar.
• Beschäftigte Biber-Programme werden von Alexander Dewdney im Wissenschaftlichen Amerikaner, August 1984, Seiten 19-23, auch März 1985 p beschrieben. 23 und April 1985 p. 30.

:* Dewdney, Alexander K. Eine Computerfalle für den beschäftigten Biber, die härteste Arbeitsmaschine von Turing, den Wissenschaftlichen Amerikaner, 251 (2), 10-17, 1984.

• Chaitin, Gregory J. (1987), die Beschäftigte Biber-Funktion In T Schätzend. M. Cover und B. Gopinath, Offene Probleme in der Kommunikation und der Berechnung, dem Springer, 1987, Seiten 108-112.
• Brady, Allen H. (1995), Das Beschäftigte Biber-Spiel und die Bedeutung des Lebens, p 237-254, in Herken, Rolf (Hrsg.) erscheinend. Die Universale Turing Maschine: Ein Überblick des Halben Jahrhunderts, 2. Ausgabe (1995), Springer-Verlag, Wien New York. Worin Brady (der 4-Staaten-Berühmtheit) etwas Geschichte des Biestes beschreibt und seine Verfolgung "Das Beschäftigte Biber-Spiel" nennt. Er beschreibt andere Spiele (z.B Zellautomaten und das Spiel von Conway des Lebens). Vom besonderen Interesse ist "Das Beschäftigte Biber-Spiel in Zwei Dimensionen" (p. 247). Mit 19 Verweisungen.
• Taylor L. Booth, Folgende Maschinen- und Automaten-Theorie, Wiley, New York, 1967. Vgl Kapitel 9, Turing Maschinen. Ein schwieriges Buch, das für Elektroingenieure und technische Fachmänner beabsichtigt ist. Bespricht recursion, der bezüglich Turing Maschinen, stockenden Problems teilweise-recursion ist. Eine Verweisung in Booth schreibt beschäftigten Biber Rado zu. Booth definiert auch das beschäftigte Biber-Problem von Rado in "Hausproblemen" 3, 4, 5, 6 des Kapitels 9, p. 396. Problem 3 ist "zu zeigen, dass das beschäftigte Biber-Problem... für alle Werte von n unlösbar ist."
• A. M. Ben-Amram, B. A. Julstrom und U. Zwick. "Ein Zeichen auf Beschäftigten Bibern und anderen Wesen", Mathematische Systemtheorie, 29:375-386, 1996.. Grenzen zwischen Funktionen Σ und S.
• A. M. Ben-Amram, H. Petersen. "Verbesserte Grenzen für mit Beschäftigten Bibern Zusammenhängende Funktionen", Theorie der Computerwissenschaft von Systemen, 35:1-11, 2002.. Verbesserte Grenzen.
• G. Lafitte, C. Papazian. "Der Stoff von kleinen Maschinen von Turing" (in der "Berechnung und Logik in der Echten Welt, den Verhandlungen der Dritten Konferenz für die Berechenbarkeit in Europa", Juni 2007, 219-227). Dieser Artikel enthält eine ganze Klassifikation der 2-Staaten-, 3-Symbole-Maschinen von Turing, und so einen Beweis für (2, 3) beschäftigter Biber: Σ (2, 3) = 9 und S (2, 3) = 38.
• G. S. Boolos, J. P. Burgess und R. C. Jeffrey, Berechenbarkeit und Logik, die Fünfte Ausgabe, 2007, Universität von Cambridge Presse, internationale Standardbuchnummer 978-0-521-87752-7.

Links

• Die Seite von Heiner Marxen, den, mit Jürgen Buntrock, die oben erwähnten Aufzeichnungen für 5 und 6-Staaten-Maschine von Turing gefunden hat.
• Der historische Überblick von Pascal Michel über beschäftigte Biber-Ergebnisse, der auch beste Ergebnisse und etwas Analyse enthält.
• Definition der Klasse RTM - Umkehrung Turing Maschinen, einfache und starke Unterklasse des TMs.
• Der "Millennium-Angriff" am Rensselaer RAIR Laboratorium auf dem beschäftigten Biber-Problem. Diese Anstrengung hat mehrere neue Aufzeichnungen gefunden und hat mehrere Werte für die vierfache Formalisierung gegründet.
• Die Website von Daniel Briggs und Forum, für das beschäftigte 5-Staaten-2-Symbole-Biber-Problem zu beheben, das auf Skelet (Georgi Georgiev) nichtregelmäßige Maschinenliste gestützt ist.
• Aaronson, Scott (1999), Wer kann die größte Zahl nennen?
• Beschäftigter Biber durch Hector Zenil, Wolfram-Demonstrationsprojekt.