Additionsprogramm
Die Turingmaschine soll zwei Zahlen auf dem Band addieren.
Die anfängliche Bandbelegung besteht aus zwei Zahlen, verknüpft durch das Zeichen "+", gefolgt von dem Zeichen "=".
Start
Wenn die Maschine hält, soll die Summe der beiden Zahlen auf dem Band stehen:
Ziel
Strategie
Eine mögliche Strategie, das zu erreichen, ist:
Unvollständiges Programm
Ein Programm zu dieser Strategie sieht so aus:
Beachte!
Immer wenn eine Turingmaschine keine anwendbare Zeile findet, geht sie automatisch in den HALT-Status über. Damit ist dann die Berechnung beendet!