Suche Home Einstellungen Anmelden Hilfe

3.2.4 Varianten von Turingmaschinen

Einseitig begrenzte TM: Bei diesen TM ist das Arbeitsband nur in eine Richtung unendlich. Der Kopf einer solchen TM kann sich nicht nach links über den Anfang des Wortes hinaus bewegen.

Nicht-deterministische TM: Wie auch bei anderen nicht-deterministischen Automaten, ist bei dieser Art von TM die Übergangsfunktion nicht eindeutig. Die Übergangsfunktion ordnet Paaren wie (q,a) eine Menge von Tripeln (p,b,H) zu.

Mehrspurige TM (multi-track): Bei dieser TM ist das Arbeitsband in weitere Zellen unterteilt. Man kann sich vorstellen, dass das Arbeitsband aus mehreren Bändern besteht, die jedoch so zusammen gefasst sind, dass die Zellen eine nach den Seiten hin unendliche Tabelle mit k Zeilen bilden. Diese TM haben sie wie bisher einen Lese-/Schreibkopf, der alle k übereinanderliegenden Zellen ( = eine "Tabellenspalte") auf einmal auslesen und beschreiben kann. Für die Übergangsfunktion ist das Ein- und Ausgabezeichen ein intern aus k Einzelsymbolen zusammengesetztes Zeichen. Für eine 3-spurige TM hätten die zusammengesetzten Symbole den Aufbau [s1,s2,s3], wobei die erste Komponente das erste Band steht, die zweite für das zweite Band usw.

Mehrköpfige TM haben k Lese-Schreibköpfe und k Arbeitsbänder. Der nächste Schritt hängt vom Zustand und vom aktuellen Eingabesymbol eines jeden Kopfes ab. Der Unterschied zur mehrspurigen TM besteht darin, dass die einzelnen Köpfe ihre Bewegung unabhängig voneinander ausführen können.

Alle diese Varianten von Turingmaschinen lassen sich auch durch die klassische TM darstellen (s.a 3.3.3). Im Prinzip sind diese Konzepte für TM Vereinfachungen in der Schreibweise. Z.B. ist Erkennen eines gespiegelten Wortes oder wiederholten Wortes sehr einfach durch TM mit zwei Bändern und zwei Köpfen. Eine normale TM müsste statt dessen immer hin und her fahren.

Sprache 1   2   3   4   5   Übersicht: Sprachklassen

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