Super Mario Bros. Es ist unmöglich, es mathematisch zu lösen

Hier sind zwei Fakten zur Mathematik, die oft unbeachtet bleiben: Erstens gibt es einige Probleme, die einfach nicht gelöst werden können. Das bedeutet nicht, dass Sie persönlich nicht schlau genug sind oder dass Sie die falsche Methode verwenden, um das herauszufinden; Die Frage, Vermutung oder das Konzept wird einfach nie von irgendjemandem gelöst werden. Zweitens kann die Inspiration für anspruchsvolle mathematische Ideen manchmal von unerwarteten Seiten kommen.

Beispiel: Ein aktueller Artikel, der sich derzeit auf dem arXiv-Preprint-Server befindet (d. h. noch nicht von Experten begutachtet wurde) und nichts anderes zu tun hat als … Super Mario Bros.

Eines der seitdem veröffentlichten 2D-Mario-Spiele Neue Super Mario Bros.Wir haben gezeigt, dass alle außer… Super Mario Wonder „Es kann nicht bestimmt werden“, heißt es in dem Artikel, der von einem Forschungsteam der Hardiness Group des Computer Science and Artificial Intelligence Laboratory am MIT verfasst wurde.

Sogar für Super Mario Wonder„Es gibt Hinweise darauf, dass es so sein könnte[,] Sie fügen hinzu: „Auf der Grundlage, dass Ereignisse existieren und unendlich viele Goombas hervorbringen, das Spiel aber noch sehr neu ist, sind weitere Untersuchungen erforderlich, um die Spielmechanik gut genug zu verstehen, um mehr Aussagen über die Unfähigkeit, Entscheidungen zu treffen, zu treffen.“

Was bedeutet das in der Praxis? Ein unlösbares Problem ist im Wesentlichen das, wonach es klingt: eine Frage, auf die es unmöglich ist, eine richtige Ja- oder Nein-Antwort zu finden. In diesem Fall besteht das Problem darin, dass Sie als Spieler sich wirklich wünschen, Sie wären klarer – es heißt einfach: „Kann das Spiel geschlagen werden?“

„Schwieriger geht es nicht“, sagte Eric Demin, Informatikprofessor am MIT und einer der Autoren des Papiers. neue Welt. „Können Sie zum Ende kommen? Es gibt keinen Algorithmus, der diese Frage in einer begrenzten Zeit beantworten kann.

Nun ist es keine leichte Aufgabe, so etwas zu beweisen, da es eindeutig nicht in Frage kommt, das Spiel endlos zu spielen und gleichzeitig ein Forschungsstipendium mit Vergnügen zu nutzen. Stattdessen nutzte das Team Technologie, die bereits im Einsatz war Vor zehn Jahren Von MIT-Doktorand Linus Hamilton für das Spiel Stichwort.

„Die zentrale Idee bestand darin, den Wert jedes Zählers in … darzustellen. Stichwort Das Papier erklärt „Level durch die Anzahl der Feinde, die einen bestimmten Ort im Level besetzen, wobei ausgenutzt wird, dass diese Zahl selbst in einem Level mit fester Größe beliebig groß sein kann.“

Formal ausgedrückt baute das Team eine Zählermaschine auf: eine theoretische Maschine, die modelliert, wie ein Computer funktioniert, indem sie eine Reihe von „Zählern“ manipuliert. Es ist ganz einfach – ein Zähler drin Super Mario Bros. Es ist nur mit den Befehlen „Auf“, „Ab“ und „Sprung“ ausgestattet, mehr nicht – aber es ist unglaublich nützlich, da es das Problem einer unendlichen Anzahl von Goombas auf etwas viel einfacheres reduzieren kann: das Problem des Anhaltens.

Was bedeutet das? Nun, starten Sie ein Computerprogramm und drücken Sie „Los“ – wird das Programm jemals ablaufen? Oder einfach ewig weiterlaufen? Das mag wie eine dumme Frage erscheinen, aber das ist das festgefahrene Problem – ein klassisches Beispiel für ein unlösbares Problem. Wenn das Spiel auf ein Stoppproblem reduziert werden könnte – z.B Stichwort Könnte und vieles mehr Super Mario Bros. Spiele – dann ist es auch unentscheidbar.

„Die Idee ist, dass Sie dieses Mario-Level nicht lösen können, wenn diese spezifischen Berechnungen nicht abgeschlossen sind, und wir wissen, dass es keine Möglichkeit gibt, das zu bestimmen, und daher auch keine Möglichkeit zu bestimmen, ob Sie es tun oder nicht“, sagte DeMaine gegenüber New Scientist. Es kann das Level lösen.“

Mit anderen Worten: Wenn das nächste Mal jemand sagt, dass Sie Ihre Zeit mit albernen Videospielen verschwenden, machen Sie sich keine Sorgen – Sie können ihm stattdessen sagen, dass Sie … in Wahrheit Lösung eines unlösbaren Problems im Bereich der Komplexitätstheorie. Goombas und empfindungsfähige Dinosaurier sind nur Augenwischerei.

Die Studie wurde am veröffentlicht arXiv.