Diskussion:Fleißiger Biber
aus Wikipedia, der freien Enzyklopädie
Woher stammt denn die Bezeichnung "Fleißiger Biber"? --Zinnmann d 08:30, 2. Mär 2005 (CET)
- Auf jeden Fall aus dem englischen. Ich sehe die Verbindung darin, dass ein kleines Progrämmchen eine große Aufgabe in mühevoller Arbeit bewältigt, also sehr viele Einsen anhäuft, also ebenso wie ein Biber viele kleine Zweige zusammenträgt um einen Staudamm zu bilden. Andere Frage, die jetzige Position der Tabelle entstellt den Text etwas. Ich denke, bei der Kürze des Textes findet der Leser auch den Zusammenhang, wenn die Tabelle oben ist. --Suricata 09:29, 2. Mär 2005 (CET)
Inhaltsverzeichnis |
[Bearbeiten] Berechenbarkeit vs. Entscheidbarkeit
Probleme sind nicht „berechenbar“ oder „nicht berechtbar“, sondern „entscheidbar“ oder „unentscheidbar“! Allerdings frage ich mich, ob man nicht einfach allgemein von der Funktion Sprechen sollte, da ich nicht genau weiß, wie das Problem definiert ist. --FAR 21:55, 30. Jun 2005 (CEST)
- Ich weiß nicht, ob das so richtig ist. Überhaupt ist der deutsche Text im Vergleich zum englischen sehr dürftig. Wenn ich das richtig verstanden habe, ist die Besonderheit des Busy Beavers ja, dass die Funktion sehr wohl (beweisbar) immer ein eindeutiges Ergebnis hat, es allerdings keinen Algorithmus geben kann, der die Funktion für alle n löst. Außerdem steigt die Funktion schneller an, als jede berechenbare (entscheidbare?) Funktion. --MX² 23:46, 7. Aug 2005 (CEST)
Also FAR macht sich meiner Meinung nach die Sache etwas zu einfach. Es ist für eine Sprache entscheidbar, ob eine Eingabe x zu ihr gehört oder nicht. Ferner gehört zu jeder Sprache ihre charakteristische Funktion, welche im Falle der rekursiven Sprachen (turing)-berechenbar ist. Das wollte ich mal ergänzt wissen...
Ein Problem wird stets als Relation beschrieben: Eine Aufgabenstellung steht in Relation zu einer Lösung. Im einfachsten Fall ist ein Problem, wie FAR bemerkt, ein Entscheidungsproblem: Zu einer Eingabe ist ja oder nein zu berechnen. Das BusyBeaverProblem ist aber eine Funktion: zu einer Zahl n ist die maximal erzeugbare Anzahl von Strichen einer entsprechenden TM zu berechnen, die mit n Zuständen hält und diese Striche dann auf das eingangs leere Band geschrieben hat.
- Die BusyBeaverFunktion ist nicht berechenbar.
- Die Menge der Werte, die sie annimmt ist nicht entscheidbar, ja sogar nicht rekursiv aufzählbar!
- Es gilt sogar, dass das Komplement dieser Menge nicht rekursiv aufzählbar ist!
In der Rekursionstheorie definiert man die arithmetische Hierrarchie und weil der Wertebereich der BeasyBeaverZahlen so leicht zu definieren ist, erhält man hiermit ein erstes einfaches Beispiel außerhalb der ersten Hierarchiebene.
Grüße
--Gerhard Buntrock 02:52, 31. Aug 2005 (CEST)
[Bearbeiten] Überarbeitung
Folgende fundamentalen Änderungen durchgeführt:
- 'Mathematisches Problem' rausgenommen. Scheint mir an dieser Stelle irrelevant und nur mit entferntem Bezug.
- Symbolmenge auf {0, 1} statt Blank und Strich geändert, damit meine Illustration passt. (Die ist schon etwas älter und ich war zu faul sie anzupassen.)
Dichotomie σ(n)/Σ(n) entfernt. Die Definition von Rado mit zusammenhägenden Ketten von Einsen ist die ursprüngliche und die Tabelle bezieht sich auch darauf. Artikel konsistent auf diese Definition umgstellt.--Rtc 04:35, 7. Sep 2005 (CEST)
Der letzte Punkt ist fehlerhaft. Werde mich darum kümmern, wenn ich im Turing-Omnibus nochmal genau nachgeschaut habe. --Rtc 18:53, 12. Sep 2005 (CEST)
Erledigt --Rtc 19:20, 13. Sep 2005 (CEST)
fände es gut, wenn der vergleich zum mathematischen problem wieder reingenommen wird. das war das einzige was mich den fleißigen biber wenigstens ansatzweise hat verstehen lassen. der artikel ist für laien recht unverständlich, gibt es da noch irgendwelche konkreteren beispiele?
[Bearbeiten] Implementierung
Fehlt in dem Artikel nicht sowas wie eine Beispielsimplementierung? --Abdull 20:29, 5. Mär 2006 (CET)
[Bearbeiten] Unverständlichkeit
Ich weiß nicht, wie schwierig das ist, aber könnte das jemand so formulieren, dass das auch Leute verstehen können, die keine Informatik studiert haben? Asgar 20:05, 26. Mär 2006 (CEST)
- In der Tat. Der Artikel war in einer früheren Version verständlicher. --Suricata 23:04, 26. Mär 2006 (CEST)
- Vorsicht, diese Version ist fehlerhaft: "Gesucht ist das Programm einer Turing-Maschine mit n Zuständen, das möglichst viele, aber nicht unendlich viele Einsen auf das Band schreibt." Es gibt trivialerweise Turing-Maschinen, die nicht halten, aber trotzdem nur eine endliche Anzahl von einsen schreiben. Das würde aber wohl nicht mehr der ursprünglichen Definition der fleißigen Bibers entsprechen. --Rtc 10:01, 5. Apr 2006 (CEST)
- Ich habe mal als ersten Schritt die Einleitung vereinfacht, sowie den gesamten bisherigen Text in einen Abschnitt "Formelle Betrachtung" verschoben. Natürlich sollte der gesamte Inhalt in einer zugänglicheren Form formuliert werden, nicht nur die Einleitung. Nczempin 17:55, 29. Mär 2006 (CEST)
- Studier erst im 2ten Semester Mathematik aber habe hier im Gegensatz zur sehr gut erklärten Ackermann-Funktion leider nicht verstanden. Wo ist überhaupt eine Funktion? Werden einfach Computer betrachtet und darauf gewettet das sie immer einsen schreiben und dann die Wahrscheinlichkeit ausgerechnet? kommentator22:11, 22.April 2008 (CEST)
[Bearbeiten] "..werden manchmal ... bezeichnet"
"Fleißige Biber werden manchmal als wissenschaftliche Spielerei der Theoretischen Informatik bezeichnet." Von wem werden sie so bezeichnet? "Manchmal" ist schwammig. Mein Vorschlag: Satz streichen. Nczempin 17:24, 28. Mär 2006 (CEST)
- Update: Satz gestrichen, im Zuge der Umstrukturierung. Nczempin 17:56, 29. Mär 2006 (CEST)
[Bearbeiten] Alternative Definitionen des Busy Beaver vernachlässigt
Es gibt auch alternative Definitionen des Busy Beaver, zum Beispiel nicht generell die Anzahl der Einsen, die ausgegeben werden können, sondern die Anzahl der Einsen, die maximal zusammenhängend ausgegeben werden können. Oder aber die maximale Anzahl an Rechenschritten, die ein solches Programm ausführen kann, bevor es terminiert, unabhängig von irgendetwas anderem wie Ausgabe, etc.
_________________________________
Das stimmt so nicht. Die Literatur der Theoretischen Informatik ist sich einig, wie die Funktionen von Rado und der Busy Beaver jeweils definiert sind. Leider ist der Zustand des Artikels zur Zeit katastrophal und falsch!
Vielleicht kümmere ich mich demnächst mal drum.
--Gerhard Buntrock 19:51, 19. Apr. 2007 (CEST)
[Bearbeiten] Anzahl an Turingmaschinen
Wie kommt man auf diese großen Zahlen? 144?!? -- 84.173.119.194 11:05, 2. Nov. 2007 (CET)
