Turingmaschine (TM)
Eine Turingmaschine besteht aus einem Arbeitsband, auf welchem Symbole durch einen Schreib- und Lesekopf (kurz: SL-Kopf genannt) gelesen und nach festen Regeln geschrieben werden. Diese Regeln nennen wir Übergangsregeln.
Man unterscheidet zwischen deterministischen und nicht-deterministischen Turingmaschinen. Letztere ist nicht mehr eindeutig festgelegt, sodass es mehrere Möglichkeiten für potentielle Übergänge gibt (siehe unten). Wir wollen uns zunächst auf deterministische Turingmaschinen beschränken.
Das Konzept wird hier nur theoretisch behandelt. Es kann auch in der Praxis nachgebaut werden. Mittlerweile gibt es jedoch weitaus effizientere Möglichkeiten zur Realisierung von Computern. Im Folgenden ist der schematische Aufbau einer Turingmaschine dargestellt. Die einzelnen Komponenten werden weiter unten einzeln erläutert. Arbeitsband Das Arbeitsband kann man sich als eine unendliche Aneinanderreihung von sogenannten Zellen vorstellen. Eine Zelle ist dabei eine Box, in die man einen Buchstaben schreiben und wieder auslesen kann. Ist die Zelle leer, schreibt man ein sogenanntes Blank-Symbol (oft auch leeres Symbol oder Leerzeichen genannt): \(\square\). Auf das Arbeitsband wird i.d.R. ein Wort (Aneinanderreihung von Zeichen) eingelesen, welches mit Hilfe der Übergangsregeln bearbeitet wird. Schreib- und Lesekopf Der Schreib- und Lesekopf zeigt zu jeder Zeit auf genau eine Zelle des Arbeitsbands. Er kann das in dieser Zelle befindliche Zeichen lesen und entsprechend bestimmten Regeln wieder beschreiben. Außerdem ist er in der Lage, Kopfbewegungen durchzuführen. Er kann sich entweder nach rechts (R), nach links (L) oder gar nicht (N, neutral) bewegen. Zustand Eine Turingmaschine befindet sich stets in einem bestimmten Zustand. Dieser Zustand kann sich ändern, während die Maschine ausgeführt wird. Der Startzustand muss jedoch stets angegeben werden. Übergangsfunktion Die Übergangsfunktion sucht sich aus einer Liste von möglichen Übergängen den passenden heraus und führt ihn aus. An dieser Stelle sei erwähnt, dass es bei nicht-deterministischen Turingmaschinen statt einer Übergangsfunktion eine sogenannte Übergangsrelation gibt. Einen Übergang kann man sich als Vorschrift vorstellen. Ausgehend vom aktuellen Zustand des Systems sowie dem aktuell gelesenen Zeichen wird in einen Zustand übergegangen, sowie ein neues Zeichen geschrieben (der Zustand und oder das Zeichen können dabei jedoch auch dasselbe bleiben). Anschließend wird noch eine Kopfbewegung (L, N, R) ausgeführt. Die einzelnen Komponenten in Die Übergangsfunktion führt, wie oben bereits beschrieben Übergänge aus. Es wird dabei zwischen deterministischen und nicht-deterministischen Turingmaschinen unterschieden. Formal schreibt man dabei: Im Gegensatz zu deterministischen Turingmaschinen ist bei nichtdeterministischen Turingmaschinen nicht nur ein Verlauf möglich. Ausgehend von der aktuellen Konfiguration der Maschine sind mittels der Übergangsrelation nun mehrere mögliche Abläufe möglich. Der Ablauf ist nun nicht mehr deterministisch (festgelegt). Formale Sprachen Mehrbandmaschinen Zu jeder k-Band-Turingmaschine \(M\) lässt sich eine 1-Band-Turingmaschine \(M'\) konstruieren, sodass gilt: \(L(M) = L(M')\). Dies bedeutet, dass beide Maschinen dieselbe Sprache akzeptieren. BerechenbarkeitAufbau einer Turingmaschine
Formale Definition einer Turingmaschine
Eine Turingmaschine ist ein Tupel der Form:1\[ TM = (Z, \Sigma, \Gamma, \delta, z_0, \square, E) \](Die Reihenfolge kann je nach Konvention leicht abweichen)1
sind:Übergangsfunktion
Ausblick
In der theoretischen Informatik werden die Begriffe der Grammatik und Sprache formal definiert. Dabei nimmt man eine von Noam Chomsky formulierte Hierarchie als Grundlage. Diese besteht aus vier verschiedenen Klassen von Grammatiken, welche je eine Sprache erzeugen. Turingmaschinen beschreiben die allgemeinste der vier Klassen, die Typ 0 Sprachen.Definition
Eine Sprache \(L\) ist vom Typ 0 genau dann, wenn es eine Turingmaschine \(M\) gibt mit \(L(M)\).Definition: akzeptieren einen Worts
Ein Wort \(w\) wird akzeptiert, wenn sich die Turingmaschine \(M\) nach dem Lesen des letzten Zeichens in einem Endzustand befindet. Dann befindet sich das Wort in der von der M erzeugten Sprache und man schreibt: \(w \in L(M)\)
Das Konzept der Turingmaschine kann auch auf beliebig viele Bänder (Anzahl k) erweitert werden. Dabei befindet sich auf jedem der k Bänder ein eigener Kopf. Übergänge der Mehrband-Turingmaschine hängen somit nicht nur von dem aktuellen Zustand ab, sondern auch von den gelesenen Zeichen auf den k Bändern ab. Die Übergangsfunktion ändert sich zu:
Turingmaschinen spielen auch bei der Prüfung der Berechenbarkeit einer Funktion eine fundamentale Rolle. Eine Funktion \(f\) gilt als berechenbar, sofern es einen Algorithmus gibt, der f berechnet, also nach endlich vielen Schritten mithält.