Mathe-News: 🚨 BB(5) wurde ermittelt!

Рет қаралды 153,488

26 күн бұрын

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

Пікірлер: 297

@DorFuchs 25 күн бұрын

Werbung: Hier gibt es 83 % Rabatt und 4 Monate gratis bei CyberGhost VPN: www.cyberghostvpn.com/DorFuchs

@KPunktFurry 25 күн бұрын

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?

@paulb5356 25 күн бұрын

BB(5) einfach vor GTA 6

@DorFuchs 25 күн бұрын

Haha 😂

@chipsian 25 күн бұрын

😂😂😂😂😂😂😂😂😂😂

@chipsian 25 күн бұрын

Gladiator 2 auch vor GTA 6 xD

@Justin-zx5bo 24 күн бұрын

@@DorFuchs es wird wahrscheinlich sogar die nächste Dedekind Zahl vor GTA 6 geben.

@chipsian 24 күн бұрын

@@Justin-zx5bo was für eine zahl?

@handschich7736 25 күн бұрын

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.

@heroaax7589 24 күн бұрын

Das wären dann busy mathematitians

@SugarBeetMC 24 күн бұрын

@@heroaax7589Sei BM(n) ("busy mathematicians") die minimale Anzahl von Mathematikern, die benötigt wird, um den Wert für BB(n) zu bestimmen ;)

@QuantenMagier 24 күн бұрын

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.

@IroAppe 23 күн бұрын

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.

@dragileinchen1485 25 күн бұрын

Die Ereignisse überschlagen sich!🚨🚨

@T1T0R3 25 күн бұрын

Krass, wie so ein vermeintlich einfaches Spiel super komplexe Fragen aufwirft. Und du hast das wirklich schön erklärt, danke! :)

@rentetier 20 күн бұрын

Wahrscheinlich kann man aus allem erdenklichen eine unendlich komplexe Wissenschaft machen, wenn man will. 🙂

@lt-ganymed 24 күн бұрын

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 😅

@keejay98195 23 күн бұрын

da schäme ich mich fast für meine masterarbeit 😂

@forge-squiggler 24 күн бұрын

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

@maroc4747 24 күн бұрын

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.

@nash6052 25 күн бұрын

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!

@samuelgebhardt2176 25 күн бұрын

Sehr cool dass du mittlerweile Videos zu spannender Mathematik, abseits der Schulinhalte machst!!

@tristansterin9747 24 күн бұрын

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!

@DorFuchs 24 күн бұрын

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!

@tristansterin9747 24 күн бұрын

@@DorFuchs Thank you for talking about our story!!

@hubertroscher1818 25 күн бұрын

Skelet hatte in seiner Jugend so extra ordinär viel gedacht, dass sein Gehirn seine ganze Biomasse aufgesogen hat.

@MrGeorge1896 25 күн бұрын

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.

@stefanmilicevic5322 25 күн бұрын

Neue Forschungsergebnisse in der Mathematik sind immer so faszinierend! Danke für die klare und relativ leichte Erklärung des neuen Ergebniss.

@Devon_Martinez 22 күн бұрын

Großartiges Video, hochgradig informativ und spannend. Danke!

25 күн бұрын

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.

@DorFuchs 25 күн бұрын

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.

@til2003 24 күн бұрын

Sehr spannend. Dankeschön.

@Klaussantoz 24 күн бұрын

Auf das Format hätt ich richtig Bock bitte regelmäßig.

@jan2882 18 күн бұрын

Verrückt. Danke für das Video. Das hat mich nachhaltig amüsiert.

@valscripted 19 күн бұрын

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 😊

@Tafkadasoh78 16 күн бұрын

Danke für das tolle Video! :)

@8-P 25 күн бұрын

Die Bachelorarbeit zu BB(745) ist verdammt interessant Nur reicht mein Amateurmathe dazu nicht aus um das zu verstehen

@johannesh7610 23 күн бұрын

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

@jordanllc7386 22 күн бұрын

@@johannesh7610 Jajaja

@marc8239 24 күн бұрын

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.

