Die Turing-Maschine: Definition, Funktionsweise und universelle Konzepte

Die Turing-Maschine: Ein fundamentales Computermodell

Die Turing-Maschine ist ein von Alan Turing entwickeltes Computermodell. Sie wurde erstmals in seiner Arbeit „On Computable Numbers, with an Application to the Entscheidungsproblem“ vorgestellt, die 1936 von der London Mathematical Society veröffentlicht wurde. Diese Arbeit untersuchte Hilberts Frage, ob die Mathematik entscheidbar sei – also ob es eine Methode gäbe, die für jeden mathematischen Satz feststellt, ob er wahr oder falsch ist.

Turing konstruierte dieses formale Modell, um den Begriff des Algorithmus zu formalisieren, und bewies, dass es Probleme gibt, die von einer Maschine nicht gelöst werden können.

Beschreibung der Turing-Maschine

Eine Turing-Maschine besteht im Wesentlichen aus:

• Einem unendlichen Band, das als Speicher dient.
• Einem Kopf (Reader/Writer), der den Inhalt des Bandes liest, löscht und neue Werte schreibt.

Die erlaubten Operationen sind stark begrenzt:

1. Bewegen des Kopfes nach rechts.
2. Bewegen des Kopfes nach links.

Die gesamte Berechnung wird durch eine Zustandstabelle (Übergangsfunktion) bestimmt, die die Form hat:

(Aktueller Zustand, Gelesener Wert) → (Neuer Zustand, Geschriebener Wert, Bewegung)

Diese Tabelle nutzt den aktuellen Zustand der Maschine und das gelesene Zeichen, um festzulegen, wohin sich der Kopf bewegen soll, in welchen neuen Zustand die Maschine übergeht und welcher Wert auf das Band geschrieben wird.

Theoretische Bedeutung und Church-Turing-These

Mit diesem einfachen theoretischen Modell ist es möglich, jede Berechnung durchzuführen, die ein heutiger digitaler Computer ausführen kann. Die Analyse der Komplexität von Algorithmen basierend auf diesem Modell führte zur Kategorisierung von Problemen, wie der Unterscheidung zwischen den Klassen P und NP, deren Lösungen in polynomialer Zeit (abhängig von Determinismus bzw. Nichtdeterminismus der Turing-Maschine) gefunden werden können.

Mathematisch lässt sich beweisen, dass für jeden Computer ein äquivalentes Turing-Maschinen-Modell erstellt werden kann. Dieser Grundsatz ist die Church-Turing-These, die unabhängig von Alan Turing und Alonzo Church Mitte des 20. Jahrhunderts formuliert wurde. Die zugrunde liegende Idee ist, dass eine Turing-Maschine eine Person darstellt, die ein formal definiertes, effektives Verfahren ausführt, wobei der Speicherplatz zwar unbegrenzt ist, aber zu jedem Zeitpunkt nur ein endlicher Teil zugänglich ist.

Turing-Maschine als Sprach-Erkenner

Die Turing-Maschine kann auch als ein Automat betrachtet werden, der formale Sprachen erkennen kann. Sie ist in der Lage, die rekursiv aufzählbaren Sprachen gemäß der Chomsky-Hierarchie zu erkennen. Ihre Rechenleistung ist daher höher als die von Automaten wie endlichen Automaten oder Kellerautomaten.

Definition einer Turing-Maschine

Eine Turing-Maschine $\mathcal{M}$ kann formal als 7-Tupel definiert werden:

$$\mathcal{M} = (Q, \Sigma, \Gamma, \delta, q_0, b, F)$$

• $Q$: Eine endliche Menge von Zuständen.
• $\Sigma$: Ein endliches Eingabealphabet.
• $\Gamma$: Ein endliches Alphabet von Bandsymbolen (enthält $\Sigma$ und das Blank-Symbol).
• $\delta$: Die Übergangsfunktion (partielle Funktion).
• $q_0$: Der Anfangszustand ($q_0 \in Q$).
• $b$: Das Blank-Symbol (oder „weiß“), das unendlich oft vorkommen kann ($b \in \Gamma$, $b \notin \Sigma$).
• $F$: Die Menge der Endzustände (Akzeptanzzustände) ($F \subseteq Q$).

