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

@KPunktFurry

15 күн бұрын

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

@DorFuchs

15 күн бұрын

Haha 😂

@chipsian

15 күн бұрын

😂😂😂😂😂😂😂😂😂😂

@chipsian

15 күн бұрын

Gladiator 2 auch vor GTA 6 xD

@Justin-zx5bo

15 күн бұрын

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

@chipsian

15 күн бұрын

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

@heroaax7589

14 күн бұрын

Das wären dann busy mathematitians

@SugarBeetMC

14 күн бұрын

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

@QuantenMagier

14 күн бұрын

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

13 күн бұрын

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

@rentetier

11 күн бұрын

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 😅

@keejay98195

14 күн бұрын

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!

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

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

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

14 күн бұрын

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

14 күн бұрын

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

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.

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

@johannesh7610

14 күн бұрын

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

12 күн бұрын

@@johannesh7610 Jajaja

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.

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

15 күн бұрын

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.

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

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

Sehr spannend. Dankeschön.

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 😊

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?

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

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

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

13 күн бұрын

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

12 күн бұрын

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

9 сағат бұрын

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

Nichts verstanden. Trotzdem zu Ende geschaut

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.

Danke für das tolle Video! :)

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

@YellowBunny

15 күн бұрын

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

15 күн бұрын

Heyy das ist ja der Mond aus Mario World

@joshix833

15 күн бұрын

​@@YellowBunnygibt es da überhaupt einen Definitionsbereich?

@YellowBunny

15 күн бұрын

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

14 күн бұрын

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

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

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

Sehr interessantes Video !!!

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

@oetzert5216

15 күн бұрын

viel Spaß und gute Nacht, Chef!

@Leon-eq6ei

14 күн бұрын

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

@user-uz5yw9mt9z

13 күн бұрын

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

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

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

14 күн бұрын

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

14 күн бұрын

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

@deinauge7894

13 күн бұрын

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

12 күн бұрын

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

@cameron7374

12 күн бұрын

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

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

Total interessant 🥱

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.

14 күн бұрын

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

Sehr interessant

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

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

12 күн бұрын

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

22 сағат бұрын

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

Hoch interessant

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

Hurra, Videos zu theoretischer Informatik! ❤

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 😢

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?

Sehr cool das kannte ich gar nicht

Interessant...

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

@hypnogri5457

13 күн бұрын

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)

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

Bitte mehr Mathe News!!!!

Mach ich im Kopf

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?

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

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

15 күн бұрын

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

@sebastianwidua2055

14 күн бұрын

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

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

11 күн бұрын

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

Ziemlich krasse Bachelorarbeit, muss man sagen

"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

wieder ein mathetastisches video, fuchsi

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

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

14 күн бұрын

Stimmt. Ich hatte es nur in der Endcard platziert. kzread.info/dash/bejne/o5ttw5avfKbZpbA.html

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

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.

Das ist echt cool

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

14 күн бұрын

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

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?

Ich warte noch auf TREE(4)

cooler Typ

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

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

2 күн бұрын

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

business biber 1, da sehe ich mich...

Kann man das dann mit BAB vergleichen?

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 ?

That's insane

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

@nocktv6559

10 күн бұрын

Nein

@tochoXK3

10 күн бұрын

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

10 күн бұрын

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

@tochoXK3

10 күн бұрын

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

@nocktv6559

9 күн бұрын

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

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

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

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

14 күн бұрын

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

14 күн бұрын

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

14 күн бұрын

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

14 күн бұрын

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.

14 күн бұрын

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

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

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

8 күн бұрын

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

8 күн бұрын

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

2 күн бұрын

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

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

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 KZread Kommentar zu klein um den Beweis des Algorithmus zu erklären_ 🌚

Justin Bieber wat?

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

"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

13 күн бұрын

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

13 күн бұрын

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

13 күн бұрын

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

Deutschland ist ausgeschieden...

Naaaa ja. Hab ChatGPT gefragt, Der sagt BB(5) ~ 600. Ich würde da vielleicht nochmal nachrechnen.🤨😅

Thüring maschün Züstand

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

Ganz schön fleißig, diese Bieber

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

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

15 күн бұрын

BB überholt TREE spätestens bei n = 748. Tatsächlich ist Graham Gn = Graham(n) TREE(3) > G64 BB(16) > G64 BB(748) > TREE(748) RAYO(1339) > BB(2^65536)

Deutsche Scott Aaronson ?

14: 02 ok das heist das f nimals in relation zu BB wachsen kann oder schneller interessant 15:57 um das zu belegen bräuchte man eine Funktion für die Primzahlen 16:35 das würde bedeutet das eine Nullstelle der realteil der rimatischen zetta Funktion einen anderen realteil als einhalb haben müste richtig? 16:50 es gibt in der Mathematik keine spitze es geht immer komplexer 17:51 ok also ich werde jetzt 745 Fakultät an der Tafel berechnen per hand, da komm ich wenigstens mit 😂😂 Und wurde nicht jede Mathematik regel schon gebrochen? Lg K.furry

EThI flashback

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

15 күн бұрын

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

15 күн бұрын

@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

15 күн бұрын

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

@bjornfeuerbacher5514

15 күн бұрын

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

15 күн бұрын

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

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

als nächstes BB(C)?

Tree(4)😏😏😏