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

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)

Nein, die Literatur ist sich nicht einig. Es gibt die Unterschiede, die der Vorposter angegeben hat. Das macht aber nichts, da das keine Auswirkungen auf die Berechenbarkeit hat, sondern nur auf die Werte. --Xycolon 15:34, 18. Jun. 2011 (CEST)

Anzahl an Turingmaschinen

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

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)

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

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)

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)

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)

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.:

• http://www.drb.insel.de/~heiner/BB/mabu90.html Kapitel 2
• http://grail.cba.csuohio.edu/~somos/busy.html am Ende
• http://www.logique.jussieu.fr/~michel/tmi.html#par2

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)

Habe ich jetzt in diesem Sinne geändert.
– H.Marxen 01:18, 27. Sep. 2010 (CEST)

Habe im Artikel die Anmerkung hinzugefügt, dass es bei einem Fleißigen Biber als Bewegung nur "nach rechts" oder "nach links" (und kein "bleib stehen") gibt. Das schien auch aus dieser Diskussion nicht immer so deutlich hervorzugehen. --Apraphul (Diskussion) 17:02, 25. Dez. 2012 (CET)

Habe die Anmerkung, nachdem sie ohne Begründung entfernt wurde, wieder eingefügt. Der Biber-Vollprofi weiß das, doch dem Laien/Erstleser erschließt sich nicht automatisch, dass ein Fleißiger Biber niemals auf einem Feld stehen bleibt, bevor er nicht den Zustand "Halt" erreicht. Letztlich wären ja durchaus Biber möglich, die das können, aber das wären nicht die Fleißigen Biber, um deren Betrachtung und Berechnung es hier geht. --Apraphul (Diskussion) 08:05, 3. Sep. 2014 (CEST)

Als ich den Artikel gelesen habe, hat mich dieser Absatz einfach nur verwirrt: Was will er mir sagen? Da hätte auch stehen können "Der Himmer ist blau". Aus den Kommentaren hier habe ich dann geschlossen, dass die Anmerkung erklären will, warum die Formel 2*2*... und nicht 2*3*... lautet (nur zwei Bewegungsrichtungen, links/rechts und nicht drei, links/stehenbleiben/rechts). Aus der Anmerkung selbst lässt sich das nicht erkennen. Ich habe also die Berechnungsgrundlagen direkt vor der Formel eingefügt und dann den sinnfreien Absatz entfernt. Wenn jemand den Busy Beaver genauer beschreiben möchte, gehört das in den Abschnitt Definition und nicht in eine Anmerkung zu einer Formel. --85.212.66.147 17:21, 3. Sep. 2014 (CEST)

Da hast Du nicht ganz Unrecht. Und ja, die Anmerkung sollte verdeutlichen, dass bei der Berechnung von einem Biber ausgegangen wird, der genau zwei (und nicht drei) Bewegungsmöglichkeiten kennt. Das ist ja schließlich keine Selbstverständlichkeit (wie auch die Diskussion hierdrüber zeigt). Dass die Anmerkung dort jetzt nach Deinen Ergänzungen im vorherigen Satz etwas redundant in der Gegend herumsteht, und dass zudem die Information besser weiter vorne auftauchen sollte, sehe ich auch so.

Aber wie bringt man es unter? Ich schätze mal, dass alle Angaben, Berechnungen und Tabellen im Artikel einen Biber meinen, der zwei Bewegungen kennt. Das kann man sicher oben irgendwie reinschreiben.

Aber ist das für wirklich für alle Fleißigen Biber so?

a.) Falls ja, müsste man es so schreiben, dass eine Turingmaschine, die "Fleißiger Biber" genannt wird, die zwei Bewegungen kennt (links und rechts, aber nicht stehenbleiben). Kennt sie mehr oder weniger (recht sinnfrei, aber denkbar) darf sie nicht "Fleißiger Biber" heißen.

b.) Falls nein, so müsste man es so schreiben, dass hier im Artikel eben genau nur eine Art von mehreren möglichen Fleißigen Bibern besprochen wird; und zwar die Art, die bei der Bewegung nur links und rechts kennt.

