Suche Home Einstellungen Anmelden Hilfe  

3.2.4 Turingmaschinen (TM)

Schema einer TM
TM mit Steuereinheit und Arbeitsband

Man kann Turingmaschinen als Erweiterung von Linear beschränkten Automaten verstehen. Das Arbeitsband kann sowohl gelesen als auch beschrieben werden; es ist in beide Richtungen unendlich. Zur Speicherung von Zwischenergebnissen stehen somit theoretisch unendlich viele Zellen zur Verfügung. Neben dem Arbeitsband besitzen sie einen Lese-/Schreibkopf und eine Kontrolleinheit. Der Kopf kann sich in beiden Richtungen über das Arbeitsband bewegen.

Durch ein besonderes Symbol, 'B' (blank) wird eine leere Zelle markiert. In der Anfangskonfiguration enthalten alle nicht durch das Eingabewort belegten Zellen dieses Symbol und der Kopf liest das erste Zeichen der Eingabe.

Die Folgekonfiguration wird durch das aktuelle Symbol und den aktuellen Zustand bestimmt. Ein Übergang von einer Konfiguration in die nächste lässt sich durch folgende Aktionen charakterisieren:

  • Wechsel in einen vom aktuellen Zustand verschiedenen Zustand oder keine Änderung
  • Schreiben eines gegebenen Symbols in die aktuelle Zelle oder keine Änderung
  • Bewegen des Lese-/Schreibkopfes nach Links oder Rechts

1   2   3   4   5 Formale Darstellung von TM

Benutzer: Gast • Besitzer: senn • Zuletzt gešndert am: