Diskussion:Fleißiger Biber

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)

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)

Ü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 $\sigma (n)$ / $\Sigma (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?

Implementierung

Fehlt in dem Artikel nicht sowas wie eine Beispielsimplementierung? --Abdull 20:29, 5. Mär 2006 (CET)

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)

"..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)

Alternative Definitionen des Busy Beaver vernachlässigt

Letzter Kommentar: vor 18 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

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)Beantworten

Anzahl an Turingmaschinen

Letzter Kommentar: vor 14 Jahren7 Kommentare6 Personen sind an der Diskussion beteiligt

Wie kommt man auf diese großen Zahlen? 144?!? -- 84.173.119.194 11:05, 2. Nov. 2007 (CET)Beantworten

Nach 19 Monaten die Antwort: Bei einem Zustand brauchst du eine Übergangsfunktion, die jedem möglich gelesenen Wert (hier 0,1) einen neuen Wert (0,1), eine Bewegung (L,0,R) und einen Neuen Zustand (1,Ende) zuweist. Von dieser Funktion gibt es genau (2*3*2)^2=144. Bei 2 Zuständen wären es schon (2*3*3)^4=104976. Allgemein berechnet sich die Anzahl: (|Alphabet|*|{L,0,R}|*(|Zustände|+1))^(|Alphabet|*Zustände). Bei 7 sind es dann schon 344.649.238.497.994.142.121.984 --84.176.202.17 15:08, 21. Mai 2009 (CEST)Beantworten