Diese Überlegungen habe ich sowohl damals wie auch heute morgen, als ich die Anmerkung zurückschrieb, nicht zufriedenstellend beenden können. Vielleicht können wir es jetzt ...? Danke für Dein Feedback. VG --Apraphul (Diskussion) 18:28, 3. Sep. 2014 (CEST)

Update: Ich habe mich nochmal tiefer ins Thema eingelesen, mich für a.) entschieden und das eingebaut. (Siehe dazu ggf. auch Kapitel "Definition geändert" hier auf der Disk.) --Apraphul ^Disk 17:37, 5. Sep. 2014 (CEST)

Definition geändert

Habe jetzt das Intro und die Definiton entsprechend den Ausführungen des "Erfinders" von fleißigen Bibern, Tibor Radó, geändert. Belege dafür waren schon da. In meine Augen ist eindeutig, was Radó mit seinem Busy Beaver gemeint hat. Nur stand das bisher überhaupt nicht so im Artikel erklärt und hat vielleicht auch deshalb die Fragen und Zweifel in den Diskussionen hier auf der Disk bewirkt ....? Ich denke und hoffe, damit ist ein Anfang für eine Artikelverbesserung zum Zwecke des besseren Biber-Verständnisses beim Otto-Normal-Interessierten getan. VG --Apraphul (Diskussion) 12:26, 4. Sep. 2014 (CEST)

Sieht mir besser verständlich aus, Danke! Worüber ich noch stolpere, ist das „modifizierte“ gleich im ersten Satz. Das klingt so, als wären es eben keine echten TM. Wie wäre es mit „spezielle“? --H.Marxen (Diskussion) 17:59, 4. Sep. 2014 (CEST)

So wirklich gefällt mir das "modifizierte" auch nicht, obwohl es im Sinne von "veränderte Turingmaschine" durchaus zutrifft. Andererseits wäre eine Biber-Programmierung mit jeder Turingmaschine durchaus möglich - man muss halt z.B. nur den Stritt "Auf der Stelle verharren" nicht verwenden. Deswegen: Ja, hast Recht! "Spezielle" ist sehr viel besser! Ich ändere es. Danke :-) VG --Apraphul (Diskussion) 18:29, 4. Sep. 2014 (CEST)

Kapitel "Nicht lösbares Problem"

Dort steht: "So ist nicht generell entscheidbar, ob eine gegebene Turingmaschine mit n Zuständen tatsächlich eine Kette von Einsen maximaler Länge schreibt."
Damit ist dort eindeutig die Rede von zusammenhängenden Einsen. Das gehört so aber nicht zu den Vorgaben eines Fleißigen Bibers, denn ihn interessieren nur Einsen, egal ob und von wievielen Nullen sie unterbrochen sind. Das umzuformulieren ist sicher nicht schwer, doch stimmt dann die Aussage selbst und die anderen Aussagen in dem Absatz auch noch? Oder besitzt dann vielleicht eine der Aussagen keine Gültigkeit mehr, wenn wir nicht mehr von einer zusammenhängenden Einser-Kette sprechen? --Apraphul (Diskussion) 15:25, 5. Sep. 2014 (CEST)

An anderer Stelle (Ebenfalls nicht berechenbare Funktion) wird auf „Kette“ eingeschränkt, aber an dieser Stelle ist das wohl eine intuitive Formulierung gewesen. Habe es geändert. --H.Marxen (Diskussion) 16:09, 5. Sep. 2014 (CEST)

Kapitel "praktische Betrachtung"

Erster Absatz, letzter Satz: "Für n = 5 konnte inzwischen durch die Untersuchung bestimmter Eigenschaften zumindest bis auf 40 Maschinen, die kein reguläres Verhalten zeigen, eine Unterteilung in haltende Maschinen, die höchstens 4098 Einsen schreiben, und nicht haltende Maschinen unternommen werden." Den Satz verstehe ich wie folgt: Von allen möglichen "Maschinen" mit 5 Zustände sind 40 identifiziert worden, die "kein reguläres" Verhalten aufweisen. Alle anderen Maschinen konnten unterteilt werden in eine Gruppe, die nicht anhalten, und in eine andere Gruppe, die nicht mehr wie 4098 Einsen schreiben. Das bedeudet also (so wie ich das verstanden habe), dass höchstens noch 40 Maschinen den in 1989 von Buntrock und Marxen gefundenen Biber übertreffen können und falls sie das nicht tun, der fleißigste Biber mit 5 Zuständen also bereits gefunden wäre.
Folgende Fragen dazu:

