Turingmaschine (Spiel)

Veröffentlicht am von

Modifiziertes Google-Doodle…

Das folgende kleine Spiel ist eine Hommage an Alan Turing, einen der einflussreichsten Computerpioniere.
Noch heute wird ein Computer darüber definiert, dass er die gleiche Funktionalität wie eine Turingmaschine hat.

Das Spiel wurde von Google entwickelt (Original hier) und unter der Apache-Lizens freigegeben.
Ich habe lediglich ein paar Kleinigkeiten verändert und ein paar Level hinzugefügt.

Erklärung zum Spiel

Das Spiel bildet eine vereinfachte Turingmaschine nach. Ziel des Spiels ist es, die Programme so abzuändern,
dass am Ende einer Runde die gesuchte Zahl auf dem Band steht. Dazu lassen sich immer einige Elemente aus dem Programm anklicken und verändern.
Es gibt:

 Schleifen kommt das Programm dort an, springt es um die in der Schleife angegebene Anzahl Felder zurück
Bedingungen Liest Zeichen an aktueller Position, entspricht es dem Zeichen in der Bedingung, springt das Programm in die andere Programmzeile
Schieben schiebt die aktuelle Position um ein Feld in die angegebene Richtung
Schreiben schreibt das angegebene Zeichen an die aktuelle Position.

Manche Level enthalten interessante Programmelemente:

  • richtige Abbruchbedingung einer Schleife finden
  • erstes und letztes Bit der Zahl finden
  • Zahl invertieren
  • Zahl um eine Stelle verschieben
  • Zeichen nur unter bestimmten Bedingungen ersetzen

Vor Start des Spiels läuft ein binärer Zähler als Programm.
Nach erfolgreichen Beenden der Levels gibt es als Belohnung eine Art Fibonnacci-Folge (binary rabbit sequence).

Der aktuelle Spielstand wird vom Browser gespeichert. Beim erneuten Aufrufen kann so an der gleichen Stelle weiter gespielt werden.

Was ist eine Turingmaschine?

Eine Turingmaschine ist eine theoretisches Maschine, die Computerprogramme ausführen kann.
Dabei ist sie verblüffend einfach aufgebaut:

  • Band mit Feldern: In jedes Feld kann genau ein Zeichen gespeichert werden. (z.B. 0, 1, nicht definiert)
  • Lese- und Schreibkopf: wird von Steuerwerk gesteuert, kann sich auf Band feldweise bewegen
  • Steuerwerk mit Programm: Führt ein bestimmtes Programm aus, steuert Lese-/Schreibkopf

Es ist tatsächlich möglich, jedes Computerprogramm auf einer Turingmaschine auszuführen.
In umgekehrten Sinn, wird zum Beispiel jede Programmiersprache, die eine Turingmaschine nachbilden kann, turing-vollständig genannt und somit als echte Programmiersprache eingestuft.

Die wohl kleinste Programmiersprache, die diese Bedingung erfüllt ist Brainfuck
und kommt mit gerade mal 8 Befehlen aus.