Skriptsprache des RPG Maker 2000/2003 Turing-vollständig?

[Maturion]

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.

[DFYX]

Ich habe gerade keine Zeit, das ausführlich zu formulieren und zu formatieren, daher einfach nur, was ich in Discord geschrieben habe. Man braucht gar nichts so kompliziertes, wie µ-rekursive Funktionen, man kann auch einfach direkt (und sehr einfach) zeigen, dass man beliebige Turingmaschinen in Makerskript simulieren kann:

Mit der Einschränkung, dass du kein unbegrenztes Band hast (aber das hat ja kein realer Computer), kannst du im Maker beinahe trivial eine Turingmaschine simulieren
Grobe Skizze:
Eine Turingmaschine besteht aus einem Zustandsautomaten und einem Band.
Du hast deinen aktuellen Zustand S, eine aktuelle Bandposition P und das Symbol an der aktuellen Bandposition X
Übergänge sind definiert als (S, X) -> (S', X', +/-/0/H)
+ heißt, du gehst auf dem Band einen Schritt vor, - heißt, du gehst einen Schritt zurück, 0 heißt, du bleibst an der gleichen Position, H heißt, die Maschine hält
S' und X' sind der neue Zustand und das neue Symbol auf dem Band
Variable 0001 beinhaltet S
Variable 0002 beinhaltet P
Die restlichen Variablen sind das Band
Dein Zustandsautomat ist ein Loop mit einer Reihe an if/else innen drin
Zum Lesen vom Band kannst du die Variable mit der Nummer, die in P steht, lesen (habe jetzt gerade nicht im Kopf, ob das in if direkt geht. Ansonsten kopierst du den Wert am Anfang der Schleife in Variable 0003 und arbeitest damit, dann hast du halt ein minimal kleineres Band)
Die if/else-Konstruktion prüft S und X
+/-/0 implementierst du, indem du den Wert von Variable 0002 veränderst
H beendet die Schleife
X' implementierst du, indem du den neuen Wert in die Variable mit der Nummer in P schreibst
S', indem du die Nummer des neuen Zustands in S schreibst
Offensichtlich lassen sich mit den passenden Befehlen beliebige Turingmaschinen implementieren
Also auch die Turingmaschine, die eine Turingmaschine simuliert
Und damit bist du turingvollständig.

...

[Maturion]

Vielen Dank für die Antwort. Hat mir sehr geholfen.