• Ist das so, wie oben von mir geschlussfolgert?
• Wenn ich den Beleg dazu richtig angesehen habe, sind es dort 43 Maschinen (nicht 40). Korrekt?
• Das "kein reguläres Verhalten" verstehe ich nicht bzw. halte es eher für falsch. "Nicht regulär" klingt für mich nach "unerlaubt" bzw. "nicht den Regeln entsprechend". Und als relevante Regeln würde ich die sehen, nach denen ein Fleißiger Biber gesucht wird. Eine Maschine, die gegen die Regeln verstößt (weil sie unter falschen Voraussetzungen eingesetzt wird oder schlicht nicht den Regeln entsprechend programmiert ist), würde doch gar nicht betrachtet werden. Die englische Quelle spricht hier von "non-regular", was ich lieber mit "unregelmäßig" übersetzen würde. Ist also "unregelmäßig" hier der bessere Begriff gegenüber "nicht regulär"?
• Falls nein: Gegen welche Regeln verstoßen die 40 (oder 43) Maschinen? Falls ja: Welche Unregelmäßigkeiten treten bei den 40 (oder 43) Maschinen auf?
  

--Apraphul ^Disk 17:21, 5. Sep. 2014 (CEST)

Ich versuche mal meinen Senf dazuzugeben:

• Ja, das ist so, wie oben von dir geschlussfolgert.
• Ich meine mich zu erinnern, dass Skelet angefangen hatte, seine Ausreißer "manuell" zu analysieren, und ein paar wenige auf diese Weise eliminiert zu haben meinte. Allerdings finde ich seine Seiten schwer genau zu interpretieren, und konnte das nicht wirklich nachvollziehen.
• Das mit dem "regulär" verstehe ich eher im Sinne von "sonst üblich", und ein bißchen assoziiere ich auch „reguläre Sprachen“ (als einfache Sprachen) im Sinne von "einfache" Verhältnisse auf dem Band.
• Was bei denen anders ist, ist ja gerade unklar. Sie sind durch alle automatischen Filter gefallen (die reguläres Verhalten erkennen und entscheiden).

Die Quelle für diese Aussage (Skelet) ist leider nicht so hochwertig und glasklar, wie ein Artikel, der ein Peer Review erfahren hat. Wir haben aber z.Z. keine bessere Quelle. Hier ist noch massig Platz für fleißige Laien ;-)

--H.Marxen (Diskussion) 18:12, 5. Sep. 2014 (CEST)

Der Senf nach dem Senf ;-):

• Okay.
• Ich denke es sind 43. Die widerborstigen Maschinen tauchen samt dem Beleg im en-Wiki im April 2004 auf. Übrigens von Skelet (Georgi Georgiev) selbst. Dort ist im Artikel von "about 40 machines" (also "ungefähr 40" oder "rund 40") die Rede. Zu der Zeit gab es den Artikel im de-Wiki noch gar nicht. Die "40 Maschinen" im deutschen Artikel (erstmals im September 2005) scheinen eher eine schlampige Abschrift zu sein, denn hüben wie drüben wird derselbe Beleg angeführt. Und dieser Beleg wiederum spricht (mindestens) seit August 2003 von: "... in HNR remain only 43 machines !"
• Ja, das wäre eine mögliche Deutung, würde hier aber nicht passen. Denn im Umkehrschluss würde es bedeuten, dass es "üblich" (oder gar "einfach") wäre, für jede Turingmaschine bestimmen zu können, ob sie hält oder nicht. Dem ist aber ja nicht so.
• Naja, an den 43 Dingern ist dann halt anders, dass sie sich gegen den Versuch streuben, ihre Terminierung zu bestimmen oder zu widerlegen. Das ist aber weder "regelwidriges" noch "unübliches" Verhalten, oder?