Die Übergangsfunktion $\delta$ bildet ein Paar aus Zustand und gelesenem Symbol auf ein Tripel ab: (neuer Zustand, neues Symbol, Bewegung), wobei die Bewegung entweder links oder rechts ist.

Beispiel: Verdopplung der Einsen

Definieren wir eine Turing-Maschine über dem Alphabet $\Sigma = \{0, 1\}$, wobei $0$ das Blank-Symbol sei. Die Maschine soll die Anzahl der Einsen verdoppeln. Wenn die Eingabe beispielsweise „111“ ist, soll die Ausgabe „1110111“ sein (wobei $0$ die Trennung darstellt).

Die Maschine arbeitet iterativ: Sie ersetzt die erste $1$ durch $0$, springt nach rechts, ersetzt die nächste $1$ durch $0$, springt zurück zur ersten $0$ (der Mitte), schreibt eine $1$, springt nach links und wiederholt den Vorgang, bis alle ursprünglichen Einsen markiert sind. Wenn sie auf die zentrale $0$ trifft, stoppt sie.

Deterministische und Nichtdeterministische Turing-Maschinen

Die Unterscheidung liegt in der Übergangsfunktion $\delta$:

• Deterministische Turing-Maschine (DTM): Für jedes Paar [Zustand, Symbol] gibt es höchstens eine mögliche Aktion.
• Nichtdeterministische Turing-Maschine (NTM): Es kann mindestens ein Paar [Zustand, Symbol] geben, für das mehrere mögliche Aktionen existieren.

Bei einer NTM kann man sich die Ausführung entweder als „bestmögliche Schätzung“ oder als „Klonen“ der Maschine vorstellen, wobei sich diese in verschiedene Zweige verzweigt, die jeweils einen möglichen Übergang verfolgen. Wenn irgendein Zweig zu einem akzeptierenden Zustand führt, akzeptiert die NTM die Eingabe.

Obwohl die Rechenfähigkeit beider Versionen äquivalent ist (jede NTM kann durch eine DTM simuliert werden), ist die Geschwindigkeit unterschiedlich: Eine NTM kann ein Wort der Länge $n$ in Zeit $O(t(n))$ erkennen, während die äquivalente DTM dafür $O(2^{t(n)})$ benötigen kann. Nichtdeterminismus kann somit die Komplexität exponentieller Probleme potenziell auf polynomiale Zeit reduzieren.

Universelle Turing-Maschine (UTM)

Eine Turing-Maschine berechnet eine spezifische partielle Funktion. Da die Beschreibung (die Tabelle) einer Turing-Maschine selbst als eine Folge von Symbolen (als String) kodiert werden kann, ist es möglich, eine Universelle Turing-Maschine (UTM) zu konstruieren. Diese UTM akzeptiert als Eingabe die Kodierung einer beliebigen anderen Turing-Maschine $\mathcal{M}$ und die Eingabe für $\mathcal{M}$, und simuliert deren Verhalten.

Turing erkannte 1947, dass man eine solche universelle Maschine bauen kann, was als Keimzelle für das Konzept des Betriebssystems (OS) gilt, das Programme (andere Maschinen) ausführen kann.

Allerdings sind viele Fragen bezüglich des Verhaltens einer beliebigen Turing-Maschine unentscheidbar. Das bekannteste Beispiel ist das Halteproblem: Es gibt keinen Algorithmus, der feststellen kann, ob eine gegebene Turing-Maschine bei einer bestimmten Eingabe jemals anhält oder in einer Endlosschleife gerät.

Quanten-Turing-Maschine (QTM)

Im Jahr 1985 wurde das Konzept der Quanten-Turing-Maschine eingeführt, basierend auf einer Variante der Church-Turing-These, dem Church-Turing-Prinzip.

Die Struktur einer QTM ähnelt der klassischen Maschine, verwendet jedoch anstelle von Bits Qubits im Speicherband. Sie besteht aus:

• Einem unendlichen Speicherband (Qubit-basiert).
• Einem Prozessor.
• Einem Cursor.