Fleißiger Biber
Fleißige Biber (auch englisch busy beaver) sind spezielle Turingmaschinen, die möglichst viele Einsen auf das Band schreiben und die nach einer endlichen Anzahl Rechenschritte den Halt-Zustand einnehmen (also anhalten). Die Radó-Funktion (auch Fleißiger-Biber-Funktion) gibt die maximale Anzahl der Einsen an, die ein fleißiger Biber mit einer gegebenen Anzahl von Zuständen schreiben kann. Beides wurde erstmals 1962[1] vom ungarischen Mathematiker Tibor Radó betrachtet.
Die Fleißiger-Biber-Funktion ist in der theoretischen Informatik ein Standardbeispiel für eine endliche, aber im Allgemeinen nicht berechenbare Funktion.[2]
Formelle Betrachtung
Definition
Nach Radó ist ein fleißiger Biber eine Turingmaschine, die wie üblich Zustände und einen Halt-Zustand einnehmen kann. Im Gegensatz zur allgemeinen Definition einer Turingmaschine unterliegt er jedoch speziellen Regeln.[1] So muss ein fleißiger Biber als Bewegungsschritt immer entweder nach links oder rechts auf dem Band gehen. Es gibt hier also keine Anweisung zum Verharren auf einem Feld. Ein fleißiger Biber erwartet auch keine leeren Felder, sondern nur welche, die bereits einen Wert aus dem ihm bekannten zweielementigen Alphabet enthalten. Das Band, auf das der fleißige Biber aufgesetzt wird, ist zuvor vollständig mit Nullen gefüllt. Ein fleißiger Biber muss nach einer endlichen Anzahl Schritte den Halt-Zustand einnehmen, darf also nicht in eine Endlosschleife geraten. Er muss nach dem Anhalten die maximale Anzahl von Einsen geschrieben haben, verglichen mit allen anderen Turingmaschinen mit ebenfalls Zuständen, die nach den gleichen Regeln arbeiten. Nur Turingmaschinen, die nicht halten, könnten mehr Einsen schreiben, wären dann aber keine fleißigen Biber.
Fleißiger-Biber-Funktion
Über die maximale Anzahl von Einsen, die ein fleißiger Biber mit Zuständen schreibt, ist der Wert der Fleißiger-Biber-Funktion (auch Radó-Funktion) an der Stelle definiert: .
Nicht lösbares Problem
Die Bestimmung der fleißigen Biber ist ein Problem, das nicht allgemein (für alle ) algorithmisch lösbar ist. So ist nicht generell entscheidbar, ob eine gegebene Turingmaschine mit Zuständen tatsächlich eine maximale Anzahl von Einsen auf das Band schreibt. Für einzelne Turingmaschinen geringer Komplexität ist das allerdings möglich. Also ist die Menge der Werte von weder entscheidbar noch rekursiv aufzählbar, obwohl wohldefiniert ist. Da auch das Komplement dieser Menge nicht rekursiv aufzählbar ist, wird diese Menge gerne als Beispiel für eine Sprache gewählt, die nicht in der ersten Stufe der arithmetischen Hierarchie liegt.
Wegen dieser Eigenschaften der Wertemenge ist die Funktion nicht berechenbar. Man kann außerdem zeigen, dass ihr asymptotisches Wachstum stärker ist als das jeder berechenbaren Funktion.
Praktische Betrachtung
In der Praxis hat sich gezeigt, dass schon für eine Erkenntnis über den Wert realistisch gesehen nicht mehr möglich zu sein scheint. Dazu müsste man für jede einzelne Turingmaschine mit Zuständen jeweils herausfinden, nach wie vielen Schritten sie hält, oder anderenfalls beweisen, dass sie das nicht tut. Für eine gegebene Anzahl von Zuständen (plus einem Haltezustand) gibt es bei einem Alphabet mit zwei Zeichen verschiedene Turingmaschinen, denn für jeden der Eingangszustände muss jeweils für jedes der beiden möglichen gelesenen Symbole festgelegt werden, welches der beiden Symbole auf das Band geschrieben werden soll und in welche Richtung der Lesekopf bewegt werden soll und welchen der möglichen Zustände die Turingmaschine danach annehmen soll. Schon bei möglichen Eingangszuständen müssen somit verschiedene Turingmaschinen betrachtet werden.
Der Bulgare Georgi Georgiev veröffentlichte 2003 eine Untersuchung, in der er fleißige Biber daraufhin analysierte, ob sie anhalten würden oder nicht.[3] Für entzogen sich lediglich knapp über 40 fleißige Biber einem gesicherten Ergebnis, da sie aufgrund besonderer Verhaltensweisen nicht mit den von Georgiev angewandten Methoden abschließend zu analysieren waren. Von denen, die als terminierend (anhaltend) bestimmt wurden, schreibt keiner mehr als 4098 Einsen auf das Band.
| Zustände | Turingmaschinen | Quelle | |
|---|---|---|---|
| 1 | 64 | 1 | (1962; Radó) |
| 2 | 20736 | 4 | (1962; Radó) |
| 3 | 16777216 | 6 | (1965; Lin, Radó) |
| 4 | 2,56×1010 | 13 | (1972; Weimann, Casper, Fenzel) |
| 5 | ≈ 6,34×1013 | ≥ 240 | (1983; Jochen Ludewig) |
| ≥ 501 | (1983; Uwe Schult) | ||
| ≥ 1915 | (1984; George Uhing) | ||
| ≥ 4098 | (1989; Jürgen Buntrock und Heiner Marxen) | ||
| 6 | ≈ 2,32×1017 | > 3,514×1018267 | (2010; Pavel Kropitz) |
| 7 | ≈ 1,18×1021 | Abschätzung unrealistisch | |
Beispiele
Fleißiger Biber mit einem Zustand
Die partielle Überführungsfunktion ist wie folgt definiert:
| aktueller Zustand |
geles. Symbol |
schr. Symbol |
neuer Zustand |
Kopf- richtung | |
|---|---|---|---|---|---|
| 0 | → | 1 | R |
durchläuft folgende Zustände, wobei die aktuelle Kopfposition fett gedruckt ist:
| Schritt | Zust. | Band |
|---|---|---|
| 1 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_0} | 00 |
| hält | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_f} | 10 |
Fleißiger Biber mit 2 Zuständen
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M = (\{q_0, q_1, q_f\}, \{\}, \{0,1\}, \delta, q_0, 0, \{q_f\})}
Die Überführungsfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta} ist wie folgt definiert:
| aktueller Zustand |
geles. Symbol |
schr. Symbol |
neuer Zustand |
Kopf- richtung | |
|---|---|---|---|---|---|
| Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_0} | 0 | → | 1 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | R |
| Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_0} | 1 | → | 1 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | L |
| Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | 0 | → | 1 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_0} | L |
| Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | 1 | → | 1 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_f} | R |
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} durchläuft folgende Zustände, wobei die aktuelle Kopfposition fett gedruckt ist:
| Schritt | Zust. | Band |
|---|---|---|
| 1 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_0} | …0000000… |
| 2 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | …0001000… |
| 3 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_0} | …0001100… |
| 4 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | …0001100… |
| 5 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_0} | …0011100… |
| 6 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | …0111100… |
| hält | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_f} | …0111100… |
Fleißiger Biber mit 3 Zuständen
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M = (\{q_0, q_1, q_2, q_f\}, \{\}, \{0,1\}, \delta, q_0, 0, \{q_f\})}
Die Überführungsfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta} ist wie folgt definiert:
| aktueller Zustand |
geles. Symbol |
schr. Symbol |
neuer Zustand |
Kopf- richtung | |
|---|---|---|---|---|---|
| Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_0} | 0 | → | 1 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | R |
| Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_0} | 1 | → | 1 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_f} | R |
| Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | 0 | → | 0 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_2} | R |
| Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | 1 | → | 1 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | R |
| Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_2} | 0 | → | 1 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_2} | L |
| Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_2} | 1 | → | 1 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_0} | L |
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} durchläuft folgende Zustände, wobei die aktuelle Kopfposition fett gedruckt ist:
| Schritt | Zust. | Band |
|---|---|---|
| 1 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_0} | 000000 |
| 2 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | 010000 |
| 3 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_2} | 010000 |
| 4 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_2} | 010100 |
| 5 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_2} | 011100 |
| 6 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_0} | 011100 |
| 7 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | 111100 |
| 8 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | 111100 |
| Schritt | Zust. | Band |
|---|---|---|
| 9 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | 111100 |
| 10 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} | 111100 |
| 11 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_2} | 111100 |
| 12 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_2} | 111101 |
| 13 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_2} | 111111 |
| 14 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_0} | 111111 |
| hält | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_f} | 111111 |
Die Funktion S
Radó definierte zusätzlich eine Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S(n)} , deren Wert die maximale Anzahl an Schritten einer haltenden Turingmaschine mit zweielementigem Alphabet und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Zuständen ist. Auch diese Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} ist nicht berechenbar; wäre sie es, so wäre das Halteproblem mit leerem Eingabeband entscheidbar, denn eine Turingmaschine mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Zuständen, die mehr als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S(n)} Schritte macht, hält nie.
Da in jedem Schritt maximal eine Eins geschrieben werden kann, gilt
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S(n) \ge \Sigma(n)} .
Zwischen den Funktionen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} besteht weiterhin die folgende Beziehung.
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S(n) < \Sigma(3n+6)} .[4]
Ebenfalls nicht berechenbare Funktion
Eine ebenfalls nicht berechenbare Funktion ergibt sich, wenn die zusätzliche Beschränkung eingeführt wird, dass alle Einsen eine zusammenhängende Kette bilden müssen.
Als Bezeichnung dafür hat sich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma(n)} eingebürgert.
1965 hat C. Dunham eine weitere Variante der Funktion des fleißigen Bibers angegeben.[5] Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D(n)} ist definiert als die maximale Anzahl Einsen, die eine Turingmaschine mit zweielementigem Alphabet und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Zuständen schreiben kann, wenn sie auf ein Band mit einem Block von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Einsen angesetzt wird und dabei hält. Wäre diese Funktion berechenbar, so gäbe es auch eine Turingmaschine M mit zweielementigem Alphabet, die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n\mapsto D(n)+1} berechnet. Diese Turingmaschine habe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} Zustände. Dann wäre Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D(m)+1 = M(m) \le D(m)} , wobei das Gleichheitszeichen gerade die Definition von M ist, und das Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \le} -Zeichen daher rührt, dass M ja eine Maschine mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} Zuständen ist und angesetzt auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} (d. h. auf einen Block aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} Einsen) hält und daher nach Definition von D die Ungleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M(m)\le D(m)} erfüllen muss. Dieser Widerspruch zeigt die Nicht-Berechenbarkeit von D.
Literatur
- A. K. Dewdney: The (new) Turing Omnibus. 66 Excursions in Computer Science. Computer Science Press, New York NY 1993, überarbeitet 1996, ISBN 0-7167-8271-5.
- Jochen Ludewig, Uwe Schult, Frank Wankmüller: Chasing the Busy Beaver. Notes and Observations on a competition to find the 5-state Busy Beaver. Universität Dortmund – Abt. Informatik, Dortmund 1983 (Abteilung Informatik, Universität Dortmund. Bericht 159).
- Heiner Marxen, Jürgen Buntrock: Attacking the Busy Beaver 5. In: Bulletin of the EATCS. 40, Februar 1990, ISSN 0252-9742, S. 247–251.
Weblinks
- W. Zimmer: Fleißige Biber (PDF, 97 KiB), exakte Einführung mit Literaturbeispielen, auf 10 Seiten für Grundkurs Theoretische Informatik am Cusanus-Gymnasium Wittlich dargestellt
- Reinhard Völler: Turing-Berechenbarkeit aus Theoretische Informatik, kurze Darstellung von Rados Busy-Beaver-Problem mit einigen Beispielen aus der Literatur, Hochschule für Angewandte Wissenschaften Hamburg
- Heiner Marxen: Busy Beaver (englisch) – bekannte Resultate, sehr viele Links (zur Forschung) bis 2010, darunter:
- Auf der Suche nach fleißigen Bibern – Turingmaschinensimulatoren, Universität Stuttgart 1996
- Scott Aaronson: The Busy Beaver Frontier (PDF; 478 kB), Überblick und Diskussion offener Probleme, 2020
Einzelnachweise
- ↑ a b T. Radó: On non-computable functions (Memento vom 27. März 2014 im Internet Archive) (PDF; 3,6 MB; WebArchive vom 27. März 2014), In The Bell System Technical Journal, Band 41, Nr. 3, S. 877–884, Mai 1962
- ↑ Eckart Zitzler: Dem Computer ins Hirn geschaut: Informatik entdecken, verstehen und querdenken. Springer-Verlag, 2017, ISBN 978-3-662-53666-7, S. 384 f. (google.com [abgerufen am 25. Oktober 2021]).
- ↑ Busy Beaver nonregular machines for class TM(5)
- ↑ A. M. Ben-Amram, B. A. Julstrom, U. Zwick: A Note on Busy Beavers and Other Creatures, In Mathematical Systems Theory, 29(4), S. 375–386, Juli / August 1996, doi:10.1007/BF01192693
- ↑ C. Dunham: A Candidate for the simplest uncomputable function In: Communications of the Association for Computing Machinery (Letter to the Editor) 8, 4, 1965, ISSN 0001-0782, S. 201