Ich denke, ich werde den Satz umformulieren bzw. etwas ausschmücken und dann schlicht von "Ausnahmen" (welche eben (sinngemäß) durch Georgievs Prüfraster gefallen sind) sprechen. Dabei werde ich auch - falls keine Einwände kommen - auf 43 Maschinen erhöhen. Denn wie gesagt: Andere Belege haben wir nicht und der, den wir haben, ist eindeutig und auf ihn beruft sich anscheinend auch die ganze (Internet-)Welt.

--Apraphul ^Disk 17:15, 6. Sep. 2014 (CEST)

Nochmal wegen "regulär": doch, für TM mit nur 5 Zuständen ist es sehr wohl üblich (und oft einfach) zu bestimmen, ob sie hält oder nicht. Die meisten der rund 90 Millionen Kandidaten ist so einfach gestrickt, daß man sie automatisch erkennen kann.

Im übrigen stimme ich Dir zu.

--H.Marxen (Diskussion) 19:20, 6. Sep. 2014 (CEST)

Dazu (und weil ich gerade über etwas gestolpert bin) zwei Fragen:

Stehen die "90 Millionen Kandidaten" irgendwo belegt, so dass man da mal nachlesen könnte? Georgiev hatte nämlich 150 Millionen TMs durchrattern lassen [Zitat: "For class TM(5) the program enumerates about 150M machines"]. Kann es also sein, dass solcherlei Untersuchungen auch nach Georgievs (im Beleg dokumentierten) Versuch irgendwo nachvollziehbar fortgeführt wurden?

Falls nein und wir überhaupt nichts anderes haben, so macht mir seine Bemerkung etwas Angst, dass er sich selbst der Fehlerfreiheit seines Programms nicht sicher war [Zitat: "I hope that my program methods are correct mathemathical proves for finitnes/infinitnes of the Turing Machines, but there may be some fatal error, making my results incorrect."]. Sollte eine Enzyklopädie dann so etwas "wackeliges" überhaupt erwähnen?

--Apraphul ^Disk 11:54, 7. Sep. 2014 (CEST)

Die 90 Millionen stammen aus meinem Gedächtnis, und beziehen sich auf die Programmläufe, die ich mit J.Buntrock zusammen in 1989/1990 gemacht habe. In meinem Paper dazu (http://www.drb.insel.de/~heiner/BB/mabu90.html) steht „ca 88 million“. Erfahrungsgemäß ist die genaue Zahl stark anhängig von der exakten Natur der angewandten Heuristiken und Beweistechniken. 150 Millionen kommt mir etwas groß vor, ist aber nicht unplausibel.
Zur Fehlerfreiheit... kein Programmierer ist sich jemals sicher, daß ein nicht-triviales Programm gänzlich fehlerfrei ist. Selbst wenn ein Beweis dazu vorläge, hätte ich noch Zweifel an der Korrektheit des Beweisers, und an der Vollständigkeit der bewiesenen Hypothese.

Die mangelhafte Abdeckung mit Belegen ist für eine Enzyklopädie ein Problem, ja. Andererseits wird hier wohl kaum viel Schaden angerichtet, wenn mal was nicht stimmen sollte... ich erinnere mich vage, das Thema schon mal diskutiert zu haben, bin aber unsicher, wo/wann genau.

Da ich das noch nicht richtig ausgesprochen habe: ich finde das „klasse“, daß Du hier konkrete Dinge angehst, und bin gerne bereit, inhaltlich mitzuhelfen. Allerdings kann ich keine Antwortzeiten garantieren, und ab dem 12.9. bin ich für 3 Wochen nur selten online.
--H.Marxen (Diskussion) 18:38, 7. Sep. 2014 (CEST)

Meine Antwortzeiten sind auch nicht immer die besten. Kein Problem also. Ich freue mich übrigens auch sehr, dass Du Dich des Themas hier wieder annimmst. Danke dafür. :-)

90M vs. 150M:

