Mathe-News: 🚨 BB(5) wurde ermittelt!
ฝัง
- เผยแพร่เมื่อ 8 ก.ค. 2024
- Werbung: Hier gibt es 83 % Rabatt und 4 Monate gratis bei CyberGhost VPN: www.cyberghostvpn.com/DorFuchs
Mein am Ende erwähntes Video zu Dedekind-Zahlen:
• Die 9. Dedekind-Zahl w...
Am 2. Juli 2024 wurde BB(5) gefunden bzw. der Beweis dafür, dass der in den Jahren zuvor vermutete Wert tatsächlich korrekt ist.
Hier schauen wir uns mal an, was BB(n) bedeutet und, welche interessanten Eigenschaften diese Zahlenfolge besitzt.
Für alle, die tiefer eintauchen wollen:
Die offizielle Ankündigung des Beweises von The Busy Beaver Challenge
discuss.bbchallenge.org/t/jul...
Die Website von The Busy Beaver Challenge
bbchallenge.org/
Ein Artikel von Quanta Magazine, der die Historie des Problems sehr schön beschreibt
www.quantamagazine.org/amateu...
Johannes Riebel, The Undecidability of BB(748), Bachelorarbeit
www.ingo-blechschmidt.eu/asse...
T-Shirts: www.DorFuchs.de/t-shirts/
Facebook: / dorfuchs
Instagram: / dor.fuchs
Twitter: / dorfuchs
TH-cam: / dorfuchs
Website: www.DorFuchs.de/
Playlist mit allen Mathe-Songs: bit.ly/MatheSongs
Spotify: bit.ly/DorFuchsSpotify
iTunes: bit.ly/DorFuchsiTunes
Dieses Video wurde für die private, nicht-kommerzielle Nutzung produziert und veröffentlicht und ist in diesem Rahmen ohne Rücksprache oder schriftlicher Genehmigung für private Zwecke kostenfrei zu verwenden. Bitte beachten Sie jedoch, dass das Video weder inhaltlich noch grafisch verändert werden darf. Geben Sie bei einer Verwendung bitte stets den TH-cam-Kanal DorFuchs als Quelle an. Für die kommerzielle Nutzung sowie die Nutzung zu zustimmungspflichtigen Nutzungshandlungen zu Bildungszwecken, wie öffentliche Filmvorführungen, öffentliche Zugänglichmachungen über Bildungsserver, Lernplattformen oder Bildungsclouds, usw. ist eine Lizenzierung erforderlich. Lizenzen erhalten Sie bei unserem Vertriebspartner www.filmsortiment.de. Dieses Video ist für schulische Unterrichtszwecke geeignet und bestimmt und daher ein geschütztes Werk gemäß §60a und §60b UrhG.
![[LIVE] : ONE ลุมพินี 73 วันนี้!! คู่เอก "วรพล vs พันฤทธิ์"](http://i.ytimg.com/vi/rrOljlqse3A/mqdefault.jpg)
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?
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.
Die Ereignisse überschlagen sich!🚨🚨
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 😂
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.
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!
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!!
Skelet hatte in seiner Jugend so extra ordinär viel gedacht, dass sein Gehirn seine ganze Biomasse aufgesogen hat.
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.
Neue Forschungsergebnisse in der Mathematik sind immer so faszinierend! Danke für die klare und relativ leichte Erklärung des neuen Ergebniss.
Großartiges Video, hochgradig informativ und spannend. Danke!
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.
Sehr spannend. Dankeschön.
Auf das Format hätt ich richtig Bock bitte regelmäßig.
Verrückt. Danke für das Video. Das hat mich nachhaltig amüsiert.
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 😊
Danke für das tolle Video! :)
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
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.
Mega cool, wie man versteht worum es bei dem Problem geht, auch mit dem Turing- Maschinen Grundwissen aus der Schule!
Sehr interessantes Video !!!
Das war beeindruckend. Haette nie gedacht an Zusammenhang von BB und Collatz, Riemann, oder Goldbach. Das is ein Supervideo!
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 😢
ok, also 744 / Riemann ist der Endgegner, danach kommt 745 / Gott
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 .
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?
Sehr interessant
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
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.
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)
Ein wunderschönes Beispiel wie unerwartet die unterschiedlichsten mathematischen Teilbereiche verbunden sein können. Tolles Video!
Hoch interessant
Krass eskalierende fleißige Biber - ich lieb's! 🤩
Interessant...
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.
Ich warte noch auf TREE(4)
Sehr cool das kannte ich gar nicht
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.
Heyy das ist ja der Mond aus Mario World
@@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?
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?
15:09 das klingt interessant. Könntest du dazu vielleicht ein Video machen und erklären warum das so ist?
Bitte mehr Mathe News!!!!
Mach ich im Kopf
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!
Hurra, Videos zu theoretischer Informatik! ❤
Was mein theoretische Informatik Prof in der Prüfung erwartet:
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
Das ist echt cool
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)
Also, ich hätte BB(3) bis BB(5) schon mal gerne in Aktion gesehen. Naja, BB(5) vielleicht nicht unbedingt bis zum Ende...
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?
Ziemlich krasse Bachelorarbeit, muss man sagen
wieder ein mathetastisches video, fuchsi
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
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
Jetzt bin ich mal gespannt! (Ich bin from bei Bruchrechnung raus)
Well, that escalated quickly.
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,😅
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?
cooler Typ
Rayo(n) ist auch sehr interessant. Rayos Funktion überholt BB(n) wenn n groß genug ist
"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
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 :)
business biber 1, da sehe ich mich...
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.
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?
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. th-cam.com/video/qg9a4vLCsuM/w-d-xo.html
Kann man das dann mit BAB vergleichen?
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.
Total interessant 🥱
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.
That's insane
Einfach Strg+C dann hält die Maschine schon...
Mathematiker immer so:
„Ich hab son Hirnschiss gehabt, viel Spaß beim beweisen“
Also wenn man das machen muss um einen bachelor zu bekommen heule ich xD
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.
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 habe keine Chance es zu verstehen, aber ich benutze sie.
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)
Wow
Wo in der fast growing hierarchy ist denn BB?
Die wichtige Frage ist doch, ob dadurch der Wetterbericht besser wird.
lange Rede kurzer Sinn: BB(6) ist der Endgegner xD
Justin Bieber wat?
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
😮
Ganz schön fleißig, diese Bieber
Thüring maschün Züstand
Deutschland ist ausgeschieden...
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
ok und jetz mit 2D Gitter statt nur ein Band :D
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?
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.
Es ist auch ziemlich intuitiv warum BB(x) schneller wächst als jede Berechenbare Funktion:
Angenommen es gäbe eine berechenbare Funktion die noch schneller wächst, dann könnten wir mit dieser eine obere Schranke für BB(x) bilden. Wenn wir nun testen wollen, ob eine Turingmaschine hält, müssten wir sie nur so lange laufen lassen, bis sie diese Schranke überschritten hat, also hätten wir das Halteproblem gelöst.
Da dieses aber unlösbar ist, haben wir einen Widerspruch.
Na ja, damit hätten wir das Halteproblem für Turing-Maschinen für BB-Funktionen gelöst. Beim Halte-Problem geht es ja aber nicht nur um solche speziellen Turing-Maschinen, sondern um _alle_ Turing-Maschinen.
@bjornfeuerbacher5514 Die BB Turingmaschinen sind aber genau die Turing maschinen, die am längsten brauchen um zu halten. Alle anderen halten entweder früher oder gar nicht
@@bjornfeuerbacher5514 Gibt es denn turing Maschinen, deren Verhalten sich nicht mit BB Maschinen emulieren lässt?
@@luiswi Ja und? Beim Halteproblem geht es ja nicht darum, wie lange eine Maschine läuft. Sondern nur darum, ob sie überhaupt hält oder nicht.
@@onecommunistboi Ich habe keine Informatik studiert, aber soweit ich Turing-Maschinen verstanden habe, würde ich sagen: ja.
"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.
Bloodborne 5? Ich Depp wusste nicht mal von einem 2. Teil