Communitytreffen-Moderator
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:
Zitat
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.
...
Zitieren
