Wenn du erfolgreich warst, steht nun der Lese/Schreibkopf über dem letzten Zeichen der zu sortierenden Folge und die Maschine befindet sich im Zustand HALT, da keine gültige Programmzeile existiert:

Der letzte Zustand, bevor die Maschine keine anwendbare Zeile mehr gefunden hat, war Zustand 7 (kein A mehr vorhanden). Nun müssen also, ausgehend von Zustand 7, die B's hinten angefügt werden.

Folgende Schritte sind noch zu programmieren:

Solange noch B's vorhanden sind:

• Zurücklaufen zum Anfang,
• erstes B finden und löschen,
• bis zum Zeichen % laufen,
• weiterlaufen bis zum ersten Leerzeichen,
• B einfügen.

Zum Schluss werden noch die beiden Markierungen gelöscht und der Lese/Schreibkopf auf den Anfang der sortierten Folge positioniert.

Beachte:

Den Zustand 3 kannst du nun nicht mehr benutzen, um den Lese/Schreibkopf zum Anfang zu bewegen, da sich die Turingmaschine sonst in einer Endlosschleife befindet.

Wenn du es bis hierher geschafft hast, sollte dir das Programmieren der fehlenden Zeilen keine Schwierigkeiten bereiten.

Im Notfall starte das fertige Sortierprogramm des Simulators.

Wir hoffen, dass du viel Spaß mit der Turingmaschine hattest und freuen uns, dass du bis hierher mitgearbeitet hast. Wenn du möchtest, erwartet dich nun eine Erläuterung der theoretischen Hintergründe und zum Schluss ein ungelöstes Problem der Informatik, an dem du dich gerne beteiligen kannst.

Wenn du Spaß am Programmieren gefunden hast, bieten wir dir eine Liste mit Ideen zu Programmen zum Weiterarbeiten sowie eine Liste mit interessanter Literatur.