Ja, auf Deinen Seiten hatte ich die 90M auch schon gesehen. Okay, dann stammen sie also aus Euren Zeiten, was meine vorherige Hoffnung dämpft, dass irgendjemand Georgievs Untersuchungen weitergeführt hat. Den Unterschied in der Anzahl der untersuchten Kandidaten sehe ich im unterschiedlichen Ansatz. Während Ihr seinerzeit primär auf der Jagd nach den meisten Einsen ward und dabei konsequent alle Kandidaten schon vorher aussortiert hattet, die augenscheinlich nicht würden siegen können, war Georgievs Augenmerk auf die Bestimmung der Terminierung gelegt, wobei er "nur" als Nebeneffekt dann auch die Einsen der terminierenden Biber ermittelt hat [Zitat aus seiner Arbeit: "As a side effect stoping machines are identified and checked for BB record."]. Dabei fällt z.B. auf, dass er - im Gegensatz zu Euch - auch Biber, die als ersten Schritt eine Null schreiben, durch sein Programm gescheucht hat und sie erst später, nachdem sein Programm sie als non-regular wieder ausgespuckt hatte, eliminierte. Ebenfalls fällt auf, dass seine 150M untersuchten Biber im ersten Schritt nicht alle konsequent immer auf denselben Folgezustand wechseln.

Georgiev hat also augenscheinlich andere Auswahlkriterien bevorzugt und so die Chance ausgelassen, den allerersten Schritt A0 immer fest mit der Aktion B1L zu belegen. Ihr dagegen hattet es so getan. Na wenigstens hat er wegen dieser Zustandsbezeichnungen keine isomorphen Biberchen mit durchgeschleppt, wenn ich die 164 non-regularen Tierchen richtig analysiert habe.

Fehlerfreiheit von Programmen:

Ja, das sehe ich auch so. Mir war nur die Tatsache, dass er es selbst so dermaßen deutlich erwähnt, etwas verwunderlich. Das, gepaart mit der Tatsache, dass seit 2003 scheinbar niemand (auch er selbst nicht) die Untersuchungen fortgetrieben hat, erlaubt Zweifel daran, ob er überhaupt auf dem richtigen Weg mit den richtigen Ergebnissen war.

Dazu kommt, dass der Beleg an einer Stelle fehlerhaft ist. Die Listen dort weisen 42 non-regulare Maschinen aus, nicht wie abschließend dort bemerkt 43. Aber den Satz deswegen ganz aus dem Artikel schmeißen, mag ich auch nicht.

Ich werde daher aus den "40" im Artikel ein "knapp über 40" machen und das alles etwas umformulieren. Kannst Dir ja mal ansehen ...

VG --Apraphul ^Disk 17:25, 9. Sep. 2014 (CEST)

Sieht gut aus. Danke. --H.Marxen (Diskussion) 21:52, 9. Sep. 2014 (CEST)

Asymtoptisches Wachstum der Σ-Funktion

Ich habe in den Artikel eingefügt:

„Man zeigt außerdem leicht, dass ihr asymptotisches Wachstum stärker ist als das jeder berechenbaren Funktion: Gäbe es eine solche berechenbare Funktion, so könnte man sie als Abbruchkriterium verwenden um das Halteorakel zu definieren.“

Das sollte ein Tipp für den Beweis sein. Denn ganz offensichtlich ist die Aussage nicht. Etwas ausführlicher ist der Beweis wie folgt:

Angenommen es gibt eine turing-berechenbare Funktion $f$, die $\Sigma$ majorisiert, also $\exists N\in \mathbb {N} \;\forall n\geq N:f(n)\geq \Sigma (n)$, dann konstruiert man das Halteorakel für die Turingmaschinen, die die „speziellen Regeln“ erfüllen, wie folgt:

Gegeben eine TM die „speziellen Regeln“ erfüllt, mit $n$ Zuständen.