Das sehe ich anders. Sei M = (Z, {0,1,#}, delta, z_a, z_e) unsere Turingmaschine. Ich habe mal wohlwollenderweise das Leerzeichen in das Alphabet aufgenommen. Dann ist delta eine Untermenge von Z x {0;1;#} x Z x {0;1;#} x {0;1;-1}. Soweit steht das in jedem Buch zur Einführung in die theoretische Informatik. Damit kann delta aber höchstens 3^3*|Z|^2 sein. Weitere außerdem könnte man noch Start- und Endzustand jeweils verschieden wählen, da gibt es |Z| * (|Z|-1) Möglichkeiten (wobei man das eigentlich auch weglassen kann). Insgesamt ist die Anzahl der Turingmaschinen in Abhängigkeit von der Anzahl der Zustände (3*|Z|)^3*(|Z|-1), und selbst bei 10 Zuständen bin ich da erst bei 243000 verschiedenen Turingmaschinen. Die Anzahl der Turingmaschinen müsste also mal dringend überarbeitet werden!

Außerdem wüsste ich gerne mal, wie eine Turingmaschine mit einem Zustand aussehen kann. Da sind Start- und Endzustand der selbe, und sie wird nie einen Befehl ausführen. (nicht signierter Beitrag von 188.192.101.6 (Diskussion | Beiträge) 22:20, 3. Feb. 2010 (CET)) Beantworten

Im Kontext des Themas "Busy Beaver" ist durch Rado zunächst mal ein ganz bestimmtes Modell für Turingmaschinen vorgegeben: 2 Symbole {0,1}, Bewegung nur {L,R}, n Zustände plus ein anonymer (nicht mitgezählter) Halte-Zustand, beidseitig unbeschränktes Band, pro Übergang sowohl neues Symbol als auch Bewegung (sog. 5-Tupel Modell). Du kannst zwar ohne Probleme auch für andere Definitionen von "Turingmaschine" eine

\Sigma

-Funktion definieren, und tabellieren wieviele TM es für n Zustände gibt, aber es kommen andere Werte raus, weil es auf einer anderen Definition basiert. Ihr habt offenbar beide ein (unterschiedlich) abweichendes Modell verwendet.
– H.Marxen 22:30, 26. Aug. 2010 (CEST)Beantworten

Also nochmals von vorn: Die Anzahl der Turingmaschinen soll

Anzahl der Buchstaben des Alphabets ({0,1}): 2
Bewegungen ({L,0,R}): 3
Anzahl der Zustände: z

$(2\cdot 3\cdot (z+1))^{2\cdot z}$ sein?

Ich dachte eine Turingmaschine ist ein 7-Tupel $M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\square ,F)$ . Diese 7-Tupel müssen folgende Eigenschaften haben:

$|Q|=z$
$\Sigma$ Das Eingabealphabet verstehe ich als eine Art "Benutzereingabe". Da muss zwar jede Eingabe endlich sein, aber die Menge der Möglichen Eingaben ist deshalb dennoch unendlich, oder? Ähnlich wie jede einzelne natürliche Zahl endlich ist, aber die Menge der natürlichen Zahlen unendlich viele Elemente hat.
$F\subseteq Q$ Da alle möglichen Teilmengen gebildet werden können, gibt es hier doch $\sum _{i=0}^{z}{\binom {z}{i}}$ Möglichkeiten, oder?
$\delta :(Q\setminus F)\times \Gamma \rightarrow Q\times \Gamma \times \{L,0,R\}$ : Die Überführungsfunktion habe ich als "Programmiersprache" der Turingmaschine verstanden. Die Anzahl der möglichen Überführungsfunktionen ist meiner Meinung nach $z\cdot z\cdot 3\cdot 2\cdot 2=24\cdot z^{2}$ . Dabei steht das erste z für den aktuellen Zustand, das zweite für den Zustand nach dem schreiben. Die 3 steht für die Bewegungsrichtung, die 2 für die Symbole die geschrieben werden können und die zweite 2 für das gelesene Symbol.
$q_{0}\in Qrightarrow$ z Möglichkeiten
$\square \in \Gamma \setminus \Sigma$ 1 Möglichkeit.

Allein weil $\Sigma$ unendlich Möglichkeiten hat, müsste es doch schon unendlich 7-Tupel geben, oder? Wenn man diesen Punkt mal außer acht lässt (indem man z.B. sagt, dass immer "0" eingegeben wird), müsste es doch für Turingmaschinen mit z Zuständen $\sum _{i=0}^{z}{\binom {z}{i}}\cdot 24\cdot z^{2}\cdot z$ mögliche Turingmaschinen geben.

Könnte mir das bitte jemand erklären? --MartinThoma 19:05, 27. Aug. 2010 (CEST)Beantworten

Man beginnt immer mit einem leeren "Band"

\Sigma

. Bei dieser Konstellation gibts keine Benutzereingabe, sonst gäbe es, wie du richtig sagst, unendlich viele Möglichkeiten. --TheMightyPirate 09:24, 28. Aug. 2010 (CEST)Beantworten

Ich versuche es nochmal: Wenn wir über "Busy Beaver" reden, macht es wenig Sinn, die Definition der Turingmaschine aus einem Lehrbuch zu nehmen, das mit der Definition von "Busy Beaver" nichts zu tun hat. Es gibt nämlich ziemlich viele verschiedene "Definitionen" von "Turingmaschine". Tibor Rado hat sich eine gewählt, die ihm in den Kram gepasst hat, und wir sollten uns daran halten, solange wir von "Busy Beaver" reden.

Bei Tibor Rado gibt es N Zustände plus einen Haltezustand, zwei Symbole 0/1, zwei Bewegungen L/R, und eine Transition tut stets beides: neues Symbol und Bewegung. Dabei komme ich auf 2N Quellen für eine Transition (2 Symbole, N Zustände), und auf 4(N+1) mögliche Werte für eine Transition (2 Symbole, 2 Richtungen, N+1 Zustaende: 2*2*(N+1)). Das ergibt insgesamt (4N+4)^(2N) Turingmaschinen. Für N=1 sind das 8^2 = 64. So findet sich das auch in der Literatur zum Thema Busy Beaver, siehe z.B.:

Nach meinem Verständnis müssen also die Zahlen im Artikel geändert werden. Man sollte sie dort aber auch kurz erklären.
– H.Marxen 02:13, 30. Aug. 2010 (CEST)Beantworten