Auf der Suche nach einer geeigneten Programmiersprache für dynamisch generierte Webseiten, stieß ich nebenbei auf den "Fleißigen Biber", auch Radó-Funktion, Fleißiger-Biber-Funktion oder Busy Beaver-Funktion genannt. Es ist eine Funktion im programmiertechnischen Sinn, die (angeblich) nicht berechnet werden kann.
Obwohl ich eine Webseite nach der anderen studierte, war (außer einer) keine Erklärung so ausführlich, dass ich überhaupt das Grundprinzip verstand. Vor allem verstand ich nicht, was ein Zustand ist. Die Erklärung daraus ergibt sich aus meinen Erklärungen automatisch. Zur Sicherheit will ich es an dieser Stelle trotzdem erklären.
Der Zustand ist weder eine bestimmte Position, noch ein Bewegungs- bzw. Arbeitsvorgang. Der Lese-/Schreibkopf hat jeweils virtuell einen bestimmten Zustand. Die Turingbefehle gelten nicht alle für den gesamten Vorgang, sondern beziehen sich jeweils nur auf einen bestimmten Zustand des Kopfes.
Hat dieser bspw. momentan den Zustand Z3, bedeutet das, dass nur die Turungprogramme, die sich auf den Zustand Z3 beziehen, angewendet werden können. Von diesen aber wiederum muss nur jeweils derjenige angewendet werden (2. Bedingung), wenn das gelesene Zeichen derjenigen Anweisung entspricht, die sich auf dieses Zeichen bezieht.
Obwohl ich eine Webseite nach der anderen studierte, war (außer einer) keine Erklärung so ausführlich, dass ich überhaupt das Grundprinzip verstand. Vor allem verstand ich nicht, was ein Zustand ist. Die Erklärung daraus ergibt sich aus meinen Erklärungen automatisch. Zur Sicherheit will ich es an dieser Stelle trotzdem erklären.
Der Zustand ist weder eine bestimmte Position, noch ein Bewegungs- bzw. Arbeitsvorgang. Der Lese-/Schreibkopf hat jeweils virtuell einen bestimmten Zustand. Die Turingbefehle gelten nicht alle für den gesamten Vorgang, sondern beziehen sich jeweils nur auf einen bestimmten Zustand des Kopfes.
Hat dieser bspw. momentan den Zustand Z3, bedeutet das, dass nur die Turungprogramme, die sich auf den Zustand Z3 beziehen, angewendet werden können. Von diesen aber wiederum muss nur jeweils derjenige angewendet werden (2. Bedingung), wenn das gelesene Zeichen derjenigen Anweisung entspricht, die sich auf dieses Zeichen bezieht.
Zum Glück fand ich dann doch eine Webseite, wo erst mal das Prinzip der Turingmaschine und dann der "leißige Biber" ausführlich erklärt wurde:
Die Turingmaschine - www.larskiesow.de/
Mit dieser Information gelang es mir als Laie dann endlich, auch das Prinzip des fleißigen Bibers zu verstehen. Trotzdem glaube ich, dass es auch mit dieser sehr ausführlichen Erklärung immer noch ziemlich schwer verständlich ist, und möchte deswegen an dieser Stelle das auf meine Weise erklären, damit es auch Nichtinformatiker möglichst schnell verstehen können.
Auf einem theoretisch unendlich langen Datenstreifen kann ein Lese- / Schreibkopf Zeichen lesen und schreiben, der von einem Turingprogramm gesteuert wird. Falls sich auf diesem eine endliche Menge von Daten befinden, ist der Rest des Datenstreifens mit dem Zeichen 0 (Null) beschrieben. Der Kopf befindet am Anfang immer im Zustand Z1.
Beim "fleißigen Biber" befindet sich der Lese/Schreibkopf zuerst an irgendeiner Stelle des Bandes, das ausschließlich mit Nullen belegt ist. Er soll möglichst viele Einsen schreiben. Für den Fall, dass er nur einen Zustand haben kann, wäre es trivial. Als Tabelle sieht dieser Turingbefehl so aus:
Die Turingmaschine - www.larskiesow.de/
Mit dieser Information gelang es mir als Laie dann endlich, auch das Prinzip des fleißigen Bibers zu verstehen. Trotzdem glaube ich, dass es auch mit dieser sehr ausführlichen Erklärung immer noch ziemlich schwer verständlich ist, und möchte deswegen an dieser Stelle das auf meine Weise erklären, damit es auch Nichtinformatiker möglichst schnell verstehen können.
Auf einem theoretisch unendlich langen Datenstreifen kann ein Lese- / Schreibkopf Zeichen lesen und schreiben, der von einem Turingprogramm gesteuert wird. Falls sich auf diesem eine endliche Menge von Daten befinden, ist der Rest des Datenstreifens mit dem Zeichen 0 (Null) beschrieben. Der Kopf befindet am Anfang immer im Zustand Z1.
Beim "fleißigen Biber" befindet sich der Lese/Schreibkopf zuerst an irgendeiner Stelle des Bandes, das ausschließlich mit Nullen belegt ist. Er soll möglichst viele Einsen schreiben. Für den Fall, dass er nur einen Zustand haben kann, wäre es trivial. Als Tabelle sieht dieser Turingbefehl so aus:
- Code: Alles auswählen
Gelesenes Zeichen 0 · Gelesenes Zeichen 1
Jetziger · Schreibe · Bewege · Neuer · Schreibe · Bewege · Neuer
Zustand Zustand Zustand
Z1 1 H Z1 · 1 H Z1
Erklärung: Der linke Teil der Tabelle: Wenn du eine 0 (Null) liest und dich im Zustand Z1 befindest, schreibe eine 1, halte an und bleibe im Zustand Z1!
Der rechte Teil der Tabelle: Wenn du eine 1 liest, und dich im Zustand Z1 befindest, schreibe eine 1, halte an und bleibe im Zustand Z1!
Der zweite (untere) Turingbefehl ist in diesem Fall wirkungslos, weil im gesamten Ablauf immer jeweils eine 0 gelesen wird. Man kann diese beiden Turingbefehle auch so ausdrücken:
(Z1, 0) -> (Z1, 1, H)
(Z1, 1) -> (Z1, 1, H)
In der linken Klammer stehen die zwei Bedingungen, die beide erfüllt sein müssen, wenn die drei Anweisungen in der rechten Klammer ausgeführt werden sollen.
Linke Klammer: Z1 ist die eine Bedingung und bedeutet, dass sich der Kopf im Zustand Z1 befinden muss. die 0 (Null) bedeutet, dass wenn der Kopf eine Null ließt, dass dann die zweite Bedingung erfüllt ist.
Wenn beide Bedingungen jeweils erfüllt sind, soll die hinter dem Pfeil (->) angegebene Anweisung ausgeführt werden.
In diesem Fall trifft nur der obere Befehl zu. Die Anweisung (Z1, 1, H) bedeutet: Bleibe im Zustand Z1, schreibe eine 1 und halte an (H)!
Wichtig ist, dass die Turingmaschine (bzw. der Biber) irgendwann seine Arbeit beendet, was in diesem Fall nicht so wäre:
- Code: Alles auswählen
Gelesenes Zeichen 0 · Gelesenes Zeichen 1
Jetziger · Schreibe · Bewege · Neuer · Schreibe · Bewege · Neuer
Zustand Zustand Zustand
Z1 1 R Z1 · H
Diese Tabelle enthält 2 Turingbefehle, die man auch so schreiben kann:
(Z1, 0) -> (Z1, 1, R)
(Z1, 1) -> ( [COLOR="silver"]·[/COLOR] , [COLOR="Silver"]·[/COLOR] , H)
In diesem Fall wird eine 0 Gelesen. Das Programm weist den Kopf an, eine 1 zu schreiben und sich um ein Feld nach rechts zu bewegen. Dort liest der Kopf wieder eine 0. Deswegen muss der Kopf dann wieder diese Anweisung befolgen, also wieder eine 1 schreiben und sich wieder ein Feld nach rechts bewegen, und so weiter.
Auf diese Weise werden unendlich viele Einsen geschrieben, wodurch die Turingmaschine nie anhalten wird, was nicht das Ziel ist. Der zweite Turingbefehl ist in diesem Fall gegenstandslos.
Wenn der "fleißige Biber" 2 Zustände annehmen kann, kann er sogar 4 Einsen schreiben, falls die Turingbefehle so gesetzt sind:
- Code: Alles auswählen
Gelesenes Zeichen 0 · Gelesenes Zeichen 1
Jetziger · Schreibe · Bewege · Neuer · Schreibe · Bewege · Neuer
Zustand Zustand Zustand
Z1 1 L Z2 · 1 R Z2
Z2 1 R Z1 · H
(Z1, 0) -> (Z2, 1, L)
(Z1, 1) -> (Z2, 1, R)
(Z2, 0) -> (Z1, 1, R)
(Z2, 1) -> ( [COLOR="Silver"]·[/COLOR] , [COLOR="silver"]·[/COLOR] , H)
Das ist die Ausgangssituation:
- Code: Alles auswählen
¥
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Der Kopf befindet sich zuerst im Zustand Z1, folglich muss nur einer von beiden Anweisungen der oberen Tabellenzeile ausgeführt werden.
Weil eine 0 gelesen wird, muss die linke Anweisung ausgeführt werden, die besagt, dass eine 1 geschrieben werden soll, der Kopf ein Feld nach links gehen und den Zustand Z2 annehmen soll. Die Turingmaschine befindet sich nach Ausführung dieser Anweisung in diesem Zustand:
- Code: Alles auswählen
¥
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
Der Kopf befindet sich nun im Zustand Z2, folglich muss nur einer von beiden Anweisungen der unteren Tabellenzeile ausgeführt werden.
Weil eine 0 gelesen wird, muss die linke Anweisung ausgeführt werden, die besagt, dass eine 1 geschrieben werden soll, der Kopf ein Feld nach rechts gehen und den Zustand Z1 annehmen soll. Die Turingmaschine befindet sich nach Ausführung dieser Anweisung in diesem Zustand:
- Code: Alles auswählen
¥
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
Der Kopf befindet sich nun im Zustand Z1, folglich muss nur einer von beiden Anweisungen der oberen Tabellenzeile ausgeführt werden.
Weil eine 1 gelesen wird, muss die rechte Anweisung ausgeführt werden, die besagt, dass eine 1 geschrieben werden soll, der Kopf ein Feld nach rechts gehen und den Zustand Z2 annehmen soll. Die Turingmaschine befindet sich nach Ausführung dieser Anweisung in diesem Zustand:
- Code: Alles auswählen
¥
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
Der Kopf befindet sich nun im Zustand Z2, folglich muss nur einer von beiden Anweisungen der unteren Tabellenzeile ausgeführt werden.
Weil eine 0 gelesen wird, muss die linke Anweisung ausgeführt werden, die besagt, dass eine 1 geschrieben werden soll, der Kopf ein Feld nach rechts gehen und den Zustand Z1 annehmen soll. Die Turingmaschine befindet sich nach Ausführung dieser Anweisung in diesem Zustand:
- Code: Alles auswählen
¥
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0
Der Kopf befindet sich nun im Zustand Z1, folglich muss nur einer von beiden Anweisungen der oberen Tabellenzeile ausgeführt werden.
Weil eine 0 gelesen wird, muss die linke Anweisung ausgeführt werden, die besagt, dass eine 1 geschrieben werden soll, der Kopf ein Feld nach links gehen und den Zustand Z2 annehmen soll. Die Turingmaschine befindet sich nach Ausführung dieser Anweisung in diesem Zustand:
- Code: Alles auswählen
¥
0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
Der Kopf befindet sich nun im Zustand Z2, folglich muss nur einer von beiden Anweisungen der unteren Tabellenzeile ausgeführt werden.
Weil eine 1 gelesen wird, muss die rechte Anweisung ausgeführt werden, die besagt, dass der Kopf anhalten soll (Programmende). Die Turingmaschine befindet sich nach Ausführung dieser Anweisung in diesem Zustand:
- Code: Alles auswählen
¥
0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0
Wie man sieht, ist dieser Befehl eigentlich gegenstandslos; denn wenn er nicht existieren würde, gäbe es zwar keinen Haltbefehl; aber der Vorgang würde trotzdem anhalten wegen fehlendem Turingbefehl in dieser Position des Kopfes.
Wenn der "fleißige Biber" 3 Zustände annehmen kann, kann er (maximal) 6 Einsen schreiben, falls die Turingbefehle so gesetzt sind:
- Code: Alles auswählen
Gelesenes Zeichen 0 · Gelesenes Zeichen 1
Jetziger · Schreibe · Bewege · Neuer · Schreibe · Bewege · Neuer
Zustand Zustand Zustand
Z1 1 R Z2 · 1 L Z3
Z2 1 R Z3 · 1 H
Z3 1 L Z1 · 0 L Z2
(Z1, 0) -> (Z2, 1, R)
(Z1, 1) -> (Z3, 1, L)
(Z2, 0) -> (Z3, 1, R)
(Z2, 1) -> ( ,1 , H)
(Z3, 0) -> (Z1, 1, L)
(Z3, 1) -> (Z2, 0, L)
Wenn der "fleißige Biber" 4 Zustände annehmen kann, kann er (maximal) 13 Einsen schreiben, falls die Turingbefehle so gesetzt sind:
- Code: Alles auswählen
Gelesenes Zeichen 0 · Gelesenes Zeichen 1
Jetziger · Schreibe · Bewege · Neuer · Schreibe · Bewege · Neuer
Zustand Zustand Zustand
Z1 1 R Z2 · 1 L Z2
Z2 1 L Z1 · 0 L Z3
Z3 1 H · 1 L Z4
Z4 1 R Z4 · 0 R Z1
(Z1, 0) -> (Z2, 1, R)
(Z1, 1) -> (Z2, 1, L)
(Z2, 0) -> (Z1, 1, L)
(Z2, 1) -> (Z3, 0, L)
(Z3, 0) -> ( , 1, H)
(Z3, 1) -> (Z4, 1, L)
(Z4, 0) -> (Z4, 1, R)
(Z4, 1) -> (Z1, 0, R)
Wenn der "fleißige Biber" 5 Zustände annehmen kann, kann er (maximal) 4098 Einsen schreiben, falls die Turingbefehle so gesetzt sind:
- Code: Alles auswählen
Gelesenes Zeichen 0 · Gelesenes Zeichen 1
Jetziger · Schreibe · Bewege · Neuer · Schreibe · Bewege · Neuer
Zustand Zustand Zustand
Z1 1 R Z2 · 1 L Z3
Z2 1 R Z3 · 1 R Z2
Z3 1 R Z4 · 0 L Z5
Z4 1 L Z1 · 1 L Z4
Z5 1 H · 0 L Z1
(Z1, 0) -> (Z2, 1, R)
(Z1, 1) -> (Z3, 1, L)
(Z2, 0) -> (Z3, 1, R)
(Z2, 1) -> (Z2, 1, R)
(Z3, 0) -> (Z4, 1, R)
(Z3, 1) -> (Z5, 0, L)
(Z4, 0) -> (Z1, 1, L)
(Z4, 1) -> (Z4, 1, L)
(Z5, 0) -> ( , 1, H)
(Z5, 1) -> (Z1, 0, L)
Die Angaben für die "fleißigen Biber" habe ich dieser Webseite entnommen:
biber.htm - Fleißige Biber - www.dbg.rt.bw.schule.de/
Das Besondere ist, dass ein Biber mit 6 Zuständen mehr als 1,29 mal 10 hoch 865 Einsen schreiben kann.
Auf dieser Webseite befindet sich ein Simulator, mit dem man sich auf die Suche nach weiteren Bibern begeben kann, bzw. nach weiteren Turingbefehlen suchen kann. Das dürfte praktisch aber sinnlos sein, weil schon genug Informatiker sich mit Hochgeschwindigkeitsrechnern auf die Suche gemacht haben durch Probieren.
"Fleißiger Biber" - Simulator - www.fmi.uni-stuttgart.de
Der funktioniert (wenn überhaupt) so: Rechts oben stellt man bei den drei oberen Einstellmöglichkeiten die jeweils auszuführende Anweisung ein. Dann klickt man jeweils links oben nach jeder erfolgten Einstellung auf diejenige Schaltfläche, die diese Einstellung übernehmen soll. Diese Tabelle entspricht im Prinzip der Tabellen in diesem Beitrag.
Man kann auch rechts oben bei der 4. Einstellungsmöglichkeit von oben eine Voreinstellung wählen. Bei mir funktioniert dieses Programm leider nicht richtig, es kommen nur falsche Ergebnisse im Feld, das die Anzahl der geschriebenen Einsen nach Abschluss des Rechenvorganges angibt (hinter "Number of ``1"-Symbols").
biber.htm - Fleißige Biber - www.dbg.rt.bw.schule.de/
Das Besondere ist, dass ein Biber mit 6 Zuständen mehr als 1,29 mal 10 hoch 865 Einsen schreiben kann.
Auf dieser Webseite befindet sich ein Simulator, mit dem man sich auf die Suche nach weiteren Bibern begeben kann, bzw. nach weiteren Turingbefehlen suchen kann. Das dürfte praktisch aber sinnlos sein, weil schon genug Informatiker sich mit Hochgeschwindigkeitsrechnern auf die Suche gemacht haben durch Probieren.
"Fleißiger Biber" - Simulator - www.fmi.uni-stuttgart.de
Der funktioniert (wenn überhaupt) so: Rechts oben stellt man bei den drei oberen Einstellmöglichkeiten die jeweils auszuführende Anweisung ein. Dann klickt man jeweils links oben nach jeder erfolgten Einstellung auf diejenige Schaltfläche, die diese Einstellung übernehmen soll. Diese Tabelle entspricht im Prinzip der Tabellen in diesem Beitrag.
Man kann auch rechts oben bei der 4. Einstellungsmöglichkeit von oben eine Voreinstellung wählen. Bei mir funktioniert dieses Programm leider nicht richtig, es kommen nur falsche Ergebnisse im Feld, das die Anzahl der geschriebenen Einsen nach Abschluss des Rechenvorganges angibt (hinter "Number of ``1"-Symbols").
In die drei Felder links unten gibt man ausreichend hohe Obergrenzen an. Wenn zu wenig angeben wird, bricht das Programm den Vorgang zu früh ab. Wenn man zuviel angegeben hat, kann man nach einem Vorgang nur dann den nächsten starten, wenn man alle Eingaben links oben mit "reset table" entfernt hat.
Um zu vermeiden die Turingbefehle erneut eingeben zu müssen, kann es einfacher sein, nach einem Rechenvorgang die großen Werte durch ausreichend kleine zu ersetzen.
Dann klickt man unten die schaltfläche so oft, bis auf dieser geschrieben steht: "press button to run simulation!". Dann kann man in die unteren drei Felder wieder die größeren Höchstwerte angeben und dann das Programm wieder starten.
Will man die bereits gefundenen Werte mit diesem Simulator überprüfen, macht man jeweils diese Angeben, wobei bspw. Q0 ein Biber mit einem Zustand bedeutet. Q1 ist ein Biber mit 2 Zuständen und so weiter.
Um zu vermeiden die Turingbefehle erneut eingeben zu müssen, kann es einfacher sein, nach einem Rechenvorgang die großen Werte durch ausreichend kleine zu ersetzen.
Dann klickt man unten die schaltfläche so oft, bis auf dieser geschrieben steht: "press button to run simulation!". Dann kann man in die unteren drei Felder wieder die größeren Höchstwerte angeben und dann das Programm wieder starten.
Will man die bereits gefundenen Werte mit diesem Simulator überprüfen, macht man jeweils diese Angeben, wobei bspw. Q0 ein Biber mit einem Zustand bedeutet. Q1 ist ein Biber mit 2 Zuständen und so weiter.
Biber mit 2 Zuständen:
Q0: Q1 1 L - Q1 1 R
Q1: Q0 1 R - Q0 1 H
Biber mit 3 Zuständen:
Q0: Q1 1 R - Q2 1 L
Q1: Q2 1 R - Q0 1 H
Q2: Q0 1 L - Q1 0 L
Biber mit 4 Zuständen:
Q0: Q1 1 R - Q1 1 L
Q1: Q0 1 L - Q2 0 L
Q2: Q0 1 H - Q3 1 L
Q3: Q3 1 R - Q0 0 R
Biber mit 5 Zuständen:
Q0: Q1 1 L - Q0 1 L
Q1: Q2 1 R - Q1 1 R
Q2: Q0 1 L - Q3 1 R
Q3: Q0 1 L - Q4 1 R
Q4: Q0 1 H - Q2 0 R
Googlesuche für mehr Infos über dieses mathematische Phänomen:
"Fleißiger Biber" - Google-Suche
Ein großes Problem ist bei der Funktion des fleißigen Bibers, dass ein Rechenvorgang aufgrund der jeweiligen Turingbefehle oftmals kein Ende finden kann, sodass das Programm unendlich lange weiterläuft. Wichtig ist deswegen, dass der Biber irgendwann in den Stopzustand kommt.
Es wird behauptet, dass es Funktionen gibt, die nicht berechenbar sind, und diese Funktion (angeblich) eine solche sei. Ich habe mir darüber Gedanken gemacht und glaube das aber nicht, dass diese Funktion nicht berechenbar ist. Es gibt Beweisverfahren, wo das aber (angeblich) bewiesen wurde, dass diese Funktion nicht berechenbar sei.
Ich bin zwar kein Experte auf dem Gebiet Informatik und Mathematik, aber mir scheint, dass schon bei diesem Beweisverfahren Fehler unterlaufen sind. Da wird bspw. davon ausgegangen, dass der "fleißige Biber" eine Funktion sei; was bedeuten würde, dass zu jedem n (Anzahl der Zustände) jeweils ein Funktionswert zugeordnet ist, der in diesem Fall die größtmögliche Anzahl der geschriebenen Einsen ist.
Wenn man es sich aber mal richtig überlegt, halte ich schon diese Voraussetzung für nicht bewiesen; weil ich nämlich glaube, dass ab einer bestimmten Größe von n es keine Lösung mehr gibt; weil nicht mit Sicherheit ausgeschlossen werden kann, dass diese Turingmaschine bei jeder Kombination von Turingbefehlen ohne Halt laufen würde, wovon ich ausgehe.
Damit würde auch die Voraussetzung des Beweises nicht stimmen, dass je größer n ist, dass dann die Anzahl der maximal möglichen Einsen auch umso größer ist. Das trifft aber mit Sicherheit nur bis n=6 zu.
Es scheint bei diesem Phänomen zwar so zu sein, dass die Anzahl der geschriebenen Einsen gigantisch ab n=5 zunimmt. Es scheint aber auch so zu sein, dass diese Funktion umso mehr dazu neigt, dass das Programm nicht anhält, je höher n ist.
Das würde also auch bedeuten, dass ab einer bestimmten Größe von n es keine Kombination von Turingbefehlen mehr gibt, die eine Rechnung mit Halt ergibt. Was dann aber bedeutet, dass es ab diesem Punkt keine Lösung mehr gäbe.
Mich erinnert das auch etwas an das physikalische Phänomen der Rückkopplung, wenn ein Mikrofon zu nahe am Lautsprecher ist. Ab einem gewissen Abstand nimmt die Verstärkung dramatisch zu; aber über einem bestimmten Punkt, findet keine Verstärkung mehr statt, sondern es pfeift nur noch grässlich, was nicht der Zweck einer Lautsprecheranlage ist.
Ich glaube einfach, dass im Prinzip alles berechenbar ist; man hat bis jetzt nur noch nicht für jedes mathematische Problem einen Lösungsalgorithmus gefunden.
Ich habe in der Wikipedia geschaut, was das Wort 'Funktion' bedeutet. In der Mathematik hat es eine andere Bedeutung als in der Informatik, wo es nur ein Programmierkonzept ist.
Prinzipiell entsteht da schon ein Widerspruch; denn in der Mathematik setzt eine Funktion voraus, dass jeder Eingangsgröße einen Funktionswert zuordnet wird, was bei einem Programmierkonzept nicht unbedingt der Fall sein muss.
"Fleißiger Biber" - Google-Suche
Ein großes Problem ist bei der Funktion des fleißigen Bibers, dass ein Rechenvorgang aufgrund der jeweiligen Turingbefehle oftmals kein Ende finden kann, sodass das Programm unendlich lange weiterläuft. Wichtig ist deswegen, dass der Biber irgendwann in den Stopzustand kommt.
Es wird behauptet, dass es Funktionen gibt, die nicht berechenbar sind, und diese Funktion (angeblich) eine solche sei. Ich habe mir darüber Gedanken gemacht und glaube das aber nicht, dass diese Funktion nicht berechenbar ist. Es gibt Beweisverfahren, wo das aber (angeblich) bewiesen wurde, dass diese Funktion nicht berechenbar sei.
Ich bin zwar kein Experte auf dem Gebiet Informatik und Mathematik, aber mir scheint, dass schon bei diesem Beweisverfahren Fehler unterlaufen sind. Da wird bspw. davon ausgegangen, dass der "fleißige Biber" eine Funktion sei; was bedeuten würde, dass zu jedem n (Anzahl der Zustände) jeweils ein Funktionswert zugeordnet ist, der in diesem Fall die größtmögliche Anzahl der geschriebenen Einsen ist.
Wenn man es sich aber mal richtig überlegt, halte ich schon diese Voraussetzung für nicht bewiesen; weil ich nämlich glaube, dass ab einer bestimmten Größe von n es keine Lösung mehr gibt; weil nicht mit Sicherheit ausgeschlossen werden kann, dass diese Turingmaschine bei jeder Kombination von Turingbefehlen ohne Halt laufen würde, wovon ich ausgehe.
Damit würde auch die Voraussetzung des Beweises nicht stimmen, dass je größer n ist, dass dann die Anzahl der maximal möglichen Einsen auch umso größer ist. Das trifft aber mit Sicherheit nur bis n=6 zu.
Es scheint bei diesem Phänomen zwar so zu sein, dass die Anzahl der geschriebenen Einsen gigantisch ab n=5 zunimmt. Es scheint aber auch so zu sein, dass diese Funktion umso mehr dazu neigt, dass das Programm nicht anhält, je höher n ist.
Das würde also auch bedeuten, dass ab einer bestimmten Größe von n es keine Kombination von Turingbefehlen mehr gibt, die eine Rechnung mit Halt ergibt. Was dann aber bedeutet, dass es ab diesem Punkt keine Lösung mehr gäbe.
Mich erinnert das auch etwas an das physikalische Phänomen der Rückkopplung, wenn ein Mikrofon zu nahe am Lautsprecher ist. Ab einem gewissen Abstand nimmt die Verstärkung dramatisch zu; aber über einem bestimmten Punkt, findet keine Verstärkung mehr statt, sondern es pfeift nur noch grässlich, was nicht der Zweck einer Lautsprecheranlage ist.
Ich glaube einfach, dass im Prinzip alles berechenbar ist; man hat bis jetzt nur noch nicht für jedes mathematische Problem einen Lösungsalgorithmus gefunden.
Ich habe in der Wikipedia geschaut, was das Wort 'Funktion' bedeutet. In der Mathematik hat es eine andere Bedeutung als in der Informatik, wo es nur ein Programmierkonzept ist.
Prinzipiell entsteht da schon ein Widerspruch; denn in der Mathematik setzt eine Funktion voraus, dass jeder Eingangsgröße einen Funktionswert zuordnet wird, was bei einem Programmierkonzept nicht unbedingt der Fall sein muss.
Der fleißige Biber wird als Funktion bezeichnet, aber in welchem Sinn? Im mathematischen oder im informellen bzw. programmiertechnischen Sinn? Im mathematischen Sinn kann man den fleißigen Biber wahrscheinlich nicht als Funktion bezeichnen, ich gehe mal davon aus, dass ab einer bestimmten Größe für n es keinen Funktionswert mehr gibt.
Bspw. beim Rubikwürfel wurde ein Algorithmus gefunden, um ihn mit verhältnismäßig geringem Aufwand in den richtigen Zustand zu bringen. Warum sollte das nicht auch bei allen anderen Problemen möglich sein?
Man sollte immer vorsichtig sein, auch dann, wenn was (angeblich) bewiesen wurde. Auch Beweise können Fehler enthalten, weil der Mensch nicht vollkommen ist. In der Physik hatte man das auch geglaubt, dass die gefundenen Naturgesetze völlig richtig seien, bis Einstein das Gegenteil bewies.
Heutzutage beweisen wiederum Wissenschaftler, dass auch seine Theorien nicht immer absolut wahr zutreffen; dass bspw. eine Informationsübertragung unter bestimmten Umständen auch schneller als Lichtgeschwindigkeit erfolgen kann.
Es sollte kein Wissenschaftler oder Experte so vermessen sein, gegenwärtig als gesichert angesehene Erkenntnisse als absolut zweifelsfrei anzusehen. Es ist immer jeweils nur eine Frage der Zeit, bis jemand kommt und eine neue Erkenntnis bringt, bzw. Fehler aufdeckt.
Es ist wirklich ein Jammer, wie Menschen ihre Erkenntnisse hinter Fachbegriffen verstecken, wo ein Außenstehender kaum noch was verstehen kann. Z.B. der fleißige Biber. Mit ganz einfachen Wörtern kann man erklären, wie diese Funktion zu verstehen ist. Aber wenn man im Web sucht, findet man fast nur schwer verständliche Erklärungsversuche; oftmals mit allen möglichen Fachbegriffen durchsetzt.
Wo man geistig nicht fähig oder nicht Willens ist, so zu kommunizieren, dass es auch ein Außenstehender verstehen kann, da schwindet natürlich dann auch das Vertrauen in die Erkenntnisse und Lehrsätze dieser hohen Herren Wissenschaftler.
Vielleicht gibt es doch Leute, die es interessiert, was der fleißige Biber überhaupt ist. Ich meine, wenn er bis ins Detail die Funktionsweise verstehen möchte, und nicht nur wie aus der Vogelperspektive was weiß, wie da so ungefähr was ist.
Unter den ca. 30 Webseiten zu diesem Thema waren etliche sogar ziemlich umfangreich, aber trotzdem nicht besonders einfach zu verstehen. Ich fand dazu nur eine einzige Webseite, die wenigstens einigermaßen verständlich geschrieben war, jedoch bemängele ich, dass man erst mal die Beschreibung für die Turingmaschine studieren muss, bevor man den fleißigen Biber verstehen kann.
Mit meiner Beschreibung habe ich versucht, den fleißigen Biber direkt zu erklären, ohne lange das Prinzip der Turingmaschine an Beispielen zu erklären. Ich erklärte einfach das Prinzip der Turingmaschine direkt am Beispiel des fleißigen Bibers, um so dem interessierten Leser einen doch möglichst schnellen Einstieg zu ermöglichen, was mir doch hoffentlich gelungen ist.
Es war mir von Anfang an klar, dass eine für den Laien verständliche Erklärung nur durch ein Mindestmaß an Ausführlichkeit möglich ist, sodass sich doch ein beträchtlicher Textumfang ergeben hatte, der sich aber meines Erachtens doch in Grenzen hält.
Bspw. beim Rubikwürfel wurde ein Algorithmus gefunden, um ihn mit verhältnismäßig geringem Aufwand in den richtigen Zustand zu bringen. Warum sollte das nicht auch bei allen anderen Problemen möglich sein?
Man sollte immer vorsichtig sein, auch dann, wenn was (angeblich) bewiesen wurde. Auch Beweise können Fehler enthalten, weil der Mensch nicht vollkommen ist. In der Physik hatte man das auch geglaubt, dass die gefundenen Naturgesetze völlig richtig seien, bis Einstein das Gegenteil bewies.
Heutzutage beweisen wiederum Wissenschaftler, dass auch seine Theorien nicht immer absolut wahr zutreffen; dass bspw. eine Informationsübertragung unter bestimmten Umständen auch schneller als Lichtgeschwindigkeit erfolgen kann.
Es sollte kein Wissenschaftler oder Experte so vermessen sein, gegenwärtig als gesichert angesehene Erkenntnisse als absolut zweifelsfrei anzusehen. Es ist immer jeweils nur eine Frage der Zeit, bis jemand kommt und eine neue Erkenntnis bringt, bzw. Fehler aufdeckt.
Es ist wirklich ein Jammer, wie Menschen ihre Erkenntnisse hinter Fachbegriffen verstecken, wo ein Außenstehender kaum noch was verstehen kann. Z.B. der fleißige Biber. Mit ganz einfachen Wörtern kann man erklären, wie diese Funktion zu verstehen ist. Aber wenn man im Web sucht, findet man fast nur schwer verständliche Erklärungsversuche; oftmals mit allen möglichen Fachbegriffen durchsetzt.
Wo man geistig nicht fähig oder nicht Willens ist, so zu kommunizieren, dass es auch ein Außenstehender verstehen kann, da schwindet natürlich dann auch das Vertrauen in die Erkenntnisse und Lehrsätze dieser hohen Herren Wissenschaftler.
Vielleicht gibt es doch Leute, die es interessiert, was der fleißige Biber überhaupt ist. Ich meine, wenn er bis ins Detail die Funktionsweise verstehen möchte, und nicht nur wie aus der Vogelperspektive was weiß, wie da so ungefähr was ist.
Unter den ca. 30 Webseiten zu diesem Thema waren etliche sogar ziemlich umfangreich, aber trotzdem nicht besonders einfach zu verstehen. Ich fand dazu nur eine einzige Webseite, die wenigstens einigermaßen verständlich geschrieben war, jedoch bemängele ich, dass man erst mal die Beschreibung für die Turingmaschine studieren muss, bevor man den fleißigen Biber verstehen kann.
Mit meiner Beschreibung habe ich versucht, den fleißigen Biber direkt zu erklären, ohne lange das Prinzip der Turingmaschine an Beispielen zu erklären. Ich erklärte einfach das Prinzip der Turingmaschine direkt am Beispiel des fleißigen Bibers, um so dem interessierten Leser einen doch möglichst schnellen Einstieg zu ermöglichen, was mir doch hoffentlich gelungen ist.
Es war mir von Anfang an klar, dass eine für den Laien verständliche Erklärung nur durch ein Mindestmaß an Ausführlichkeit möglich ist, sodass sich doch ein beträchtlicher Textumfang ergeben hatte, der sich aber meines Erachtens doch in Grenzen hält.