• Setze $n'=\max(n,N)$.
• Simuliere die gegebene TM für bis zu $f(n')+1$ Schritte; falls sie bis dahin nicht abbricht, terminiert sie gewiss nicht.

$N$ ist von der TM unabhängig und wird ins Orakel fest eingebaut. Dann gilt $\Sigma (n')\leq f(n')$. Zur Gewissheit: Nach der Definition von $\Sigma$ terminieren alle haltenden TM mit $n$ Zuständen nach spätestens $\Sigma (n)\leq \Sigma (n')\leq f(n')$ Schritten.

Man müsste noch zeigen, dass das spezielle Halteproblem trotzdem unentscheidbar bleibt, wenn es keine Zustandsübergänge mit Verweilen gibt. Aber die lassen sich generell simulieren, indem man jeden Übergang $\delta (p,a)=(q,b,0)$ ersetzt durch $\delta (p,a)=(q_{0},b,L)$ und $\delta (q_{0},b)=(q,b,R)$ (für alle Bandsymbole $b$) mit neuen Zuständen $q_{0}$ für jeden Zustand $q$.

Bei der Bearbeitung wollte ich anfangs mehr erwähnen, aber das schien mir zu detailliert. Also habe ich es auf das Wesentliche beschränkt. Man kann ja voraussetzen, dass der Leser weiß, dass das Halteproblem vor allem daran scheitert, dass man nicht weiß, wann man aufhören soll, die TM zu simulieren; und dass eine berechenbare Funktion dafür taugt, wenn sie Σ majorisiert, erscheint naheliegend.

Spezialist^(D) 16:32, 28. Jan. 2017 (CET)

Hi Spezialist, danke, dass Du Dich meldest. :-) Ich hatte das aus mehreren Gründen (die so halbwegs in der Zusammenfassungszeile angegeben waren) zurückgesetzt.

• Das "leicht" störte mich persönlich, weil es, so wie es da stand und klang, gegen WP:NPOV verstößt. Falls es nicht einfach nur (Deine) Autorenmeinung ist und zudem noch enzyklopädisch relevant ist, so sollte natürlich nicht vorausgesetzt werden, dass der Leser weiß wie es geht, sondern dann die Sache auch wirklich aufgezeigt werden. Und wenn es aufgezeigt wird, gehören Belege dazu.
• Vielleicht ist Dein größter Irrtum der, dass der Leser von all den Dingen eh weiß. Das stimmt einfach nicht. Sieh mich an: Ich verstehe von den ganzen mathematischen Formeln und Erklärungen zur theoretischen Informatik im Allgemeinen und zu Turing-Maschinen mitsamt dem Halteproblem im Besonderen so gut wie gar nichts. Aber ich kenne die Fleißigen Biber seit Anfang der 1980-er Jahre. Um sich für die kleinen Biester und für den entsprechenden Wiki-Artikel zu interessieren, sollte es kein Mathematik-/Informatikstudium brauchen. Und genau da liegt die Pflicht der "Wissenden"/Hochstudierten: Den Artikel verständlich und lesbar für die Otto-Normal-Interessierten zu gestalten und zu halten.
• Da komme ich zum von Dir angesprochenen Halteorakel. Das habe ich zu ersten mal gehört. In über 30 Jahren Beschäftigung mit und Interesse an den Fleißigen Bibern habe ich (als Laie wohlgemerkt) dafür nie das Halteorakel gebraucht oder davon lesen müssen. Ist das also wirklich ein Mehrwert für den umseitigen Artikel? Ich könnte es weder bestreiten, noch bestätigen. Ich zweifel es lediglich an. Ich kann dafür aber mit aller Deutlichkeit sagen, dass der Satz im Artikel "Man kann außerdem zeigen, dass ihr asymptotisches Wachstum stärker ist als das jeder berechenbaren Funktion" für mich völlig nichtssagend ist. Deine Erklärung oben leider ebenso. Was hilft mir der Satz, wenn ich etwas über Fleißige Biber erfahren möchte? Möglicherweise hast Du genau das auch gedacht und hast es deshalb ergänzen wollen, aber Deine Einfügung hat den Satz (für mich) auch in kein helleres Licht gerückt. :-)

