Irgendwie amüsiert mich die Vorstellung, dass alle Mathematiker dieser Welt sich nur noch auf BB stürzen und damit nebenbei diese ganzen Dinge beweisen würden.
Bringt nur nichts, letztendlich sind das auch nur Turing-Programme mit Komogorov-Komplexität und Halteproblem und damit allgemein unlösbar, also nur weil man einen Beweis als Computerprogramm schreiben kann macht es ihn nicht einfacher.
BB ist bei kleinen Zahlen ganz lustig. Aber es macht Sinn, warum bei großen Zahlen auf einmal alle diese Probleme inkludiert sind, was DorFuchs gesagt hat - je mehr Zustände, desto mehr Möglichkeiten gibt es, und auf einmal sind mehr und mehr Computerprogramme inkludiert, die das Problem codieren können. Nehme eine ausreichend große Zahl von Zuständen, und es ist auf einmal die ganze Codebase von Microsoft Word drin. Oder jegliche andere Möglichkeiten, die Code so anstellen kann. Also es macht Sinn, warum BB irgendwann von Beweisen von ein paar übersichtlichen Zuständen übergeht zu: Man beweist die anderen Sachen alle mit. Es ist einfach die Definition von BB. BB sagt: Eigenschaft X von allen Maschinen mit Y Zuständen. Damit wird es nicht einfacher die spezifische Maschine mit Y Zuständen zu lösen, sondern sie ist einfach dabei, und muss vorher gelöst werden. Damit ist BB schwerer als alle inkludierten Probleme. Es ist keine andere Form oder bietet eine andere Sichtweise auf das Problem. Es ist nur als Über-Container definiert, der erst beantwortet werden kann, sobald alle enthaltenen Maschinen gelöst sind. Es ist aber eine sehr geschickt definierte Zahl, das muss ich sagen. Stark, was man definieren kann, wenn man eine Funktion möchte, die möglichst stark ansteigt. Und scheinbar auch in Komplexität und Schwierigkeit stark ansteigt, dadurch, dass sie so definiert wurde, dass sie so viele anderen Komplexitäten inkludiert. Ebenfalls ist es stark, wie einfach die Definition gleichzeitig ist, und dass sie von jedem in einer kurzen Zeit verstanden werden kann.
@@IroAppe Erinnerung daran, dass MS Word nicht auf einer Turing Maschine laufen kann, da eine Turing Maschine kein Dateisystem, Bildschirm, Druckfähigkeiten, Internet oder Tastatur/Maus hat.
Also ich habe auch einen Bachelor in Mathematik gemacht, aber der Typ mit der 745-er Maschine hat darüber seine Bachelor-Arbeit gemacht? WTF, also ich bin bei dem Video ausgestiegen 😅
Das alles ist wirklich sehr intressant, vorallem die theoretische Informatik dahinter fasziniert mich sehr. Ich weiß ja nicht wie viel Fachwissen du in der Informatik hast, aber ein Video über weitere Themen der theoretischen Informatik, die sich sehr mit der Mathematik auseinandersetzen, wäre wirklich cool. Auch zu Bereichen wie der Mathematischen Logik, würde ich mir mal sehr gerne ein Video wünschen. Wennn es sich mal ergibt bzw. du die Zeit hast, soetwas zu machen. Dennoch mag ich all deine Videos und finde, dass du langweilige oder sehr trockene Themen, spannend und Interessant rüber bringst und sie sehr gut veranschaulichst. Weiterso, Dorfuchs!
Thank you very much for this great video! May I just add that at 0:11, the correct crediting for the BB(5) result is (bbchallenge, 2024) and not (Stérin, 2024). Indeed, while I created bbchallenge, the final result is the product of a collaboration involving 15+ people (listed in the credit section of the announcement post that you used in the video). Thank you!
I was thinking of just writing (2024) because I was not sure, how to put it. Maybe "Stérin et al" would be the classical way to indicate a group effort, but I really like using just the name of the project. Thank you for starting the project and bringing so many people together!
Ich liebe diese Art von Problemen, die zu verstehen auch ohne mathematisches Spezialwissen möglich sind, die aber zu beweisen verdammt schwierig oder sogar unmöglich sind. Die Collatz-Vermutung z.B. kann ich natürlich auch nicht beweisen, ich konnte zumindest aber meine Programmierskills dabei verbesserm, um effizient einen Zahlenraum eins bis 2 hoch n zu überprüfen.
Ich bin so glücklich das ich das video heute erst gefunden habe, ich hab vorgestern eine klausur in theoretischer Informatik geschrieben und hab alles verstanden wovon im Video geredet wurde. Bevor ich vor 2 Wochen angefangen habe zu lernen hätte ich dumm den Bildschirm angestarrt
Auf das Format hätt ich richtig Bock bitte regelmäßig.
3 месяца назад+12
Sehr schönes Video! Ich persönlich hätte es noch cool gefunden, den neu gefundenen fünften fleißigen Bieber in der schönen farbigen Darstellung zu zeigen. Auch wenn niemand 47 Mio. Schritte mit Stift und Papier durchgehen will, wäre es einfach mal interessant zu sehen, wie die fünf Zustände untereinander verknüpft sind. Und Leute, die es interessiert, hätten trotzdem mal anfangen können das auszuprobieren, nur um ein Gefühl dafür zu bekommen, wie dieser ausgeklügelte fleißige Bieber sich so verhält und warum sein Verhalten schwer zu verstehen ist. (Tipp für alle die das lesen: Auf der englischen Wikipediaseite über Busy Beaver stehen die 5 Zustände für den fünften Busy Beaver). Noch eine Info: Normalerweise wird eher nach der Anzahl der maximalen Einsen gesucht als nach den maximalen Schritten. In dem Sinne ist BB(5)=4098. Mich würde mal interessieren, ob es auch passieren kann, daß man zwei verschiedene Busy Beaver braucht, um diese beiden Zahlen zu maximieren.
Stimmt. Den 5. fleißigen Biber hätte ich ruhig auch zeigen können. Und ja, oft sind mir S und Sigma als die maximale Anzahl der Schritte und der 1en begegnet. Und ich weiß auch nicht, ob es immer einen fleißigen Biber geben muss, der in beiden Kategorien das Maximum erreicht. Für die bekannten 5 Beispiele ist das wohl der Fall.
wollte gerade kommentieren "mach mehr solche Videos" aber dann habe ich mir mal deinen Channel durchgesehen und gemerkt, dass du das schon ne ganze Weile machst 😄 kannte dich nur von früher aus dem Mathesongs, die unser Lehrer uns vorgespielt hat. Schöne Entwicklung des Channels 😊
Das krasseste ist, dass mein Freund die geschreiben hat! Ich weiß noch, wie wir im Europapark darüber gefachsimpelt haben; unsere Freunde waren nicht so begeistert XD
Großartiges Video! Danke dafür. Busy Beaver und Riemann‘sche Vermutung. Darüber muss ich noch ein wenig nachdenken. Aber großer Respekt an Johannes Riebel für den Zusammenhang von BB(748) und Gödel‘s Unvollständigkeitssatz. Das sollte doch nicht nur für eine Masterarbeit reichen, oder?
Der Typ muss ein Gehirn von der Größe wie Chuck Norris' Eier haben wenn er so ne Bachelorarbeit geschrieben hat.... oder er hatte schon Forschungserfahrung und hat sich ordentlich Zeit genommen.
Was hierbei etwas untergeht ist die umgekehrte Richtung: Wenn ich BB(n) kenne, kann ich jedes Problem, dass sich mit n Zuständen darstellen lässt, leicht lösen, indem ich einfach die entsprechende Maschine mit n Zuständen laufen lasse und schaue, ob sie nach BB(n) schritten noch am laufen ist. Somit können wir nun da wir BB(5) kennen, jedes problem das sich mit 5 Zuständen lösen lässt, in relative schneller Zeit lösen.
Das ist natuerlich nur interessant fuer BB(5), da die untere Schranke fuer BB(6) schon so gross ist, das wir keine Maschine fuer so viele Schritte laufen lassen koennen.
@@hypnogri5457 Ah, aber es verrät uns auch, ob ein bestimmtes Problem berechenbar ist oder nicht, je nach dem ob die Maschine dafür anhält oder nicht. Und das ist ja schonmal ein Anfang.
@@Leon-eq6ei Und das Wechseln ist völlig grundlos. Wenn Zimmer vorhanden sind , in die vorhandene Gäste wechseln können , dann können die neu ankommenden auch direkt dort hin gehen. Die anderen können bleiben wo sie sind .
Das ist ja auch eine Funktion ohne Parameter, also konstante Funktion. Dass sie berechenbar ist, ist ziemlich offensichtlich, aber auch eine Folgerung aus folgendem Satz, mit dem man immer gut junge Studenten verwirren kann, die noch nicht ganz verstehen, was Berechenbarkeit bedeutet: Jede Funktion mit endlichem Definitionsbereich ist berechenbar.
@@joshix833 Man kann es als Funktion von der leeren Menge auf {0,1} betrachten. Es existiert eine eindeutige solche Funktion, die nichts irgendwie abbildet. Weil das wenig sinnvoll und die stückweise Definition so überflüssig ist, kann man stattdessen eine beliebige einelementige Menge als Definitionsbereich wählen. Die Uneindeutigkeit, welche dieser beiden Interpretationen die richtige ist, liegt an der unpräzise Weise, wie die Funktion definiert wurde. Zum Glück sind aber sowohl 0 als auch 1 endlich Zahlen, womit der Satz in beiden Fällen anwendbar ist.
Busy Biber und Collatz ist eine interessante Kombi. Collatz kann man mit Schulkentnissen lösen. Den Grund warum jede (natürliche) Zahl beim Collatzproblem bei Eins landet ist eine Struckturverschiebung. Vereinfacht gesagt wird aus einer 9 eine 5 und das sorgt dafür, daß die ganze Stuktur kollabiert. Die 5 sorgt dafür, daß mehr Stellen abgebaut werden, als je durch die Multiplikation mit 3 aufgebaut werden können. Ich hab noch vieles mehr rausgefunden, so kann man tatsächlich nur aus der Strukur der Zahl berechnen, wieviel Schritte diese braucht, bis zur Eins. Es gibt bei Collatz unendlich viele Zahlen, die die Funktion der Eins übernehmen. Diese Zahlen sind 1, 5, 21, 85, 341, 1365 usw. Lustig ist auch die Formel mit der man sofort den Wert der Struktur nach dem ersten Fall berechnen kann: (3^s * n + 3^s- 2^s) / 2^(s+1) Das s kann man aus der Struktur der Zahl sofort ablesen. Die 7 hat z.B. den s-Wert 3. Die Zahlen, die die 2 übernehmen hab ich auch schon identifiziert, kann sie aber mathematisch noch nicht darstellen. Auch die 3 ist schon in arbeit. Soll heißen, man kann aus allen Zahlen sofort berechnen, wieviel Schritte es bis zur eins sind.
3 месяца назад+1
Du solltest eine Mail an Prof. Weitz schreiben, der freut sich!
Als jemand der in 3 wochen seine theoretische Informatik klausur schreibt kann ich nur sagen wie cool das Thema ist aber wie absolut bodenlos schwer das ist, ist beinahe schon kriminell 😢
0:08 Die Zahl kam mir bekannt vor und somit hab ich gerade eine meiner eingereichten Lösungen zu Übungsblättern zu Berechenbarkeit und Komplexität aus dem Jahr 2012 herausgekramt (ist ein PDF).. und siehe da, "[...] Also terminiert M_5 auf die leere Eingabe nach 47176870 Schritten und hat 4098 Einsen auf das Band geschrieben" Neu ist also nur der Beweis zur Minimalität. Aber ich schau trotzdem mal das Video an.. :D Edit: Sehr coole Zusatzinfos, hat sich gelohnt!
Glaube hat er erwaehnt. Weil jede berechenbare Funktion ein (zb Python) Programm hat welches sie berechnet. Dies bedeutet, dass es eine Turing Maschine fuer dieses Programm gibt. (und diese TM hat eine bestimmte Art von Zustaenden, sagen wir n Zustaende, sodass B(n+1) die berechenbare Funktion eingeholt hat. Und das funktioniert fuer jede berechenbare Funktion)
Wenn man die Aussage am Ende mal so richtig durchdenkt, wird es richtig wild: Angenommen ich könnte wissen, welche Maschine mit 745 Zuständen nicht entscheidbar ist. Dann führt das zu 'nem Widerspruch, da wenn diese Maschine ja terminieren würde, ich das durch einfaches Durchrechnen beweisen kann, weshalb sie nicht terminieren kann, wodurch ich aber wüsste, dass sie nicht terminiert. Daher kann man niemals wissen, welche Maschinen nicht entscheidbar sind. Weil die Menge aller Maschinen mit 745 Zuständen aber endlich ist, führt das zu Folgendem. Angenommen ich hätte für alle Maschinen, die entscheidbar sind, einen Beweis. Dann bliebe nur noch die Menge der Maschinen, für die ich keinen solchen Beweis finden kann und wenn ich wüsste, dass es keine Beweise mehr gibt, lande ich wieder bei obigem Widerspruch. Das ist für sich genommen nicht spektakulär, weil man in der Realität eh nur endlich viele Beweise haben kann und sich daher eh nie gewiss sein kann, aber es zeigt insbesondere, dass es keine Menge aller möglichen Beweise für die Maschinen mit 745 Zuständen geben kann, sie wäre also schlicht zu groß. Man kann also sehen, dass bereits für die Eigenschaften einer festen endlichen Zahl von Objekten die Klasse aller möglichen Beweise keine Menge mehr zu sein braucht. Ist man nun reduktionistisch unterwegs, das heißt, denkt man, dass Menschen nichts mehr als ein hochkomplexer Roboter sind und KI uns vollständig ersetzen kann, hieße das, dass wir Menschen vollständig korrekte Beweise aufschreiben könnten, die wir nicht verstehen (denke ich zumindest). Andernfalls könnte es bedeuten, dass es eine menschliche Intuition oder metaphysische Sache geben muss, die sich nicht auf das mechanische/physische zurückführen lässt. Freilich ist diese Fragestellung für uns vermutlich wieder unentscheidbar. Wobei auch noch angemerkt sei, dass dieser letzte Absatz voraussetzt, dass ZFC mit unserer Kognition d'accord geht.
Das ging mir auch durch den Kopf! Das heißt auch, dass es mindestens zwei Maschinen geben muss, die nicht entscheidbar sind. Denn, wenn man es für alle außer einer Maschine zeigen kann, weißt du, dass die letzte nicht hält. Dann weißt du aber aus diesem Grund, dass diese zwei Maschinen nicht entscheidbar sind usw. Das wirkt paradox (ich sage bewusst nicht widersprüchlich)
nunja, die betroffene Turingmaschine wird doch explizit konstruiert 😅 sie kann alle formulierbaren Beweise durchgehen und bleibt stehen, wenn zwei widersprüchliche Aussagen bewiesen wurden. Wenn die Maschine hält ist ZFC nicht widerspruchsfrei. Wenn sie nicht hält, kann das aber nicht bewiesen werden. Nur in diesem Sinne ist es nicht entscheidbar.
@@espeed10 Warum sollte es zwei unentscheidbare Maschinen geben müssen. Wenn wir ein Ergebnis für alle außer einer Maschine gefunden haben, könnte es trotzdem sein, dass diese letzte Maschine nach irgendeiner gigantischen Anzahl an Schritten hält. (oder nicht, können wir ja vielleicht nicht wissen)
BB(744) erschlägt die Riemannsche Vermutung, und BB(745) ist unentscheidbar?! Wow. Dann wird die Riemannsche Vermutung wohl noch einige Jahrhunderte eine Vermutung bleiben.
Ich denke die Schlussfolgerung kann man so nicht machen. Jemand hat eine Turingmaschine mit 744 Zuständen gebaut, die die Riemannsche Vermutung per Brute Force prüft und anhält, falls ein Gegenbeispiel gefunden wird. Das sagt aber nichts darüber aus wie schwierig es ist einen Beweis oder Gegenbeweis für die Riemannsche Vermutung zu finden.
Das wirft für mich die Frage auf, ob es eine "flachere" Version der Busy-Beaver-Folge gibt, die die gleichen Zahlen durchläuft und auch monoton wächst, aber dazwischen noch viele Zwischenwerte erreicht, indem sie sich nach und nach verschiedene Arten von z.B. 5-State-Maschinen anschaut
Zu 14:00: Was ist mit der Rayo Zahl? Dem liegt doch auch eine Funktion zu Grunde und da der Busy Beaver mathematisch formulierbar ist, muss er langsamer wachsen als die Rayo Funktion.
Die Rayo Funktion ist nicht berechenbar (es gibt keinen Algorithmus der für jede Prädikatenlogische Aussage bestimmt ob sie wahr ist), also kann sie schneller als BB wachsen
Die BB-Zahlen bezeichnen ja die längstmögliche Laufzeit, aber geht damit auch unbedingt die größtmögliche Anzahl geschriebener Einsen einher? Ist es nicht möglich sozusagen unnötige Schritte so einzubauen, daß vielleicht die meisten Einsen sogar tatsächlich von einem Programm, das nicht so viele Schritte wie seiner Komponentenzahl entsprechend möglich wäre, macht, geschrieben werden?
Unfassbar gutes Video, Danke! Ich verstehe aber nicht; sind alle nicht berechenbaren Funktionen stärker als alle Berechenbaren? In der Verketteten Pfeilschreibweise ist cg(4)=4➡4➡4➡4 bereits größer als Grahams Zahl! Der Busy Beaver muss Chained Arrow Notation später überholen, aber wie kann man das wissen? EDIT: Ja bei 14:00 wirds gesagt aber ich schnalls nicht,😅
Ab etwa TimeCode 13:40 erwähnst Du ja den bewiesenen Satz, dass BB schneller wächst als jede "berechenbare" Funktion f:N -> N. Da würde mich interessieren, ob es sowas wie eine "schnellst wachsende berechenbare" Funktion gibt bzw. vielleicht sogar bekannt ist. Ich versuche die Frage mal formal zu stellen: Sei BF die Menge aller berechenbaren Funktionen f:N->N. Gibt es ein F in BF, so dass für alle anderen Elemente f in BF gilt: lim_{n ightaoorw \intfy} F(n)/f(n) = \infty ? BB selber ist ja nicht in BF enthalten, oder?
Wenn F(n) berechenbar ist, dann ist auch F(n)+1, F(n)^2, F(n)!, F(n)^F(n) usw. berechenbar. Deswegen kann es keine "schnellst wachsende berechenbare" Funktion geben.
@@DorFuchs Danke, das leuchtet gut ein. Dass BB(n) noch schneller wächst als alle "berechenbaren" Funktionen ist dadurch noch beeindruckender bzw. weniger intuitiv.
Busy Beaver fühlt sich ein bisschen so an wie das Halting Problem einfach durchzurechnen. "Okay, es gibt keinen allgeimeinen Algorithmus um zu prüfen ob eine Turing Maschine anhält, aber was wenn wir einfach alle durchgehen und schauen ob wir beweisen können, dass sie (nicht) hält?"
Jap, der BB ist absichtlich genau so konstruiert dass das halting Problem zum Problem der Aufgabe gemacht wird um dann sagen zu können, dass das BB Problem nicht berechenbar ist. Ist mehr ein Beispiel für ein einfach zu definierendes Problem was nicht lösbar ist als eine wichtige Mathematische Frage aber das ist ja bei vielen dieser wichtigen Dinge die keinen Beweis haben so :)
hm, also ich würde ja sagen quantencomputer lösen das problem, aber naja, das BB ist ja ein Problem wo ein zustand auf den nächsten folgt, und QTPCs sind ja nur gut darin gleichzeitig dinge ablaufen zu lassen, dass hilft dem Problem nicht unbedingt. Da muss man schon ne Zeitmaschine erfinden und einen Rechner so Millionen von Jahren rechnen lassen.
Klassische Computer können Quantencomputer simulieren, mit höchstens exponentiellem overhead. Für Berechenbarkeit bringen Quantencomputer also keinen Unterschied.
Ich weiß zwar nicht ob es eine "erlaubte" Funtkion ist - aber wenn ich f(n) = {3, ,3, ,3, 3, 3, ...} definiere (mit n∈ℕ), also z.B. f(4) = {3, 3, ,3, 3} (wobei das hier als BAN - also der "Bird Array Notation" - gemeicht ist), dann würde es mich doch sehr wundern wenn die BB(n) Funktion schneller wachesn soll als diese Funktion. Bereits {3, 3, ,3 ,3} ("Tetratri") ist so groß dass es schon eine Herausforderung ist zu verstehen wie dieser Wert überhaupt gebildet wird (geschweige denn wie groß er isr). Jedenfalls ist dieser Potenzturm für BB(6) kaum von Null zu unterscheiden im Vergleich zu Tetratri.
ich verstehe nicht, wieso BB schneller wachsen soll, als eine funktion in einer programmiersprache. man kann schließlich eine funktion bauen, die BB(n) bzw. BB(n)+1 für den parameter n berechnet. ist natürlich eine unglaublich langsame funktion, die für n=5 schon nicht mehr in unserer lebenszeit zum ende kommt, aber trotzdem existiert sie.
@@horstheinemann2132 warum sollte das was ich beschrieben habe nicht möglich sein. man kann BB schließlich programmieren (brute force) und es somit lösen.
3 месяца назад+4
@@multiarray2320 Nein, wie sähe Brute Force bei BB denn aus? Wie lang willst du eine Maschine laufen lassen bis du entscheidest, daß sie nicht hält, und sie deshalb ausschließen darfst? Eine Quindezilliarde Schritte? Und wenn sie nur einen mehr gebrauch hätte lägst du falsch.
ich dachte, dass ich einen weg gefunden hatte wie man bestimmen kann ob er sich in einer schleife befindet oder nicht. aber ich irre mich offensichtlich. nur um meinen weg einmal zu erklären. wenn man für jeden schritt das gesamte band und den aktuellen zustand speichert, dann könnte man doch hetausfinden, ob sich das programm in einer schleife befindet, falls die konstellation der 0 und 1 sowie der zustand schon einmal erreicht wurden. dabei darf man natürlich nur den abschnitt des bandes betrachten, der davor schon erreicht wurde und nicht das gesamte band.
3 месяца назад+4
@@multiarray2320 Das geht leider nicht allgemein, weil Schleifen auch unterschiedliche Muster pro Durchlauf erzeugen können. Es könnte z.B. eine Schleife geben, die nacheinander alle durch 5 teilbaren Zahlen in Binärcode aufs Band schreibt. Dann kommt bei jedem Schleifendurchlauf ein anderer Wert aufs Band. Oder eine Schleife die alle Primzahlen aufschreibt.
"Man kann zeigen dass [berechenbare Funktionen] am Ende alles Turing Maschinen auch leisten können." (14:04) Ist das so? Ich dachte das ist nur eine These die Turing und Church aufgestellt haben
Soll das bedeuten, dass wer BB(744) beweist oder widerlegt, der beweist oder widerlegt die RH ? Selbiges gilt dann auch für GV ? Wo findet man weiterführen Informationen über den Zusammen zwischen mathematischen Problemen und der BB ?
Ich hab mal mich ein bisschen darangesetzt. Ich habe eine Rechenvorschrift gefunden, wie man die n-te Busy Beaver Zahl berechnet. _Nur leider ist der Platz in einem RUclips Kommentar zu klein um den Beweis des Algorithmus zu erklären_ 🌚
@@nocktv6559 Wenn BB ab einem bestimmten n nicht wohldefiniert ist, dann kann man doch nicht sagen, BB wächst schneller als jede berechenbare Funktion.
@@tochoXK3 Keine uncountable Function ist wirklich wohldefiniert. Ist auch wirklich ein sehr umfassend großer Thema und nicht so kurz einfach zu erklären ohne sehr auszuschweifen. Du kannst es dir mit den verschiedenen "Größen" der Unendlichkeiten erklären. Die unzählbare Unendlichkeiten sind größer als Zählbare.
"Extrem schnell wächst" finde ich aber auch relativ zu dem mit was man es vergleicht. Wenn ich an eine extrem schnell wachsende Zahlenfolge denke wäre das eher TREE. Die ersten fünf Zahlen von BB kann man schon mal ausschreiben. Für die sechste kennt man zumindest eine obere Grenze die man noch als Potenzturm schreiben kann und noch nicht auf Pfeilschreibweise oder andere Notationen zurückgreifen muss um die Größenordnung auf Papier zu bringen. Das beindruckende bei BB(5) ist doch wie die Zahl bewiesen wurde und nicht das die Zahl 8 Ziffern lang ist.
Bei BB(6) hat man eine *untere* Schranke. Es könnte sein, dass BB(6) bereits TREE(3) übersteigt. Und da TREE berechenbar ist, gilt auf alle Fälle BB(n) > TREE(n), wenn n hinreichend groß ist (vielleicht schon bei n=50 oder so, aber das weiß man halt nicht).
Das eigentlich interessante zum Wachstum der BB Zahlenreihe ist das je größer die Zahl wird um so schwieriger wird es die Zahl zu beweisen. Ob die exakte Größe von BB(6) überhaupt irgendwann bestimmt und bewiesen werden kann ist fragwürdig.
Kann mir jemand erklären, was das in irgend einer Form für ein Use Case geben kann? Ist dieses Wissen einfach nur logisch und cool oder wirklich nützlich?
Stell dir vor Menschen hätten sich damals gewagt von anderen eingrenzen zu lassen, weil sie keine Use Cases sahen. Wir hätten keine Handys, Technologie, kein gar nichts. (und das ist eine Untertreibung) Wir sind hier nicht auf RUclips, weil Mathematiker damals sich Socialmedia vorgestellt haben. Aber rückblickend doch dankbar, dass sich diese Leute damit beschäftigt haben. Bin selbst kein Experte aber solche Probleme die wie im Video erwähnt zu historischen Problemen in Verbindung stehen würden einen gewaltigen Einfluss auf die Welt der Mathematik haben. Und nur Gott weiß wozu all dies beitragen wird, was im Endeffekt auch unser Leben beeinflussen könnte. Auf der anderen Seite reicht es aber auch einfach faszinierend zu sein.
Würde da statt Computer besser FPGAs nehmen, in die fetten Dinger mit irgendwas 10Mio LEs passen sicher locker 100'000 von den Dingern pro FPGA, vermutlich auch so ca. 100'000-1Mio mal effizienter als mit CPU durchprobieren.
@@headsetbozz5559 es geht nicht um absolute Größe. Es geht um die "Beschleunigung" TREE (0) =O TREE (1) = 1 TREE (2) = 3 TREE (3) = zweitgrößte jemals in einem Beweis angewandte Zahl Wenn es um fast growing hierachies geht, schlägt nichts die TREE Funktion
What if you wanted to flex with BB(5) but I challenge you with Tree(3) Und ich bin mir sicher dass wir Tree(3) nie genau rausfinden werden, es gibt im Universum nicht genug Atome und diese Zahl darzustellen
Ehm ich hab jetzt nicht ganz gerafft wie man nachweisen kann wann ein BB(n) genau dann hält, wenn eine mathematische Vermutung Eintritt 😂 Muss man dass nicht auch erstmal nachweisen mathematisch? Bzw woher weiß ich, welche Form die einzelnen Zustände von BB(n) haben?
BB überholt TREE spätestens bei n = 748. Tatsächlich ist Graham < Tree < BB < Rayo, also wächst Rayo am schnellsten wenn n groß genug ist. Dazu gibts auch coole Googology Beiträge. Gn = Graham(n) TREE(3) > G64 BB(16) > G64 BB(748) > TREE(748) RAYO(1339) > BB(2^65536)
Das allgemeine Halteproblem kann ja von einer Turing-Maschine nicht gelöst werden. Gibt es schon Antworten oder Annäherungen auf eingeschränkte Formen des Halteproblems? Also zb, gibt es eine Antwort auf "Wie viele Zustände muss eine Turing Maschine mindestens haben um das Halteproblem für Turing Maschinen mit N oder weniger Zuständen zu lösen?" Ich vermute, dass die Antwort auf diese Frage ziemlich wahrscheinlich sehr eng damit verbunden ist, wie stark die Busy Beaver numbers wachsen. EDIT: Hab das video fertig geschaut, und die unentscheidbarkeit einiger Busy Beaver Zahlen zeigt mir, dass meine Frage zumindest für allgemeine N definitiv nicht mit unserer aktuellen Mathematik zu beantworten ist.
Wenn du nur Turing-Maschinen mit endlich vielen Zuständen betrachtest gibt es immer eine Turing-Maschine, die das Halteproblem für all diese löst, da du einfach die Antwort für jede Maschine hardcoden kannst. Dafür brauchst du ungefähr genauso viele Zustände wie du Maschinen betrachten willst.
@@gehirndoper Das problem ist aber, dass es manchmal unglaublich schwer ist zu berechnen, welche Antwort man hardcoden muss (zb für die halteproblem lösende maschine mit N = 5 muss man im endeffekt BB(5) berechnen)
@@TheFerdi265 Für deine Frage spielt nur Existenz eine Rolle. Ob wir Menschen wissen, welche Antwort man hardcoden müsste, ist egal. Man müsste auch nicht BB(5) berechnen, sondern nur, welche Maschinen halten und welche nicht.
Werbung: Hier gibt es 83 % Rabatt und 4 Monate gratis bei CyberGhost VPN: www.cyberghostvpn.com/DorFuchs
Nur mal kurz ne frage wenn es um die Sicherheit geht ist es dann nicht besser und günstiger den Tor Browser bzw das vpn vom Tor-Netzwerk zu nutzen?
BB(5) einfach vor GTA 6
Haha 😂
😂😂😂😂😂😂😂😂😂😂
Gladiator 2 auch vor GTA 6 xD
@@DorFuchs es wird wahrscheinlich sogar die nächste Dedekind Zahl vor GTA 6 geben.
@@Justin-zx5bo was für eine zahl?
Die Ereignisse überschlagen sich!🚨🚨
Irgendwie amüsiert mich die Vorstellung, dass alle Mathematiker dieser Welt sich nur noch auf BB stürzen und damit nebenbei diese ganzen Dinge beweisen würden.
Das wären dann busy mathematitians
@@heroaax7589Sei BM(n) ("busy mathematicians") die minimale Anzahl von Mathematikern, die benötigt wird, um den Wert für BB(n) zu bestimmen ;)
Bringt nur nichts, letztendlich sind das auch nur Turing-Programme mit Komogorov-Komplexität und Halteproblem und damit allgemein unlösbar, also nur weil man einen Beweis als Computerprogramm schreiben kann macht es ihn nicht einfacher.
BB ist bei kleinen Zahlen ganz lustig. Aber es macht Sinn, warum bei großen Zahlen auf einmal alle diese Probleme inkludiert sind, was DorFuchs gesagt hat - je mehr Zustände, desto mehr Möglichkeiten gibt es, und auf einmal sind mehr und mehr Computerprogramme inkludiert, die das Problem codieren können. Nehme eine ausreichend große Zahl von Zuständen, und es ist auf einmal die ganze Codebase von Microsoft Word drin. Oder jegliche andere Möglichkeiten, die Code so anstellen kann. Also es macht Sinn, warum BB irgendwann von Beweisen von ein paar übersichtlichen Zuständen übergeht zu: Man beweist die anderen Sachen alle mit. Es ist einfach die Definition von BB.
BB sagt: Eigenschaft X von allen Maschinen mit Y Zuständen. Damit wird es nicht einfacher die spezifische Maschine mit Y Zuständen zu lösen, sondern sie ist einfach dabei, und muss vorher gelöst werden. Damit ist BB schwerer als alle inkludierten Probleme. Es ist keine andere Form oder bietet eine andere Sichtweise auf das Problem. Es ist nur als Über-Container definiert, der erst beantwortet werden kann, sobald alle enthaltenen Maschinen gelöst sind.
Es ist aber eine sehr geschickt definierte Zahl, das muss ich sagen. Stark, was man definieren kann, wenn man eine Funktion möchte, die möglichst stark ansteigt. Und scheinbar auch in Komplexität und Schwierigkeit stark ansteigt, dadurch, dass sie so definiert wurde, dass sie so viele anderen Komplexitäten inkludiert. Ebenfalls ist es stark, wie einfach die Definition gleichzeitig ist, und dass sie von jedem in einer kurzen Zeit verstanden werden kann.
@@IroAppe Erinnerung daran, dass MS Word nicht auf einer Turing Maschine laufen kann, da eine Turing Maschine kein Dateisystem, Bildschirm, Druckfähigkeiten, Internet oder Tastatur/Maus hat.
Krass, wie so ein vermeintlich einfaches Spiel super komplexe Fragen aufwirft.
Und du hast das wirklich schön erklärt, danke! :)
Wahrscheinlich kann man aus allem erdenklichen eine unendlich komplexe Wissenschaft machen, wenn man will. 🙂
Also ich habe auch einen Bachelor in Mathematik gemacht, aber der Typ mit der 745-er Maschine hat darüber seine Bachelor-Arbeit gemacht? WTF, also ich bin bei dem Video ausgestiegen 😅
da schäme ich mich fast für meine masterarbeit 😂
Das alles ist wirklich sehr intressant, vorallem die theoretische Informatik dahinter fasziniert mich sehr. Ich weiß ja nicht wie viel Fachwissen du in der Informatik hast, aber ein Video über weitere Themen der theoretischen Informatik, die sich sehr mit der Mathematik auseinandersetzen, wäre wirklich cool. Auch zu Bereichen wie der Mathematischen Logik, würde ich mir mal sehr gerne ein Video wünschen. Wennn es sich mal ergibt bzw. du die Zeit hast, soetwas zu machen. Dennoch mag ich all deine Videos und finde, dass du langweilige oder sehr trockene Themen, spannend und Interessant rüber bringst und sie sehr gut veranschaulichst. Weiterso, Dorfuchs!
Ohne dich hätte ich mir das nie im leben angeschaut xD
Geil, dass du dich solchen Themen widmest und die so verständlich aufbereitest
Es gibt eine Maschine mit 900 Zuständen die genau dann anhält wenn meine Frau und ich entscheiden können was wir essen wollen.
Sehr cool dass du mittlerweile Videos zu spannender Mathematik, abseits der Schulinhalte machst!!
Thank you very much for this great video!
May I just add that at 0:11, the correct crediting for the BB(5) result is (bbchallenge, 2024) and not (Stérin, 2024).
Indeed, while I created bbchallenge, the final result is the product of a collaboration involving 15+ people (listed in the credit section of the announcement post that you used in the video).
Thank you!
I was thinking of just writing (2024) because I was not sure, how to put it. Maybe "Stérin et al" would be the classical way to indicate a group effort, but I really like using just the name of the project.
Thank you for starting the project and bringing so many people together!
@@DorFuchs Thank you for talking about our story!!
Neue Forschungsergebnisse in der Mathematik sind immer so faszinierend! Danke für die klare und relativ leichte Erklärung des neuen Ergebniss.
Ich liebe diese Art von Problemen, die zu verstehen auch ohne mathematisches Spezialwissen möglich sind, die aber zu beweisen verdammt schwierig oder sogar unmöglich sind.
Die Collatz-Vermutung z.B. kann ich natürlich auch nicht beweisen, ich konnte zumindest aber meine Programmierskills dabei verbesserm, um effizient einen Zahlenraum eins bis 2 hoch n zu überprüfen.
Ich bin so glücklich das ich das video heute erst gefunden habe, ich hab vorgestern eine klausur in theoretischer Informatik geschrieben und hab alles verstanden wovon im Video geredet wurde. Bevor ich vor 2 Wochen angefangen habe zu lernen hätte ich dumm den Bildschirm angestarrt
Großartiges Video, hochgradig informativ und spannend. Danke!
Auf das Format hätt ich richtig Bock bitte regelmäßig.
Sehr schönes Video! Ich persönlich hätte es noch cool gefunden, den neu gefundenen fünften fleißigen Bieber in der schönen farbigen Darstellung zu zeigen. Auch wenn niemand 47 Mio. Schritte mit Stift und Papier durchgehen will, wäre es einfach mal interessant zu sehen, wie die fünf Zustände untereinander verknüpft sind. Und Leute, die es interessiert, hätten trotzdem mal anfangen können das auszuprobieren, nur um ein Gefühl dafür zu bekommen, wie dieser ausgeklügelte fleißige Bieber sich so verhält und warum sein Verhalten schwer zu verstehen ist. (Tipp für alle die das lesen: Auf der englischen Wikipediaseite über Busy Beaver stehen die 5 Zustände für den fünften Busy Beaver).
Noch eine Info: Normalerweise wird eher nach der Anzahl der maximalen Einsen gesucht als nach den maximalen Schritten. In dem Sinne ist BB(5)=4098. Mich würde mal interessieren, ob es auch passieren kann, daß man zwei verschiedene Busy Beaver braucht, um diese beiden Zahlen zu maximieren.
Stimmt. Den 5. fleißigen Biber hätte ich ruhig auch zeigen können. Und ja, oft sind mir S und Sigma als die maximale Anzahl der Schritte und der 1en begegnet.
Und ich weiß auch nicht, ob es immer einen fleißigen Biber geben muss, der in beiden Kategorien das Maximum erreicht. Für die bekannten 5 Beispiele ist das wohl der Fall.
Verrückt. Danke für das Video. Das hat mich nachhaltig amüsiert.
Mega cool, wie man versteht worum es bei dem Problem geht, auch mit dem Turing- Maschinen Grundwissen aus der Schule!
wollte gerade kommentieren "mach mehr solche Videos" aber dann habe ich mir mal deinen Channel durchgesehen und gemerkt, dass du das schon ne ganze Weile machst 😄 kannte dich nur von früher aus dem Mathesongs, die unser Lehrer uns vorgespielt hat. Schöne Entwicklung des Channels 😊
Die Bachelorarbeit zu BB(745) ist verdammt interessant
Nur reicht mein Amateurmathe dazu nicht aus um das zu verstehen
Das krasseste ist, dass mein Freund die geschreiben hat! Ich weiß noch, wie wir im Europapark darüber gefachsimpelt haben; unsere Freunde waren nicht so begeistert XD
@@johannesh7610 Jajaja
Dass das alles zusammenpasst und so wunderbar sich überschneidet. 😊
Mathe ist so faszinierend.
Super Video! Vielen Dank dafür! ❤
Das war beeindruckend. Haette nie gedacht an Zusammenhang von BB und Collatz, Riemann, oder Goldbach. Das is ein Supervideo!
Großartiges Video! Danke dafür. Busy Beaver und Riemann‘sche Vermutung. Darüber muss ich noch ein wenig nachdenken. Aber großer Respekt an Johannes Riebel für den Zusammenhang von BB(748) und Gödel‘s Unvollständigkeitssatz. Das sollte doch nicht nur für eine Masterarbeit reichen, oder?
Der Typ muss ein Gehirn von der Größe wie Chuck Norris' Eier haben wenn er so ne Bachelorarbeit geschrieben hat.... oder er hatte schon Forschungserfahrung und hat sich ordentlich Zeit genommen.
Was hierbei etwas untergeht ist die umgekehrte Richtung: Wenn ich BB(n) kenne, kann ich jedes Problem, dass sich mit n Zuständen darstellen lässt, leicht lösen, indem ich einfach die entsprechende Maschine mit n Zuständen laufen lasse und schaue, ob sie nach BB(n) schritten noch am laufen ist. Somit können wir nun da wir BB(5) kennen, jedes problem das sich mit 5 Zuständen lösen lässt, in relative schneller Zeit lösen.
Das ist natuerlich nur interessant fuer BB(5), da die untere Schranke fuer BB(6) schon so gross ist, das wir keine Maschine fuer so viele Schritte laufen lassen koennen.
@@hypnogri5457 Ah, aber es verrät uns auch, ob ein bestimmtes Problem berechenbar ist oder nicht, je nach dem ob die Maschine dafür anhält oder nicht.
Und das ist ja schonmal ein Anfang.
@@hypnogri5457ich kenne eine Maschine, die dein Umlautproblem löst
Soweit ich das jetzt verstehe löst das ganze aber nur das Halteproblem oder nicht und hilft uns aber nicht wirklich beim schnelleren berechnen oder?
Die Welt der Mathe ist unendlich danke sehr!
Morgen schlafe ich in Hotel Hilbert.
viel Spaß und gute Nacht, Chef!
Kann ich nicht empfehlen. Man wird ständig gebeten in das Nachbarzimmer zu wechseln...
@@Leon-eq6ei
Und das Wechseln ist völlig grundlos.
Wenn Zimmer vorhanden sind , in die vorhandene Gäste wechseln können , dann können die neu ankommenden auch direkt dort hin gehen.
Die anderen können bleiben wo sie sind .
Sehr spannend. Dankeschön.
Bitte mehr Mathe News!!!! Das ist grro0e Klasse auf die grafische Aufbereitung
Nichts verstanden. Trotzdem zu Ende geschaut
Ob der Dorffuchs den besten "Erklärsprachduktus" besitzt? Ich bin nach dem ersten Satz ausgestiegen.
Ein wunderschönes Beispiel wie unerwartet die unterschiedlichsten mathematischen Teilbereiche verbunden sein können. Tolles Video!
16:04 Zum Glück ist die Funktion
f = {
1, falls die Goldbachsche Vermutung wahr ist
0, sonst
}
berechenbar :-)
Das ist ja auch eine Funktion ohne Parameter, also konstante Funktion. Dass sie berechenbar ist, ist ziemlich offensichtlich, aber auch eine Folgerung aus folgendem Satz, mit dem man immer gut junge Studenten verwirren kann, die noch nicht ganz verstehen, was Berechenbarkeit bedeutet:
Jede Funktion mit endlichem Definitionsbereich ist berechenbar.
@@YellowBunnygibt es da überhaupt einen Definitionsbereich?
@@joshix833 Man kann es als Funktion von der leeren Menge auf {0,1} betrachten. Es existiert eine eindeutige solche Funktion, die nichts irgendwie abbildet. Weil das wenig sinnvoll und die stückweise Definition so überflüssig ist, kann man stattdessen eine beliebige einelementige Menge als Definitionsbereich wählen. Die Uneindeutigkeit, welche dieser beiden Interpretationen die richtige ist, liegt an der unpräzise Weise, wie die Funktion definiert wurde. Zum Glück sind aber sowohl 0 als auch 1 endlich Zahlen, womit der Satz in beiden Fällen anwendbar ist.
@@YellowBunny 0 und 1 wären doch der Wertebereich, oder nicht?
@@joshix833 Ja. Der Definitionsbereich ist entweder die leere Menge oder eine beliebige einelementige Menge. Der Definitionsbereich ist {0, 1}.
Skelet hatte in seiner Jugend so extra ordinär viel gedacht, dass sein Gehirn seine ganze Biomasse aufgesogen hat.
Busy Biber und Collatz ist eine interessante Kombi. Collatz kann man mit Schulkentnissen lösen. Den Grund warum jede (natürliche) Zahl beim Collatzproblem bei Eins landet ist eine Struckturverschiebung. Vereinfacht gesagt wird aus einer 9 eine 5 und das sorgt dafür, daß die ganze Stuktur kollabiert. Die 5 sorgt dafür, daß mehr Stellen abgebaut werden, als je durch die Multiplikation mit 3 aufgebaut werden können.
Ich hab noch vieles mehr rausgefunden, so kann man tatsächlich nur aus der Strukur der Zahl berechnen, wieviel Schritte diese braucht, bis zur Eins.
Es gibt bei Collatz unendlich viele Zahlen, die die Funktion der Eins übernehmen. Diese Zahlen sind 1, 5, 21, 85, 341, 1365 usw.
Lustig ist auch die Formel mit der man sofort den Wert der Struktur nach dem ersten Fall berechnen kann: (3^s * n + 3^s- 2^s) / 2^(s+1)
Das s kann man aus der Struktur der Zahl sofort ablesen. Die 7 hat z.B. den s-Wert 3.
Die Zahlen, die die 2 übernehmen hab ich auch schon identifiziert, kann sie aber mathematisch noch nicht darstellen. Auch die 3 ist schon in arbeit. Soll heißen, man kann aus allen Zahlen sofort berechnen, wieviel Schritte es bis zur eins sind.
Du solltest eine Mail an Prof. Weitz schreiben, der freut sich!
Als jemand der in 3 wochen seine theoretische Informatik klausur schreibt kann ich nur sagen wie cool das Thema ist aber wie absolut bodenlos schwer das ist, ist beinahe schon kriminell 😢
0:08 Die Zahl kam mir bekannt vor und somit hab ich gerade eine meiner eingereichten Lösungen zu Übungsblättern zu Berechenbarkeit und Komplexität aus dem Jahr 2012 herausgekramt (ist ein PDF).. und siehe da, "[...] Also terminiert M_5 auf die leere Eingabe nach 47176870 Schritten und hat 4098 Einsen auf das Band geschrieben"
Neu ist also nur der Beweis zur Minimalität. Aber ich schau trotzdem mal das Video an.. :D
Edit: Sehr coole Zusatzinfos, hat sich gelohnt!
Krass eskalierende fleißige Biber - ich lieb's! 🤩
Sehr cool! Wäre schön gewesen noch zu sehen, warum BB jede berechenbare Funktion einholt.
Glaube hat er erwaehnt. Weil jede berechenbare Funktion ein (zb Python) Programm hat welches sie berechnet. Dies bedeutet, dass es eine Turing Maschine fuer dieses Programm gibt. (und diese TM hat eine bestimmte Art von Zustaenden, sagen wir n Zustaende, sodass B(n+1) die berechenbare Funktion eingeholt hat. Und das funktioniert fuer jede berechenbare Funktion)
Wenn man die Aussage am Ende mal so richtig durchdenkt, wird es richtig wild:
Angenommen ich könnte wissen, welche Maschine mit 745 Zuständen nicht entscheidbar ist. Dann führt das zu 'nem Widerspruch, da wenn diese Maschine ja terminieren würde, ich das durch einfaches Durchrechnen beweisen kann, weshalb sie nicht terminieren kann, wodurch ich aber wüsste, dass sie nicht terminiert. Daher kann man niemals wissen, welche Maschinen nicht entscheidbar sind.
Weil die Menge aller Maschinen mit 745 Zuständen aber endlich ist, führt das zu Folgendem. Angenommen ich hätte für alle Maschinen, die entscheidbar sind, einen Beweis. Dann bliebe nur noch die Menge der Maschinen, für die ich keinen solchen Beweis finden kann und wenn ich wüsste, dass es keine Beweise mehr gibt, lande ich wieder bei obigem Widerspruch. Das ist für sich genommen nicht spektakulär, weil man in der Realität eh nur endlich viele Beweise haben kann und sich daher eh nie gewiss sein kann, aber es zeigt insbesondere, dass es keine Menge aller möglichen Beweise für die Maschinen mit 745 Zuständen geben kann, sie wäre also schlicht zu groß. Man kann also sehen, dass bereits für die Eigenschaften einer festen endlichen Zahl von Objekten die Klasse aller möglichen Beweise keine Menge mehr zu sein braucht.
Ist man nun reduktionistisch unterwegs, das heißt, denkt man, dass Menschen nichts mehr als ein hochkomplexer Roboter sind und KI uns vollständig ersetzen kann, hieße das, dass wir Menschen vollständig korrekte Beweise aufschreiben könnten, die wir nicht verstehen (denke ich zumindest). Andernfalls könnte es bedeuten, dass es eine menschliche Intuition oder metaphysische Sache geben muss, die sich nicht auf das mechanische/physische zurückführen lässt. Freilich ist diese Fragestellung für uns vermutlich wieder unentscheidbar. Wobei auch noch angemerkt sei, dass dieser letzte Absatz voraussetzt, dass ZFC mit unserer Kognition d'accord geht.
Das ging mir auch durch den Kopf! Das heißt auch, dass es mindestens zwei Maschinen geben muss, die nicht entscheidbar sind. Denn, wenn man es für alle außer einer Maschine zeigen kann, weißt du, dass die letzte nicht hält. Dann weißt du aber aus diesem Grund, dass diese zwei Maschinen nicht entscheidbar sind usw. Das wirkt paradox (ich sage bewusst nicht widersprüchlich)
Also haben wir eine obergrenze für die menge aller möglichen beweise (auf basis von zfc)?
nunja, die betroffene Turingmaschine wird doch explizit konstruiert 😅 sie kann alle formulierbaren Beweise durchgehen und bleibt stehen, wenn zwei widersprüchliche Aussagen bewiesen wurden.
Wenn die Maschine hält ist ZFC nicht widerspruchsfrei. Wenn sie nicht hält, kann das aber nicht bewiesen werden. Nur in diesem Sinne ist es nicht entscheidbar.
Diese Schlussfolgerungen sind zwar interessant, aber alles baut nur auf Axiomen auf🤯
@@espeed10 Warum sollte es zwei unentscheidbare Maschinen geben müssen. Wenn wir ein Ergebnis für alle außer einer Maschine gefunden haben, könnte es trotzdem sein, dass diese letzte Maschine nach irgendeiner gigantischen Anzahl an Schritten hält. (oder nicht, können wir ja vielleicht nicht wissen)
Hurra, Videos zu theoretischer Informatik! ❤
Ich warte noch auf TREE(4)
Sehr interessantes Video !!!
Danke für das tolle Video! :)
Ah, in der Graph-Theory gibt es auch "Funktionen" die gewaltig schnell wachsen, z. B. TREE oder was aus dem Robertson-Seymour Theorem herauskommt.
Ja aber selbst TREE wächst nicht so schnell wie BB
BB(744) erschlägt die Riemannsche Vermutung, und BB(745) ist unentscheidbar?! Wow. Dann wird die Riemannsche Vermutung wohl noch einige Jahrhunderte eine Vermutung bleiben.
Ich denke die Schlussfolgerung kann man so nicht machen. Jemand hat eine Turingmaschine mit 744 Zuständen gebaut, die die Riemannsche Vermutung per Brute Force prüft und anhält, falls ein Gegenbeispiel gefunden wird. Das sagt aber nichts darüber aus wie schwierig es ist einen Beweis oder Gegenbeweis für die Riemannsche Vermutung zu finden.
Vermutlich.
Das wirft für mich die Frage auf, ob es eine "flachere" Version der Busy-Beaver-Folge gibt, die die gleichen Zahlen durchläuft und auch monoton wächst, aber dazwischen noch viele Zwischenwerte erreicht, indem sie sich nach und nach verschiedene Arten von z.B. 5-State-Maschinen anschaut
Also, ich hätte BB(3) bis BB(5) schon mal gerne in Aktion gesehen. Naja, BB(5) vielleicht nicht unbedingt bis zum Ende...
Well, that escalated quickly.
Mach ich im Kopf
Hm, du erwähnst am Ende was zu den Dedekind-Zahlen, aber in der Videobeschreibung ist nichts dazu zu finden. Vielleicht wäre ein Link dort angebracht?
Stimmt. Ich hatte es nur in der Endcard platziert. ruclips.net/video/qg9a4vLCsuM/видео.html
Ziemlich krasse Bachelorarbeit, muss man sagen
Bitte mehr Mathe News!!!!
15:09 das klingt interessant. Könntest du dazu vielleicht ein Video machen und erklären warum das so ist?
Zu 14:00:
Was ist mit der Rayo Zahl?
Dem liegt doch auch eine Funktion zu Grunde und da der Busy Beaver mathematisch formulierbar ist, muss er langsamer wachsen als die Rayo Funktion.
Rayos Zahl ist nicht berechenbar, sie ist als Supremum über alle darstellbaren Zahlen innerhalb eines Mengensystems definiert.
Die Rayo Funktion ist nicht berechenbar (es gibt keinen Algorithmus der für jede Prädikatenlogische Aussage bestimmt ob sie wahr ist), also kann sie schneller als BB wachsen
Was mein theoretische Informatik Prof in der Prüfung erwartet:
Hoch interessant
ok, also 744 / Riemann ist der Endgegner, danach kommt 745 / Gott
Rayo(n) ist auch sehr interessant. Rayos Funktion überholt BB(n) wenn n groß genug ist
Die BB-Zahlen bezeichnen ja die längstmögliche Laufzeit, aber geht damit auch unbedingt die größtmögliche Anzahl geschriebener Einsen einher?
Ist es nicht möglich sozusagen unnötige Schritte so einzubauen, daß vielleicht die meisten Einsen sogar tatsächlich von einem Programm, das nicht so viele Schritte wie seiner Komponentenzahl entsprechend möglich wäre, macht, geschrieben werden?
Unfassbar gutes Video, Danke! Ich verstehe aber nicht; sind alle nicht berechenbaren Funktionen stärker als alle Berechenbaren? In der Verketteten Pfeilschreibweise ist cg(4)=4➡4➡4➡4 bereits größer als Grahams Zahl! Der Busy Beaver muss Chained Arrow Notation später überholen, aber wie kann man das wissen?
EDIT: Ja bei 14:00 wirds gesagt aber ich schnalls nicht,😅
Ab etwa TimeCode 13:40 erwähnst Du ja den bewiesenen Satz, dass BB schneller wächst als jede "berechenbare" Funktion f:N -> N. Da würde mich interessieren, ob es sowas wie eine "schnellst wachsende berechenbare" Funktion gibt bzw. vielleicht sogar bekannt ist.
Ich versuche die Frage mal formal zu stellen:
Sei BF die Menge aller berechenbaren Funktionen f:N->N.
Gibt es ein F in BF, so dass für alle anderen Elemente f in BF gilt:
lim_{n
ightaoorw \intfy} F(n)/f(n) = \infty ?
BB selber ist ja nicht in BF enthalten, oder?
Wenn F(n) berechenbar ist, dann ist auch F(n)+1, F(n)^2, F(n)!, F(n)^F(n) usw. berechenbar. Deswegen kann es keine "schnellst wachsende berechenbare" Funktion geben.
@@DorFuchs Danke, das leuchtet gut ein. Dass BB(n) noch schneller wächst als alle "berechenbaren" Funktionen ist dadurch noch beeindruckender bzw. weniger intuitiv.
@@DorFuchs die frage, die ich mir hier stelle: wächst BB oder die Ackermann-Funktion schneller?
Sehr cool das kannte ich gar nicht
Wäre das ganze auch 3-Dimensional möglich? Also dass man nach links, rechts, oben und unten gehen kann? Wieviel schneller würde der Wert da ansteigen?
Busy Beaver fühlt sich ein bisschen so an wie das Halting Problem einfach durchzurechnen. "Okay, es gibt keinen allgeimeinen Algorithmus um zu prüfen ob eine Turing Maschine anhält, aber was wenn wir einfach alle durchgehen und schauen ob wir beweisen können, dass sie (nicht) hält?"
Jap, der BB ist absichtlich genau so konstruiert dass das halting Problem zum Problem der Aufgabe gemacht wird um dann sagen zu können, dass das BB Problem nicht berechenbar ist. Ist mehr ein Beispiel für ein einfach zu definierendes Problem was nicht lösbar ist als eine wichtige Mathematische Frage aber das ist ja bei vielen dieser wichtigen Dinge die keinen Beweis haben so :)
Jetzt bin ich mal gespannt! (Ich bin from bei Bruchrechnung raus)
hm, also ich würde ja sagen quantencomputer lösen das problem, aber naja, das BB ist ja ein Problem wo ein zustand auf den nächsten folgt, und QTPCs sind ja nur gut darin gleichzeitig dinge ablaufen zu lassen, dass hilft dem Problem nicht unbedingt. Da muss man schon ne Zeitmaschine erfinden und einen Rechner so Millionen von Jahren rechnen lassen.
Klassische Computer können Quantencomputer simulieren, mit höchstens exponentiellem overhead. Für Berechenbarkeit bringen Quantencomputer also keinen Unterschied.
Sehr interessant
Ich mach bald mein Fach abi mit Leistungskurs Mathematik, wenn ich mir so ein Video anschaue weiß ich echt ned ob des die falsche Entscheidung war
Ich weiß zwar nicht ob es eine "erlaubte" Funtkion ist - aber wenn ich f(n) = {3, ,3, ,3, 3, 3, ...} definiere (mit n∈ℕ), also z.B. f(4) = {3, 3, ,3, 3} (wobei das hier als BAN - also der "Bird Array Notation" - gemeicht ist), dann würde es mich doch sehr wundern wenn die BB(n) Funktion schneller wachesn soll als diese Funktion. Bereits {3, 3, ,3 ,3} ("Tetratri") ist so groß dass es schon eine Herausforderung ist zu verstehen wie dieser Wert überhaupt gebildet wird (geschweige denn wie groß er isr). Jedenfalls ist dieser Potenzturm für BB(6) kaum von Null zu unterscheiden im Vergleich zu Tetratri.
Einfach Strg+C dann hält die Maschine schon...
ich verstehe nicht, wieso BB schneller wachsen soll, als eine funktion in einer programmiersprache. man kann schließlich eine funktion bauen, die BB(n) bzw. BB(n)+1 für den parameter n berechnet. ist natürlich eine unglaublich langsame funktion, die für n=5 schon nicht mehr in unserer lebenszeit zum ende kommt, aber trotzdem existiert sie.
Gäbe es eine solche Funktion, so könnte man das Halteproblem lösen, was nach einem sehr bekannten Satz von Alan Turing unmöglich ist.
@@horstheinemann2132 warum sollte das was ich beschrieben habe nicht möglich sein. man kann BB schließlich programmieren (brute force) und es somit lösen.
@@multiarray2320 Nein, wie sähe Brute Force bei BB denn aus? Wie lang willst du eine Maschine laufen lassen bis du entscheidest, daß sie nicht hält, und sie deshalb ausschließen darfst? Eine Quindezilliarde Schritte? Und wenn sie nur einen mehr gebrauch hätte lägst du falsch.
ich dachte, dass ich einen weg gefunden hatte wie man bestimmen kann ob er sich in einer schleife befindet oder nicht. aber ich irre mich offensichtlich. nur um meinen weg einmal zu erklären. wenn man für jeden schritt das gesamte band und den aktuellen zustand speichert, dann könnte man doch hetausfinden, ob sich das programm in einer schleife befindet, falls die konstellation der 0 und 1 sowie der zustand schon einmal erreicht wurden. dabei darf man natürlich nur den abschnitt des bandes betrachten, der davor schon erreicht wurde und nicht das gesamte band.
@@multiarray2320 Das geht leider nicht allgemein, weil Schleifen auch unterschiedliche Muster pro Durchlauf erzeugen können. Es könnte z.B. eine Schleife geben, die nacheinander alle durch 5 teilbaren Zahlen in Binärcode aufs Band schreibt. Dann kommt bei jedem Schleifendurchlauf ein anderer Wert aufs Band. Oder eine Schleife die alle Primzahlen aufschreibt.
"Man kann zeigen dass [berechenbare Funktionen] am Ende alles Turing Maschinen auch leisten können." (14:04) Ist das so? Ich dachte das ist nur eine These die Turing und Church aufgestellt haben
Soll das bedeuten, dass wer BB(744) beweist oder widerlegt, der beweist oder widerlegt die RH ? Selbiges gilt dann auch für GV ?
Wo findet man weiterführen Informationen über den Zusammen zwischen mathematischen Problemen und der BB ?
business biber 1, da sehe ich mich...
Ich hab mal mich ein bisschen darangesetzt. Ich habe eine Rechenvorschrift gefunden, wie man die n-te Busy Beaver Zahl berechnet.
_Nur leider ist der Platz in einem RUclips Kommentar zu klein um den Beweis des Algorithmus zu erklären_ 🌚
Interessant...
16:53
Ist BB(n) für n>=748 dann überhaupt wohldefiniert?
Nein
@@nocktv6559 Wenn BB ab einem bestimmten n nicht wohldefiniert ist, dann kann man doch nicht sagen, BB wächst schneller als jede berechenbare Funktion.
@@tochoXK3 die Antwort ist schon in deiner Frage
BB ist eine uncountable function
Also somit größer als jede "Berechenbare" Funktion
@@nocktv6559 Aber "größer" ergibt keinen Sinn, wenn di Funktion nicht wohldefiniert ist.
@@tochoXK3 Keine uncountable Function ist wirklich wohldefiniert.
Ist auch wirklich ein sehr umfassend großer Thema und nicht so kurz einfach zu erklären ohne sehr auszuschweifen.
Du kannst es dir mit den verschiedenen "Größen" der Unendlichkeiten erklären.
Die unzählbare Unendlichkeiten sind größer als Zählbare.
wieder ein mathetastisches video, fuchsi
"Extrem schnell wächst" finde ich aber auch relativ zu dem mit was man es vergleicht. Wenn ich an eine extrem schnell wachsende Zahlenfolge denke wäre das eher TREE. Die ersten fünf Zahlen von BB kann man schon mal ausschreiben. Für die sechste kennt man zumindest eine obere Grenze die man noch als Potenzturm schreiben kann und noch nicht auf Pfeilschreibweise oder andere Notationen zurückgreifen muss um die Größenordnung auf Papier zu bringen. Das beindruckende bei BB(5) ist doch wie die Zahl bewiesen wurde und nicht das die Zahl 8 Ziffern lang ist.
Bei BB(6) hat man eine *untere* Schranke. Es könnte sein, dass BB(6) bereits TREE(3) übersteigt. Und da TREE berechenbar ist, gilt auf alle Fälle BB(n) > TREE(n), wenn n hinreichend groß ist (vielleicht schon bei n=50 oder so, aber das weiß man halt nicht).
Das eigentlich interessante zum Wachstum der BB Zahlenreihe ist das je größer die Zahl wird um so schwieriger wird es die Zahl zu beweisen. Ob die exakte Größe von BB(6) überhaupt irgendwann bestimmt und bewiesen werden kann ist fragwürdig.
Korrektur für BB(6) kennt man eine untere und keine obere Grenze.
Die wichtige Frage ist doch, ob dadurch der Wetterbericht besser wird.
Kann mir jemand erklären, was das in irgend einer Form für ein Use Case geben kann? Ist dieses Wissen einfach nur logisch und cool oder wirklich nützlich?
Stell dir vor Menschen hätten sich damals gewagt von anderen eingrenzen zu lassen, weil sie keine Use Cases sahen. Wir hätten keine Handys, Technologie, kein gar nichts. (und das ist eine Untertreibung)
Wir sind hier nicht auf RUclips, weil Mathematiker damals sich Socialmedia vorgestellt haben. Aber rückblickend doch dankbar, dass sich diese Leute damit beschäftigt haben.
Bin selbst kein Experte aber solche Probleme die wie im Video erwähnt zu historischen Problemen in Verbindung stehen würden einen gewaltigen Einfluss auf die Welt der Mathematik haben.
Und nur Gott weiß wozu all dies beitragen wird, was im Endeffekt auch unser Leben beeinflussen könnte.
Auf der anderen Seite reicht es aber auch einfach faszinierend zu sein.
Würde da statt Computer besser FPGAs nehmen, in die fetten Dinger mit irgendwas 10Mio LEs passen sicher locker 100'000 von den Dingern pro FPGA, vermutlich auch so ca. 100'000-1Mio mal effizienter als mit CPU durchprobieren.
Zahlentheorie ist super (schwer)
Und die TREE Funktion so: 😴
Das ist die schnellst wachsende Folge überhaupt
nein, BB überholt TREE
also je nachdem wie "groß" n ist
@@headsetbozz5559 es geht nicht um absolute Größe. Es geht um die "Beschleunigung"
TREE (0) =O
TREE (1) = 1
TREE (2) = 3
TREE (3) = zweitgrößte jemals in einem Beweis angewandte Zahl
Wenn es um fast growing hierachies geht, schlägt nichts die TREE Funktion
What if you wanted to flex with BB(5) but I challenge you with Tree(3)
Und ich bin mir sicher dass wir Tree(3) nie genau rausfinden werden, es gibt im Universum nicht genug Atome und diese Zahl darzustellen
e^x ist keine Funktion, deren Werte natürliche Zahlen wären. Nur für x=0. Also kein gutes Beispiel für den "Satz".
That's insane
Das ist echt cool
Ganz schön fleißig, diese Bieber
Ich habe keine Chance es zu verstehen, aber ich benutze sie.
Ehm ich hab jetzt nicht ganz gerafft wie man nachweisen kann wann ein BB(n) genau dann hält, wenn eine mathematische Vermutung Eintritt 😂
Muss man dass nicht auch erstmal nachweisen mathematisch?
Bzw woher weiß ich, welche Form die einzelnen Zustände von BB(n) haben?
Um mal die Faszination großer Zahlen aufzugreifen, wie verhält sich BB zur TREE-Funktion? Weiß man bspw. ob BB(6) > TREE(3)?
BB überholt TREE spätestens bei n = 748. Tatsächlich ist Graham < Tree < BB < Rayo, also wächst Rayo am schnellsten wenn n groß genug ist. Dazu gibts auch coole Googology Beiträge.
Gn = Graham(n)
TREE(3) > G64
BB(16) > G64
BB(748) > TREE(748)
RAYO(1339) > BB(2^65536)
Das allgemeine Halteproblem kann ja von einer Turing-Maschine nicht gelöst werden.
Gibt es schon Antworten oder Annäherungen auf eingeschränkte Formen des Halteproblems? Also zb, gibt es eine Antwort auf "Wie viele Zustände muss eine Turing Maschine mindestens haben um das Halteproblem für Turing Maschinen mit N oder weniger Zuständen zu lösen?"
Ich vermute, dass die Antwort auf diese Frage ziemlich wahrscheinlich sehr eng damit verbunden ist, wie stark die Busy Beaver numbers wachsen.
EDIT: Hab das video fertig geschaut, und die unentscheidbarkeit einiger Busy Beaver Zahlen zeigt mir, dass meine Frage zumindest für allgemeine N definitiv nicht mit unserer aktuellen Mathematik zu beantworten ist.
Wenn du nur Turing-Maschinen mit endlich vielen Zuständen betrachtest gibt es immer eine Turing-Maschine, die das Halteproblem für all diese löst, da du einfach die Antwort für jede Maschine hardcoden kannst. Dafür brauchst du ungefähr genauso viele Zustände wie du Maschinen betrachten willst.
@@gehirndoper Das problem ist aber, dass es manchmal unglaublich schwer ist zu berechnen, welche Antwort man hardcoden muss (zb für die halteproblem lösende maschine mit N = 5 muss man im endeffekt BB(5) berechnen)
@@TheFerdi265 Für deine Frage spielt nur Existenz eine Rolle. Ob wir Menschen wissen, welche Antwort man hardcoden müsste, ist egal. Man müsste auch nicht BB(5) berechnen, sondern nur, welche Maschinen halten und welche nicht.
Also wenn man das machen muss um einen bachelor zu bekommen heule ich xD
Wo in der fast growing hierarchy ist denn BB?
Gibt es auch ein dreidimensionales BB? Also nicht nur Links und Rechts sondern auch hoch und runter?
Mathematiker immer so:
„Ich hab son Hirnschiss gehabt, viel Spaß beim beweisen“
Naaaa ja. Hab ChatGPT gefragt, Der sagt BB(5) ~ 600. Ich würde da vielleicht nochmal nachrechnen.🤨😅
Kannst du bitte mal ein Video zur Σ N = -1/12 machen? Es gibt so viele Leute die das tatsächlich glauben dass ich fast weine
Kann man das dann mit BAB vergleichen?