Turingmaschine

Grundidee und Bedeutung

Eine Turingmaschine ist ein mathematisches Modell einer abstrakten Rechenmaschine. Sie führt nach festen Regeln schrittweise Zeichenmanipulationen aus und stellt damit einen Algorithmus beziehungsweise ein Programm dar. Alan Turing führte das Modell 1936/37 ein. Anders als ein physischer Computer ist die Turingmaschine ein mathematisches Objekt, an dem sich Aussagen über Algorithmen, Berechenbarkeit und Komplexität beweisen lassen.

Eine Berechnung bildet eine anfangs gespeicherte Zeichenkette auf eine Zeichenkette ab, die nach der Bearbeitung auf dem Band steht. Zeichenketten können beispielsweise als Zahlen interpretiert werden. Eine durch eine Turingmaschine berechenbare Funktion heißt Turing-berechenbar oder einfach berechenbar.

Turing entwickelte das Modell im Zusammenhang mit dem von David Hilbert 1920 formulierten Entscheidungsproblem: Gesucht war ein automatisches Verfahren, das bestimmt, ob eine Formel der Prädikatenlogik unter jeder Interpretation wahr ist. Turing zeigte, dass dieses Problem nicht durch eine Turingmaschine gelöst werden kann. Auch das Halteproblem, also die allgemeine Frage, ob ein Programm bei einer Eingabe irgendwann anhält, ist unentscheidbar.

Die Church-Turing-These besagt, dass Turing-Berechenbarkeit dem intuitiven Begriff der Berechenbarkeit entspricht. Dafür spricht unter anderem ihre mathematische Äquivalenz zu anderen Berechenbarkeitsbegriffen, etwa dem Lambda-Kalkül, partiell-rekursiven Funktionen und Registermaschinen. Trotz ihrer Einfachheit kann eine Turingmaschine mit nur drei grundlegenden Tätigkeiten – Lesen, Schreiben und Bewegen des Kopfes – alle Operationen gewöhnlicher Computerprogramme simulieren. Systeme und Programmiersprachen, die bei unbegrenztem Speicher alle Operationen einer universellen Turingmaschine ausführen können, heißen turingvollständig.

Nicht jede mathematische Funktion ist Turing-berechenbar. Nach dem Satz von Rice ist jede nicht-triviale Eigenschaft eines Programms in einer turingmächtigen Programmiersprache unentscheidbar. Selbst für stets terminierende Turingmaschinen ist unentscheidbar, ob zwei Maschinen dieselbe Sprache akzeptieren. In der Komplexitätstheorie können Laufzeit und Speicherbedarf untersucht werden; bei Turingmaschinen dient etwa die asymptotische Anzahl der Zustandsübergänge in Abhängigkeit von der Eingabelänge als Laufzeitmaß. Die Simulation vieler Registermaschinen verursacht dabei nur polynomialen Mehraufwand.

Aufbau und Arbeitsweise

Eine Ein-Band-Turingmaschine besitzt ein Steuerwerk mit dem festen Programm, ein unendlich langes Speicherband aus nacheinander angeordneten Feldern und einen programmgesteuerten Lese-Schreib-Kopf. Jedes Feld enthält genau ein Zeichen aus einem endlichen Bandalphabet. Das zusätzliche Blank-Zeichen □ bezeichnet ein leeres Feld. Der Kopf kann ein Zeichen lesen, es überschreiben oder durch ein Blank löschen und sich anschließend ein Feld nach links oder rechts bewegen oder stehen bleiben.

Zu Beginn steht das Eingabewort auf dem ansonsten leeren Band. Der Kopf befindet sich auf dessen erstem Zeichen, und die Maschine ist im Startzustand. In jedem Schritt bestimmen der aktuelle Zustand und das gelesene Bandsymbol gemeinsam, welches Zeichen geschrieben wird, wohin sich der Kopf bewegt und welcher Zustand folgt. Die Zahl möglicher Zustände ist endlich; Zustände können wiederholt durchlaufen werden und enthalten selbst keine vollständige Information über den Bandinhalt.

Eine Maschine stoppt, wenn für die Kombination aus Zustand und gelesenem Symbol kein Übergang definiert ist. Endzustände sind Zustände, in denen sie unabhängig vom Bandsymbol anhält. Für manche Eingaben kann eine Turingmaschine jedoch unbegrenzt weiterlaufen. Bei Entscheidungsproblemen werden Endzustände als akzeptierend oder nicht akzeptierend festgelegt. Eine Eingabe wird genau dann akzeptiert, wenn die Berechnung einen akzeptierenden Endzustand erreicht.

Formale Definition und Berechnung

Eine deterministische Turingmaschine wird als 7-Tupel M=(Q,Σ,Γ,δ,q₀,□,F) definiert. Dabei ist Q die endliche Zustandsmenge, Σ das endliche Eingabealphabet und Γ das endliche Bandalphabet mit Σ ⊂ Γ. q₀∈Q ist der Anfangszustand, □∈Γ∖Σ das Blank und F⊆Q die Menge der akzeptierenden Endzustände.

Die partielle Überführungsfunktion lautet δ:(Q∖F)×Γ→Q×Γ×{L,N,R}. Sie ordnet einem Zustand und einem gelesenen Zeichen genau einen nächsten Zustand, ein zu schreibendes Zeichen und eine Kopfbewegung zu: L bedeutet ein Feld nach links, R ein Feld nach rechts und N keine Bewegung. Da akzeptierende Endzustände immer anhalten, gehören sie nicht zur Definitionsmenge von δ.

Eine Konfiguration beschreibt den gesamten augenblicklichen Rechenstand: Zustand, Kopfposition und relevanten Bandinhalt. Formal ist sie ein Tripel (q,u,v) mit q∈Q und u,v∈Γ*, wobei uv den betrachteten Bandinhalt bildet und der Kopf auf dem ersten Zeichen von v steht. Nur ein endlicher Bandbereich muss angegeben werden, weil er von unendlich vielen Blanks umgeben ist. Gleichwertig kann der Zustand direkt vor dem gerade gelesenen Symbol in das Bandwort eingefügt werden. Die übliche Startkonfiguration für X₁…Xₙ ist q₀X₁…Xₙ beziehungsweise (q₀,ε,X₁…Xₙ), wobei ε das leere Wort bezeichnet.

Ein einzelner Übergang von der Konfiguration c₁ zur Nachfolgekonfiguration c₂ wird als c₁⊢c₂ geschrieben. Eine Berechnung ist eine endliche oder unendliche Folge solcher Schritte. Sie akzeptiert ein Wort, wenn sie in einem Zustand qf∈F endet. Endet sie in einer anderen Konfiguration, wird das Wort verworfen. Läuft sie unendlich weiter, wird es weder akzeptiert noch verworfen. Bei einer beendeten Funktionsberechnung bildet der verbleibende Bandinhalt die Ausgabe.

Beispiel und universelle Maschine

Die im Artikel beschriebene deterministische Ein-Band-Turingmaschine verdoppelt eine Eingabe aus Einsen und lässt zwischen Original und Kopie ein Blank stehen. Aus „11“ wird „11011“. Sie ist definiert durch M=(Q,Σ,Γ,δ,s₁,0,{s₆}) mit Q={s₁,s₂,s₃,s₄,s₅,s₆}, Σ={1}, Γ={1,0}; dabei steht 0 für das Blank. Der Kopf beginnt auf der ersten Eins im Anfangszustand s₁.

In jedem Arbeitszyklus ersetzt die Maschine zunächst eine noch nicht bearbeitete Eins durch ein Blank. Sie läuft nach rechts über die verbleibenden ursprünglichen Einsen, überquert das trennende Blank und bewegt sich über die bereits erzeugte Kopie. Am rechten Ende schreibt sie eine neue Eins. Danach kehrt sie nach links zurück, stellt die vorübergehend gelöschte Eins wieder her und beginnt den nächsten Zyklus. Liest sie in s₁ ein Blank, wechselt sie in den Endzustand s₆. Für die Eingabe „11“ endet die Berechnung nach dem 16. aufgeführten Schritt mit „11011“.

Bei einer gewöhnlichen Turingmaschine ist das Programm fest eingebaut. Eine universelle Turingmaschine UTMφ erhält dagegen eine kodierte Maschinenbeschreibung zusammen mit deren Eingabe und simuliert die beschriebene Maschine. Formal liest sie w∥x: w beschreibt eine Maschine Mw, x ist deren Eingabe und ∥ ein Trennzeichen. Der Index φ weist darauf hin, dass verschiedene universelle Maschinen unterschiedliche Kodierungssprachen verstehen können. Die Idee, ein Programm als veränderbare Eingabe zu behandeln, ähnelt der Von-Neumann-Architektur heutiger Rechner. Aus der Existenz universeller Turingmaschinen folgt beispielsweise die Unentscheidbarkeit des Halteproblems.

Äquivalente Varianten und verwandte Modelle

Viele Definitionsvarianten sind hinsichtlich der Berechenbarkeit äquivalent: Eine Maschine lässt sich in eine andere Variante umwandeln, ohne die berechenbaren Ergebnisse zu verändern. Möglich sind etwa nur ein akzeptierender Endzustand, zusätzliche verwerfende Zustände, eine stets nach links oder rechts erfolgende Kopfbewegung, eine totale Überführungsfunktion oder ein nur einseitig unendliches Band. Weitere äquivalente Modelle sind Mehrspur- und Mehrband-Turingmaschinen, vergessliche Turingmaschinen mit nur von der Eingabelänge abhängigen Kopfbewegungen, Zweikellerautomaten sowie Zählermaschinen mit mindestens zwei Zählern. Viele Simulationen verursachen höchstens polynomialen Mehraufwand. Turing beschrieb außerdem ein Verfahren, eine normalisierte Überführungstabelle durch Ersetzen ihrer Bestandteile mit Zahlen als eine einzige lange Ganzzahl zu kodieren.

Eine nichtdeterministische Turingmaschine verwendet statt einer Übergangsfunktion eine Übergangsrelation und kann daher mehrere mögliche nächste Schritte besitzen. Sie akzeptiert, wenn mindestens eine mögliche Berechnung einen akzeptierenden Endzustand erreicht. Eine alternierende Turingmaschine unterscheidet existentielle Zustände, bei denen eine akzeptierende Berechnung genügt, und universelle Zustände, bei denen alle möglichen Berechnungen akzeptieren müssen.

Orakel-Turingmaschinen dürfen bestimmte zusätzliche Operationen in einem Schritt ausführen, beispielsweise Lösungen unentscheidbarer oder sehr aufwendiger Probleme. Probabilistische Turingmaschinen wählen zufällig aus zwei beziehungsweise endlich vielen möglichen Übergängen und modellieren randomisierte Algorithmen. Quanten-Turingmaschinen beschreiben theoretisch die Möglichkeiten von Quantencomputern. Eine persistente Turingmaschine ist eine nichtdeterministische 3-Band-Maschine mit Eingabe-, Arbeits- und Ausgabeband; ihr Arbeitsband bleibt zwischen Eingaben als Gedächtnis erhalten. Die fiktive Zenomaschine beschleunigt ihre Schritte in geometrischer Reihe und liegt jenseits der Turing-Berechenbarkeit.

Bekannte Sondermodelle sind der Fleißige Biber und Langtons Ameise. Ein Fleißiger Biber schreibt unter allen terminierenden deterministischen Maschinen mit gleicher Zustands- und Symbolzahl maximal viele Exemplare eines bestimmten Symbols und hält dann. Weder diese maximale Symbolzahl, die Radó-Funktion, noch die benötigte Schrittzahl ist allgemein berechenbar. Langtons Ameise arbeitet nach sehr einfachen Regeln auf einer zweidimensionalen Fläche; ihr zunächst chaotisch wirkender Inhalt bildet nach über 10.000 Schritten eine sichtbare Struktur.

Formale Sprachen und Entscheidbarkeit

Eine Turingmaschine akzeptiert eine Sprache L, wenn sie für jedes Wort x∈L nach endlich vielen Schritten in einem akzeptierenden Zustand hält und für jedes x∉L entweder in einem nicht akzeptierenden Zustand hält oder überhaupt nicht anhält. Eine Sprache L⊆Σ* ist genau dann rekursiv aufzählbar beziehungsweise semientscheidbar, also vom Typ 0 der Chomsky-Hierarchie, wenn eine Turingmaschine existiert, die L akzeptiert. Damit entsprechen die von Turingmaschinen akzeptierten Sprachen den durch Typ-0-Grammatiken definierbaren Sprachen.

Eine Turingmaschine entscheidet eine Sprache, wenn sie diese akzeptiert und außerdem bei jeder Eingabe, die nicht zur Sprache gehört, anhält. Eine Sprache L⊆Σ* heißt genau dann rekursiv oder entscheidbar, wenn es eine Turingmaschine gibt, die L entscheidet. Der wesentliche Unterschied lautet daher: Beim bloßen Akzeptieren darf die Maschine für Wörter außerhalb der Sprache unendlich laufen; beim Entscheiden muss sie für jede mögliche Eingabe ein Ergebnis liefern.