Die Webseiten der Fachschaft Informatik am ERG Saalfeld

Turingmaschine

Es wird hier der Aufbau und die Arbeitweise der Turingmaschine angegeben. (Quelle Wikipedia)

Aufbau

Die TM besteht aus einem unendlich langen Speicherband mit unendlich vielen sequentiell angeordneten Feldern. Pro Feld kann genau ein Zeichen aus einem vordefinierten Alphabet gespeichert werden. Als zusätzliches Zeichen ist ein Blank (englisch für „leer/unbeschrieben“) zugelassen, das einem leeren Feld auf dem Speicherband entspricht.
Aus einem programmgesteuerten Lese- und Schreibkopf, der sich auf dem Speicherband feldweise bewegen und die Zeichen verändern kann.
Einem Steuerwerk, in dem sich das Programm befindet.

By Denniss [CC BY-SA 3.0], via Wikimedia Commons

Arbeitsweise

Mit jedem Schritt liest der Lese-Schreib-Kopf das aktuelle Zeichen, überschreibt dieses mit einem anderen (oder dem gleichen) Zeichen und bewegt sich dann ein Feld nach links oder rechts oder bleibt stehen. Welches Zeichen geschrieben wird und welche Bewegung ausgeführt wird, hängt von dem an der aktuellen Position vorgefundenen Zeichen sowie dem Zustand ab, in dem sich die Turingmaschine gerade befindet. Dies wird durch eine zu der Turingmaschine gehörende Überführungsfunktion definiert. Zu Beginn befindet sich die Turingmaschine in einem vorgegebenen Startzustand und geht bei jedem Schritt in einen neuen Zustand über. Die Anzahl der Zustände, in denen sich die Turingmaschine befinden kann, ist endlich. Ein Zustand kann mehrere Male durchlaufen werden, er sagt nichts über die auf dem Band vorliegenden Zeichen aus.

Aufbau des Programms

Ein Beispiel:
 0 1 1 R 1            bedeutet: die TM ist im Zustand 0, liest eine 1, schreibt eine 1, geht nach rechts und ist im Zustand 1
 1 1 1 R 1                      die TM ist im Zustand 1, liest eine 1, schreibt eine 1, geht nach rechts und ist im Zustand 1
 1 # 1 S 2                      die TM ist im Zustand 1, liest ein Leereichen, schreibt eine 1, stoppt und ist im Zustand 2
Die erste Spalte gibt den aktuellen Zustand an.
Die zweite Spalte gibt das Zeichen an, welches gelesen wird.
Die dritte Spalte gibt das Zeichen an, welches geschrieben wird.
Die vierte Spalte gibt die Kopfbewegung an.
die fünfte Spalte gibt den neuen Zustand an.

Aufgaben

Gegeben sei ein Band mit vier Einsen. Der Schreib-Lese-Kopf ist beim Start (wie üblich) über der ersten Eins. Simulieren Sie dieses Programm als Trockentest für das gerade angegebene Band. Beschreiben Sie das Ergebnis.

Weblinks

de.wikipedia.org/wiki/Turingmaschine

zurück