@alvar0jacky 25 күн бұрын

Mega cool, wie man versteht worum es bei dem Problem geht, auch mit dem Turing- Maschinen Grundwissen aus der Schule!

@ironsimonx4221 24 күн бұрын

Sehr interessantes Video !!!

@hassanalihusseini1717 24 күн бұрын

Das war beeindruckend. Haette nie gedacht an Zusammenhang von BB und Collatz, Riemann, oder Goldbach. Das is ein Supervideo!

@mehmetjj9163 18 күн бұрын

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 😢

@ddBenny 24 күн бұрын

ok, also 744 / Riemann ist der Endgegner, danach kommt 745 / Gott

@carlbrenninkmeijer8925 25 күн бұрын

Die Welt der Mathe ist unendlich danke sehr! Morgen schlafe ich in Hotel Hilbert.

@oetzert5216 24 күн бұрын

viel Spaß und gute Nacht, Chef!

@Leon-eq6ei 23 күн бұрын

Kann ich nicht empfehlen. Man wird ständig gebeten in das Nachbarzimmer zu wechseln...

@user-uz5yw9mt9z 23 күн бұрын

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

@FrankWilhelmRuediger 17 күн бұрын

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?

@KEKWEH 25 күн бұрын

Sehr interessant

@martinit4k178 24 күн бұрын

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.

@hypnogri5457 23 күн бұрын

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.

@cameron7374 22 күн бұрын

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

@Wladik0 10 күн бұрын

@@hypnogri5457ich kenne eine Maschine, die dein Umlautproblem löst

@Baschidas12 24 күн бұрын

Bitte mehr Mathe News!!!! Das ist grro0e Klasse auf die grafische Aufbereitung

@Elastico2007 24 күн бұрын

Nichts verstanden. Trotzdem zu Ende geschaut

@Salome--393 6 күн бұрын

Ob der Dorffuchs den besten "Erklärsprachduktus" besitzt? Ich bin nach dem ersten Satz ausgestiegen.

@PietSmietGeraeusche 25 күн бұрын

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.

@espeed10 24 күн бұрын

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)

@Luuniixo 23 күн бұрын

Also haben wir eine obergrenze für die menge aller möglichen beweise (auf basis von zfc)?

@deinauge7894 23 күн бұрын

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.

@heinrich6294 22 күн бұрын

Diese Schlussfolgerungen sind zwar interessant, aber alles baut nur auf Axiomen auf🤯

@cameron7374 22 күн бұрын

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

@babsibecause 24 күн бұрын

Ein wunderschönes Beispiel wie unerwartet die unterschiedlichsten mathematischen Teilbereiche verbunden sein können. Tolles Video!

@Annydenktzuviel 24 күн бұрын

Hoch interessant

@jamoke_jabroni 7 күн бұрын

Krass eskalierende fleißige Biber - ich lieb's! 🤩

@mt31415 25 күн бұрын

Interessant...

@Bruno_Haible 22 күн бұрын

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.

@NLogSpace 22 күн бұрын

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.

@danielm4333 10 күн бұрын

Vermutlich.

@aqwaa3057 19 күн бұрын

Ich warte noch auf TREE(4)

@dapengu777 25 күн бұрын

Sehr cool das kannte ich gar nicht

@Spulg 25 күн бұрын

16:04 Zum Glück ist die Funktion f = { 1, falls die Goldbachsche Vermutung wahr ist 0, sonst } berechenbar :-)

@YellowBunny 25 күн бұрын

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.

@Kosin-zs9il 24 күн бұрын

Heyy das ist ja der Mond aus Mario World

@joshix833 24 күн бұрын

@@YellowBunnygibt es da überhaupt einen Definitionsbereich?

@YellowBunny 24 күн бұрын

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

@joshix833 24 күн бұрын

@@YellowBunny 0 und 1 wären doch der Wertebereich, oder nicht?

@EinBessererMenschAlsDu 17 күн бұрын

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?

@marcmuller943 9 күн бұрын

