Deterministische Turingmaschinen

Wir betrachten nun ein anderes Berechnungsmodell. Wir werden am Ende sehen, wie es mit Automaten zusammenhängt.

Zunächst arbeitet dieses Berechnungsmodell mit einem Band. Als dieses Modell entwickelt wurde, waren Tonbänder gerade Stand der Technik, und dass man auf ihnen Daten speichern konnte, war klar. Formal betrachten wir ein nach beiden Seiten hin unendliches Band, eine Folge von Elementen aus einem Alphabet $\cal L$. Sei zum Beispiel $\cal L = \{0,1\}$, dann sähe ein Endlosband so aus:

      -+---+---+---+---+---+---+---+-
   ... | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ...
      -+---+---+---+---+---+---+---+-

Auf einem solchen Band haben wir einen Kopf (Lesekopf, Schreibkopf), der immer auf eine Stelle zeigt, und diese auslesen und überschreiben kann.

                     ↓
      -+---+---+---+---+---+---+---+-
   ... | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ...
      -+---+---+---+---+---+---+---+-

Der Kopf hat als Operationen Bewegung nach rechts und links, auslesen, und schreiben.

Wie auch schon bei Automaten besteht unser Programm aus Zuständen. Ein Zustand kann folgendes tun:

• Aktuelle Speicherzelle auslesen
• Aktuelle Speicherzelle überschreiben
• Kopf verschieben
• Zu einem anderen Zustand springen

Eine sinnvolle Notation für Zustände ist damit folgende Tabelle:

         0 || o0 | r0 | j0
    (n) ---++----+----+----
         1 || o1 | r1 | j1

n ist dabei der Name des Zustandes. Die 0-Zeile wird ausgeführt, falls aktuell eine 0 gelesen wird. Die 1-Zeile wird ausgeführt, wenn eine 1 gelesen wird. o ist dabei jeweils 0 oder 1, das Zeichen, mit dem die aktuelle Speicherzelle überschrieben wird. r ist die richtung in die der Speicherkopf geshiftet wird, und ist entweder L (für links), S (für stationär) und R (für rechts). j ist dann jeweils der Name des Zustandes, zu dem gesprungen wird, oder E für Ende.

Zum Beispiel ist

       0 || 0 | L | 22
  (19) --++---+---+----
       1 || 0 | R | 23

ein Zustand mit der Bezeichnung 19. Wird 0 gelesen, so wird 0 geschrieben (die aktuelle Zelle also unverändert beibehalten), der Kopf wird nach links verschoben, und es wird zum Zustand 22 gesprungen. Wird 1 gelesen, so wird 0 geschrieben, der Kopf wird nach rechts verschoben, und es wird zum Zustand 23 gesprungen.