Ein Sortierprogramm
Wir könnten an dieser Stelle Programme zur Subtraktion, Multiplikation und Division schreiben. Um aber deutlich zu machen, dass die Turingmaschine mehr kann als "nur rechnen", betrachten wir nun ein Sortierprogramm.
Das folgende Programm soll eine Zeichenkette bestehend aus den Buchstaben A und B sortieren.
Anfangszustand
Zunächst überlegt man sich wieder eine Strategie, um die Zeichenkette zu sortieren.
Eine Möglichkeit:
Strategie
Bis kein A mehr vorhanden ist:
| Suche ein A, lösche dieses, laufe an das Ende der Bandbeschriftung und füge es dort ein. |
| Suche ein B, lösche dieses und schreibe es hinter die Zeichenkette aus A's. |
Diese Strategie ist zwar nicht effizient, aber leicht verständlich und auch ohne Probleme auf mehr als zwei Zeichen zu erweitern.
Problem:
| Wenn die Maschine Zeichen auf dem Band löscht entstehen "Löcher" in der Bandbeschriftung! Woher "weiß" die Maschine nun, ob überhaupt noch ein Zeichen kommt oder ob das Ende der Bandbeschriftung schon erreicht ist? |
Man setzt auf dem Band Markierungen, z.B.:
|
Markierungen setzen
Unser Programm startet also damit, die Anfang-Markierung zu setzen:
Nun ist die Maschine in Zustand 2 und soll die Ende-Markierung setzen:
Jetzt befindet sich die Maschine in Zustand 3 und soll auf dem ersten Zeichen positioniert werden. Überlege, wie das Programm zu ergänzen ist.
