Zur MathePrisma-Startseite
Zur Modul-Startseite  


Turingmaschine (Programme 2)
 
 
 
Ein Sortierprogramm









Anfangszustand
 
 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.



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.


Bis kein B mehr vorhanden ist:

    Suche ein B, lösche dieses und schreibe es hinter die Zeichenkette aus A's.
 

























Markierungen setzen
 
 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?


Abhilfe:

    Man setzt auf dem Band Markierungen, z.B.:

   
  • " # " für den Anfang der Bandbeschriftung und
  • "%" um das Ende der zu sortierenden Zeichenkette zu markieren.


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.

 
Lade nun im Simulator das Programm "Sortieren Teil 1", ergänze das Programmfragment und teste es.
 
Seite 7/17