Definition Turingmaschine

Was ist eine Turingmaschine?

Eine Turingmaschine wird durch einen Tupel beschrieben. Sei TM eine Turingmaschine. Dann sei TM gegeben durch:

TM=(E, B, S, d, s0, F)

Wobei

  • E die Bandinschrift ist (= Menge der verschiedenen Zeichen die auf dem Speicherband am Anfang vorhanden sind).
  • B das Bandalphabet ist (= Menge der verschiedenen Zeichen, die auf dem Speicherband der Turingsmaschine vorkommen können).
  • S die Menge aller Zustände der Turingmaschine ist.
  • d die Überführungsfunktion darstellt
  • s0 der Anfangszustand ist, der automatisch am Anfang erreicht wird.
  • F die Menge aller Endzustände darstellt.

Eine Turingmaschine verfügt über ein unendlich langes Speicher- / Arbeitsband. Auf diesem Speicherband können sowohl Schreibe- als auch Leseoperationen durchgeführt werden.

Die Überführungsfunktion einer Turingmaschine schaut sich immer den aktuellen Zustand und das aktuelle Element des Speicherbandes an, und bestimmt anhand dieser Information einen Folgezustand. Jedoch muss in der Überführungsfunktion angegeben werden, in welche Richtung sich der Lese- und Schreibkopf der Turingmaschine bewegen soll – ob nach links, nach rechts oder überhaupt nicht.

Sowie Automaten können Turingmaschinen zur Überprüfung der Akzeptanz von Wörtern benutzt werden.