Ich glaube, dass es sehr schwer ist, bei solch komplexen Themen den Artikel-Spagat zwischen möglichst vollständiger Beschreibung (mit allen möglichen Formeln dieser Welt ;-)) und einer nur-so-viel-wie-nötig-Beschreibung (mit der Otto-Normal-Verbraucher auch noch halbwegs am Ball bleiben kann) hinzubekommen. Bei der "Mutter" Turingmaschine tendiere ich sogar zum ersten; bei der davon abgeleiteten Spielerei mit den Feißigen Bibern denke ich aber wirklich, dass weniger mehr ist. VG --Apraphul ^Disk _WP:SNZ 18:28, 28. Jan. 2017 (CET)

Tja, du hast recht. Der Beweis ist im Übrigen so falsch. Ich habe die Anzahl der Einsen mit der Anzahl der Schritte, die die TM macht, verwechselt. Wegen der Abschätzung und den Ausführungen weiter unten im Artikel erübrigt sich ein Beweis eigentlich vollkommen. Spezialist^(D) 16:32, 29. Jan. 2017 (CET)

Praktische Betrachtung: Tabelle veraltet

Eine aktualisierte Tabelle habe ich in Spektrum der Wissenschaft 9/2017 gefunden. So das plausibel ist, bitte ich einen Spezialisten, sie einzubauen, da ich kein sehr geübter Gelegenheitswikipedianer bin und meine letzte mathematische Vorlesung Jahrzehnte her ist.
Leider steht mir nur die gedruckte Ausgabe zur Verfügung, wenn jemand Spektrum-Digital-Abonnent ist, kann er das im Netz online nachvolziehen. Änderungen sind fett. Die 5-fache Exponentiation am Ende ist ernstgemeint und entspricht dem Gedruckten.

Zustände $n$	Turingmaschinen	$\Sigma (n)$	Quelle
1	64	1	(1962; Rado)
2	20736	6	k.A.
3	16777216	21	(1965; Lin, Rado)
4	2,56×1010	197	(1975; Brady)
5	≈ 6,34×1013	≥ 240	(1983; Jochen Ludewig)
		≥ 501	(1983; Uwe Schult)
		≥ 1915	(1984; George Uhing)
		≥ 47.176.870	(1990; Jürgen Buntrock und Heiner Marxen)
6	≈ 2,32×1017	≥ 7,4 * 1036.534	(2000; Pavel Kropitz)
7	≈ 1,18×1021	> 10101010107	Wynthagoras, 2014

Warum in S.d.W. für 1 und 2 (1 muss ja definitiv von Rado als "Erfinder" sein) kein Name angegeben ist, ist unklar, ebenso die Jahreszahl 2000 bei Kropitz, die könnte evtl. ein Druckfehler sein (oder aber der alte Wert 2010 hier - ein unentscheidbares Problem!!?). Autor des Artikels ist der über alle Zweifel erhabene Jean-Paul Delahaye: Bedrohliche Unentscheidbarkeit, pp.72-79. --84.176.130.164 19:46, 28. Nov. 2017 (CET) ...und bitte die Literaurangabe als Fussnote dazusetzen. Danke. --84.176.130.164 19:50, 28. Nov. 2017 (CET)

Hi 84.176.., sorry, aber die Tabelle ist Unfug. Wie auch immer SdW auf die Idee kommt, sowas abzubilden ... Bist Du sicher, dass Du sie hier korrekt wiedergegeben hast? $\Sigma (n)$ gibt die Anzahl von Einsen an, die ein Biber erzeugt; und da sind die neuen Zahlen zumindest bis einschl. Marxen/Buntrock Quatsch. Gruß --Apraphul ^Disk _WP:SNZ 21:05, 28. Nov. 2017 (CET)

Erklärung: Die Biberchen, die in der Ausgabe der SdW besprochen werden, sollen dort nicht möglichst viele Einsen schreiben, sondern möglichst viele Schritte vor dem Anhalten machen (Quelle). Also ist $\Sigma (n)$ dort nicht die Anzahl von Einsen, sondern vermutlich die Anzahl von Schritten. Das hat mit unserem Artikel, wo der klassische Fleißige Biber - der mit den meisten Einsen - beschrieben wird, nichts zu tun. Gruß --Apraphul ^Disk _WP:SNZ 21:34, 28. Nov. 2017 (CET)