Deterministische Turingmaschinen

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

Einführung

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. Statt E für Ende kann man auch, bei Entscheidungsproblemen, T und F für true und false benutzen, um anzugeben, dass die Maschine eine Eingabe akzeptiert, oder eben nicht.

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.

Bei anderen Alphabeten werden es entsprechend mehr Zeilen in der Tabelle.

Ein wesentlicher Unterschied zu den bisher betrachteten Berechnungsmodellen ist, dass wir jetzt nicht nur sogenannte Entscheidungsprobleme, also Probleme, bei denen man entscheiden muss, ob ein Wort in einer Sprache ist, formalisieren können, sondern auch Algorithmen die eine Ausgabe haben.

Eine Turingmaschine formalisiert dabei eine partielle Funktion: Bei Funktionen wird jeder Eingabe eine Ausgabe zugeordnet. Bei Turingmaschinen kann es vorkommen, dass sie niemals aufhören zu laufen, und deshalb kein Ergebnis liefern. Es wird also nicht jeder Eingabe eine Ausgabe zugeordnet. Deshalb nur partielle Funktionen.

In der Informatik lässt man aber häufig das "partielle" weg, und spricht einfach von Funktionen, wenn man partielle Funktionen meint.

Beispiele

Als Ein-Ausgabekonvention wird, bei Turingmaschinen über ${\cal L}=\{0,1\}$, meistens das Unalsystem benutzt, und als Ergebnis der Berechnung wird die Unalzahl angesehen, an deren erster stelle der Kopf steht. Inkrementierung geht zum Beispiel mit

         0 || 1 | S | E         0 || 1 | L | C        0 || 0 | R | E
    (A) ---++---+---+---   (B) ---++---+---+---  (C) ---++---+---+---
         1 || 1 | R | B         1 || 1 | R | B        1 || 1 | L | C

Zweiband-Turingmaschinen

Man kann nun versuchen, Turingmaschinen zu verallgemeinern. Beispielsweise kann man ihnen mehrere Bänder geben, statt nur einem. Betrachten wir beispielsweise eine Turingmaschine mit zwei Bändern und zwei Köpfen:

          ↓
   -+---+---+---+---+---+---+-
    |   |   |   |   |   |   |
   -+---+---+---+---+---+---+-
   
                      ↓
   -+---+---+---+---+---+---+-
    |   |   |   |   |   |   |
   -+---+---+---+---+---+---+-

Entsprechend müssen die Tabellen der Zustände mehr Einträge bekommen.

Eine interessante Frage ist nun, ob Zweiband-Turingmaschinen echt mehr können, als Einband-Turingmaschinen. Tatsächlich kann man aber jedes Zweiband-Programm in ein Einband-Programm umwandeln, das dazu äquivalent ist.