15:09 das klingt interessant. Könntest du dazu vielleicht ein Video machen und erklären warum das so ist?

@Baschidas12 24 күн бұрын

Bitte mehr Mathe News!!!!

@deadlypendroppingby 24 күн бұрын

Mach ich im Kopf

@ichnicht1433 24 күн бұрын

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.

24 күн бұрын

Du solltest eine Mail an Prof. Weitz schreiben, der freut sich!

@NLogSpace 23 күн бұрын

Hurra, Videos zu theoretischer Informatik! ❤

@notsven810 24 күн бұрын

Was mein theoretische Informatik Prof in der Prüfung erwartet:

@mmg1279 25 күн бұрын

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.

@ziggs9053 24 күн бұрын

Rayos Zahl ist nicht berechenbar, sie ist als Supremum über alle darstellbaren Zahlen innerhalb eines Mengensystems definiert.

@sebastianwidua2055 24 күн бұрын

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

@xamtodd0360 25 күн бұрын

Das ist echt cool

@BedrockBlocker 24 күн бұрын

Sehr cool! Wäre schön gewesen noch zu sehen, warum BB jede berechenbare Funktion einholt.

@hypnogri5457 23 күн бұрын

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)

@miriamkapeller6754 23 күн бұрын

Also, ich hätte BB(3) bis BB(5) schon mal gerne in Aktion gesehen. Naja, BB(5) vielleicht nicht unbedingt bis zum Ende...

@xCorvus7x 24 күн бұрын

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?

@herkules593 24 күн бұрын

Ziemlich krasse Bachelorarbeit, muss man sagen

@zirkq 25 күн бұрын

wieder ein mathetastisches video, fuchsi

@iwersonsch5131 24 күн бұрын

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

@TheDarkElder 24 күн бұрын

Ah, in der Graph-Theory gibt es auch "Funktionen" die gewaltig schnell wachsen, z. B. TREE oder was aus dem Robertson-Seymour Theorem herauskommt.

@nocktv6559 21 күн бұрын

Ja aber selbst TREE wächst nicht so schnell wie BB

@Jestereza 24 күн бұрын

Jetzt bin ich mal gespannt! (Ich bin from bei Bruchrechnung raus)

@stanislavkozak2806 24 күн бұрын

Well, that escalated quickly.

@TheMatthiasDrummer 24 күн бұрын

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,😅

@harales7849 24 күн бұрын

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?

@Viki13 25 күн бұрын

cooler Typ

@palukku 24 күн бұрын

Rayo(n) ist auch sehr interessant. Rayos Funktion überholt BB(n) wenn n groß genug ist

@lyde9272 10 күн бұрын

"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

@Susul-lj2wm 24 күн бұрын

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?"

@zapl80 24 күн бұрын

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

@emafink3018 24 күн бұрын

business biber 1, da sehe ich mich...

@tochoXK3 24 күн бұрын

16:53 Ist BB(n) für n>=748 dann überhaupt wohldefiniert?

@nocktv6559 20 күн бұрын

Nein

@tochoXK3 20 күн бұрын

@@nocktv6559 Wenn BB ab einem bestimmten n nicht wohldefiniert ist, dann kann man doch nicht sagen, BB wächst schneller als jede berechenbare Funktion.

@nocktv6559 20 күн бұрын

@@tochoXK3 die Antwort ist schon in deiner Frage BB ist eine uncountable function Also somit größer als jede "Berechenbare" Funktion

@tochoXK3 20 күн бұрын

@@nocktv6559 Aber "größer" ergibt keinen Sinn, wenn di Funktion nicht wohldefiniert ist.

@nocktv6559 19 күн бұрын

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

@JoachimRipken 18 күн бұрын

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?

@DorFuchs 18 күн бұрын

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.

@JoachimRipken 17 күн бұрын

@@DorFuchs Danke, das leuchtet gut ein. Dass BB(n) noch schneller wächst als alle "berechenbaren" Funktionen ist dadurch noch beeindruckender bzw. weniger intuitiv.

@DieChaosBohne 11 күн бұрын

