Skriptsprache des RPG Maker 2000/2003 Turing-vollständig?
Es ist jetzt schon ein paar Jahre her, dass ich mich an der Uni mit Theoretischer Informatik auseinandergesetzt habe, aber ich habe seitdem immer wieder über diese Frage nachgedacht. Ist die Event-„Skriptsprache“ des RPG Maker 2000/2003 Turing-vollständig? Denn falls ja, würde daraus folgen, dass Makerskript selbst eine universelle Programmiersprache wäre. Genauso mächtig wie C++, Java, Python oder jede andere Sprache, zumindest theoretisch. Das klingt erstmal wenig glaubwürdig und ich habe lange nicht mehr mit dem Maker gearbeitet, weiß also gerade gar nicht mehr so genau, was mit Maker-Skript alles möglich ist. Dass Makerskript tatsächlich Turing-vollständig sein könnte, halte ich aber für durchaus möglich.
Erstmal zum Konzept der Turing-Vollständigkeit, das sicherlich den meisten hier nicht geläufig sein dürfte. Ist eine Programmiersprache oder ein Befehlssatz Turing-vollständig, kann man damit eine Turingmaschine zu simulieren. Eine Turingmaschine ist ein theoretisches Konstrukt, eine imaginäre Maschine, die alles mathematisch berechenbare auch tatsächlich berechnen kann. Programmiersprachen wie C++ sind etwa Turing-vollständig, sind also genauso mächtig wie eine Turingmaschine. Mit Turing-vollständigen Programmiersprachen oder Befehlssätzen lassen sich also alle berechenbaren Funktionen implementieren.
Daher meine Frage: Ist die Event-Skriptsprache des RM2k(3) Turing-vollständig? Falls ja, wie könnte man einen Beweis dazu erstellen? Ein Ansatz wäre es, nachzuweisen oder zu widerlegen, eines der alternativen Modelle für Turing-Vollständigkeit zu verwenden. Es gibt eine Reihe von alternativen Berechenbarkeitsmodellen, die bewiesenermaßen äquivalent zu Turing-Vollständigkeit sind. Eines davon sind die sogenannten µ-rekursiven Funktionen. Man kann durch Verwendung von Rekursion und Kombination dieser sogenannten µ-rekursiven Basisfunktionen sämtliche andere Funktionen implementieren. Kann man in einer Programmiersprache die µ-rekursiven Basisfunktionen implementieren, folgt daraus, dass diese Programmiersprache Turing-vollständig ist. Folgende Diskussion auf Stackoverflow ist auch ganz interessant.
Um die Turing-Vollständigkeit des Makers zu beweisen, müsste man also diese µ-rekursiven Funktionen mit Maker-Event-Skripts implementieren. Makerskript hat Variablen, kann Bedingungen, Schleifen inklusive Breaks, Labels und GOTO-Anweisungen und es lassen sich innerhalb eines Events andere Events aufrufen. Das sieht mir durchaus nach einem soliden Baukasten aus? Oder mache ich gerade einen Denkfehler? Fehlt etwas Essentielles? Angenommen ein solches Beweis würde gelingen, was folgt daraus? Über Kommentare würde ich mich sehr freuen. :)
