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