@@DorFuchs die frage, die ich mir hier stelle: wächst BB oder die Ackermann-Funktion schneller?

@TimwiTerby 24 күн бұрын

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?

@DorFuchs 24 күн бұрын

Stimmt. Ich hatte es nur in der Endcard platziert. kzfaq.info/get/bejne/p81plJensanXpYE.html

@testiyyy33 25 күн бұрын

Kann man das dann mit BAB vergleichen?

@multiarray2320 24 күн бұрын

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 24 күн бұрын

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.

@multiarray2320 24 күн бұрын

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

24 күн бұрын

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

@multiarray2320 24 күн бұрын

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.

24 күн бұрын

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

@mathiasmuller291 19 күн бұрын

Total interessant 🥱

@nikelnac3726 24 күн бұрын

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.

@gehirndoper 12 күн бұрын

Klassische Computer können Quantencomputer simulieren, mit höchstens exponentiellem overhead. Für Berechenbarkeit bringen Quantencomputer also keinen Unterschied.

@opiret44 23 күн бұрын

That's insane

@lalabumpeng4618 24 күн бұрын

Einfach Strg+C dann hält die Maschine schon...

@RealKaukus 13 күн бұрын

Mathematiker immer so: „Ich hab son Hirnschiss gehabt, viel Spaß beim beweisen“

@lars9168 15 күн бұрын

Also wenn man das machen muss um einen bachelor zu bekommen heule ich xD

@hinz1 22 күн бұрын

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.

@chrisikritiker8216 17 күн бұрын

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 ?

@carlbrenninkmeijer8925 25 күн бұрын

Ich habe keine Chance es zu verstehen, aber ich benutze sie.

@user-th6qq4lk7n 25 күн бұрын

Um mal die Faszination großer Zahlen aufzugreifen, wie verhält sich BB zur TREE-Funktion? Weiß man bspw. ob BB(6) > TREE(3)?

@palukku 24 күн бұрын

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)

@fusel 23 күн бұрын

Wow

@tobiaswilhelmi4819 Күн бұрын

Wo in der fast growing hierarchy ist denn BB?

@TimeMachine3000 25 күн бұрын

Die wichtige Frage ist doch, ob dadurch der Wetterbericht besser wird.

@derLenus 24 күн бұрын

lange Rede kurzer Sinn: BB(6) ist der Endgegner xD

@TimeFadesMemoryLasts 20 күн бұрын

Justin Bieber wat?

@weibrot6683 24 күн бұрын

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

@arnonym42 25 күн бұрын

😮

@MCRuCr 24 күн бұрын

Ganz schön fleißig, diese Bieber

@AdrianKnauff 24 күн бұрын

Thüring maschün Züstand

@alteriusnonsit6124 24 күн бұрын

Deutschland ist ausgeschieden...

@primesparrow 24 күн бұрын

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

@aqa2866 9 күн бұрын

ok und jetz mit 2D Gitter statt nur ein Band :D

@sinceredeku 8 күн бұрын

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?

@TheFerdi265 24 күн бұрын

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.

@gehirndoper 12 күн бұрын

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.

@TheFerdi265 12 күн бұрын

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

@gehirndoper 12 күн бұрын

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

@luiswi 24 күн бұрын

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.

@bjornfeuerbacher5514 24 күн бұрын

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.

@luiswi 24 күн бұрын

@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

@onecommunistboi 24 күн бұрын

@@bjornfeuerbacher5514 Gibt es denn turing Maschinen, deren Verhalten sich nicht mit BB Maschinen emulieren lässt?

@bjornfeuerbacher5514 24 күн бұрын

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

@bjornfeuerbacher5514 24 күн бұрын

@@onecommunistboi Ich habe keine Informatik studiert, aber soweit ich Turing-Maschinen verstanden habe, würde ich sagen: ja.

@TischTiger 23 күн бұрын

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

@DorFuchs 23 күн бұрын

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

@TischTiger 23 күн бұрын

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.

@TischTiger 23 күн бұрын

Korrektur für BB(6) kennt man eine untere und keine obere Grenze.