Turingmaschine

Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes mathematisches Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie wurde im Rahmen des von David Hilbert im Jahr 1920 formulierten Hilbertprogramms, speziell zur Lösung des so genannten Entscheidungsproblems, in der Schrift "On Computable Numbers, with an Application to the Entscheidungsproblem" vorgestellt.

Definition

Informelle Beschreibung

1-Band Turingmaschine

Die Turingmaschine besteht aus

• einem unendlich langen Speicherband mit unendlich vielen Feldern. In jedem dieser Felder kann genau ein Zeichen gespeichert werden.
• einem programmgesteuerten Lese- und Schreibkopf, der sich auf dem endlosen Speicherband feldweise bewegen und die Zeichen verändern kann

Eine Turingmaschine modifiziert die Eingabe auf dem Band nach einem gegebenen Programm. Ist die Berechnung beendet, so befindet sich das Ergebnis auf dem Band. Es wird somit jedem Eingabewert ein Ausgabewert zugeordnet. Eine Turingmaschine muss aber nicht für alle Eingaben stoppen. In diesem Fall ist die Funktion für die Eingabe undefiniert.

Das Ergebnis der Berechnung wird manchmal als das definiert, was nach dem Anhalten auf dem Band steht. Wie die meisten Automaten wird die Turingmaschine jedoch meistens für Entscheidungsprobleme eingesetzt, also für Fragen, die mit "ja" oder "nein" zu beantworten sind. Dabei wird das Anhalten der TM als "ja" interpretiert, "nein" ist dem entsprechend durch das nicht-Anhalten signalisiert (Endlosschleife). Zu beachten ist dabei, dass sich jedes Problem als Entscheidungsproblem formulieren lässt, indem man fragt, ob ein bestimmter Wert eine Lösung für ein konkretes Problem ist.

Formale Definition

Formal kann eine deterministische Turingmaschine als 7-Tupel $M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\square ,F)$ dargestellt werden.

• $Q$ ist die endliche Zustandsmenge
• $\Sigma \subset \Gamma$ ist das endliche Eingabealphabet
• $\Gamma$ ist das endliche Bandalphabet
• $\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,0,R\}$ ist die Überführungsfunktion
• $q_{0}\in Q$ ist der Anfangszustand
• $\square \in \Gamma \setminus \Sigma$ steht für das leere Feld
• $F\subseteq Q$ ist die Menge der End- bzw. akzeptierenden Zustände

Die Turingmaschine arbeitet wie folgt: In einem bestimmten (Start-)Zustand $q_{s}$ liest sie ein Zeichen vom Band. In Abhängigkeit vom gelesenen Zeichen und dem Zustand, in dem sie sich gerade befindet, schreibt sie ein Zeichen auf das Band, bewegt den Schreib-/Lesekopf in die vorgegebene Richtung und ändert ihren internen Zustand. Dieser Vorgang wird durch die Überführungsfunktion realisiert. Damit hat die TM einen Takt ihres Arbeitszyklus' durchlaufen und steht für einen weiteren bereit.

Erreicht die Turingmaschine einen End-Zustand, also einen Zustand der Menge $F$, ist die Berechnung beendet. Das Ergebnis befindet sich dann auf dem Band.

Im nichtdeterministischen Fall ändert sich die Überführungsfunktion zu $\delta :Q\times \Gamma \rightarrow {\mathcal {P}}\left(Q\times \Gamma \times \{L,0,R\}\right)$. Hierbei steht ${\mathcal {P}}$ wie üblich für die Potenzmenge.

Beispiel

Die folgende deterministische 1-Band-Turingmaschine $M$ erwartet eine Folge von Einsen als Eingabe auf dem Band. Sie verdoppelt die Anzahl der Einsen wobei ein Leersymbol in der Mitte stehen bleibt. Aus "111" wird beispielsweise die Zeichenfolge "1110111". Der Schreib-/Lesekopf befindet sich initial auf der ersten Eins. Der Anfangszustand ist $s1$, der Endzustand $s6$.

$M=(Q,\Sigma ,\Gamma ,\delta ,s1,0,F)$

* $Q=\{s1,s2,s3,s4,s5,s6\}$
* $\Sigma =\{1\}$
* $\Gamma =\{1,0\}$
* $F=\{s6\}$

 alter geles.    schr.  neuer Kopf-     alter geles.    schr.  neuer Kopf-
 Zust. Symbol    Symbol Zust. richtg.   Zust. Symbol    Symbol Zust. richtg.
 ------------------------------------   ------------------------------------  
  s1    1   ->    0     s2     R         s4    1   ->    1     s4     L 
  s1    0   ->    0     s6     0         s4    0   ->    0     s5     L
  s2    1   ->    1     s2     R         s5    1   ->    1     s5     L  
  s2    0   ->    0     s3     R         s5    0   ->    1     s1     R
  s3    0   ->    1     s4     L          
  s3    1   ->    1     s3     R     

$M$ durchläuft zum Beispiel bei der Eingabe "11" folgende Zustände, wobei die aktuelle Kopfposition fett gedruckt ist:

 Schritt Zust. Band     Schritt Zust. Band
 -------------------    -------------------
    1    s1    11          9    s2    1001 
    2    s2    01         10    s3    1001
    3    s2    010        11    s3    10010
    4    s3    0100       12    s4    10011
    5    s4    0101       13    s4    10011
    6    s5    0101       14    s5    10011
    7    s5    0101       15    s1    11011
    8    s1    1101       16    s6    -halt-

Die Berechnung beginnt im Anfangszustand $s1$. Hier wird die erste Eins durch eine Null ersetzt, der Schreib-/Lesekopf bewegt sich nach rechts und neuer Zustand wird $s2$. Der Kopf wandert nun solange nach rechts, bis eine Null gelesen wird. Danach gelangt die Turingmaschine in den Zustand $s3$ und überliest alle weiteren Einsen, bis sie erneut eine Null findet. Diese wird dann durch eine Eins ersetzt. Im Zustand $s4$ bewegt sich der Kopf zurück, überliest wieder alle Einsen, bis er auf eine Null trifft, Zustandswechsel auf $s5$. Der Kopf bewegt sich nun solange nach links, bis die ursprünglich in Zustand $s1$ geschriebene Null gefunden wird. Diese wird wieder durch eine Eins ersetzt, der Kopf bewegt sich ein Feld nach rechts und die Turingmaschine gelangt wieder in den Zustand $s1$. Hier beginnt ein neuer Rechenzyklus.
Wird im Zustand $s1$ eine Null gelesen, so gelangt die Turingmaschine $M$ in den Endzustand $s6$, woraufhin die Berechnung beendet wird.

Variationen des Turingmaschinen-Modells

In der Literatur findet man zahlreiche unterschiedliche Definitionen der Turingmaschine, die sich jeweils in einigen Details unterscheiden. So variieren etwa die Anzahl der Bänder, das verwendete Bandalphabet, die zusätzlich verwendeten Spezialzeichen und andere Eigenschaften. Die Vielfalt ist theoretisch durch die These von Church gerechtfertigt, welche im Hinblick auf die Berechenbarkeit die Äquivalenz aller universellen Maschinenmodelle postuliert. Selbst komplexitätstheoretisch sind die Unterschiede zwischen verschiedenen Definitionen weitgehend zu vernachlässigen. So lässt sich etwa jede f(n)-zeitbeschränkte k-Bandmaschine mit beliebig großem k durch eine nur O(f²(n))-zeitbeschränkte 1-Bandmaschine simulieren. Für die Simulation beliebig vieler Bänder kommt es also zu einem maximal quadratischen Mehraufwand. Insgesamt führen alle Arten von Variationen zu nicht mehr als polynomialen Aufwandsunterschieden (wobei Aufwand hier eine beliebige Ressource meint) und sind daher für viele komplexitätstheoretische Untersuchungen vernachlässigbar. Man passt in Abhängigkeit von den Zielen der jeweiligen Analyse das verwendete Modell so an, dass die Analyse möglichst einfach durchgeführt werden kann. Folgende Beispiele zeigen Anwendungen und Variationen des Turingmaschinen-Modells.

Universelle Turingmaschine

In der obigen Definition ist das Programm fest in die Maschine eingebaut und kann nicht verändert werden. Man kann aber eine universelle Turingmaschine definieren, welche die Kodierung einer Turingmaschine als Teil ihrer Eingabe nimmt, und das Verhalten der kodierten Turingmaschine auf der ebenfalls gegebenen Eingabe simuliert. Aus der Existenz einer solchen universellen Turingmaschine folgt zum Beispiel die Unentscheidbarkeit des Halteproblems. Eine ähnliche Idee, bei der das Programm als ein Teil der veränderbaren Eingabedaten betrachtet wird, liegt auch fast allen heutigen Rechnerarchitekturen zugrunde (Von-Neumann-Architektur).

Formal ist eine universelle Turingmaschine eine Maschine UTM, die eine Eingabe w#x liest. w ist hierbei eine beliebige Beschreibung einer Maschine Mw, die zu einer bestimmten Funktion mit Eingabe x die Ausgabe berechnet. # ist ein Trennzeichen zwischen Programmbeschreibung und Eingabe. UTM simuliert also das Verhalten von Mw mit Eingabe x, wobei die zu simulierende Maschine und Eingabe ausgetauscht werden können.

Persistente Turingmaschine

Um interaktive Modelle (im Sinne von "Modellen mit Gedächtnis") durch eine Turingmaschine darzustellen, ist eine Erweiterung derselben um ebendieses Gedächtnis notwendig.

Laut Definition (Goldin et al., 2003: Turing Machines, Transition Systems and Interaction) ist eine Persistente Turingmaschine (PTM) eine nichtdeterministische 3-Band-Turingmaschine mit einem Input-, einem Arbeits- und einem Output-Band. Der Input wird auf dem Arbeits-Band verarbeitet und erst nach vollständiger Bearbeitung gelangen die Ergebnisse auf dem Output-Band zurück in die "Umwelt". Danach kann ein erneuter Input aus der Umwelt verarbeitet werden. Zwischen zwei Arbeitsschritten bleiben die Inhalte des Arbeits-Bandes als "Gedächtnis" erhalten.

Ameise

Chris Langtons Ameise ist eine Turingmaschine mit zweidimensionalem Band, mit sehr einfachen Regeln und sehr verblüffenden Ergebnissen. Eine Abbildung und einen erklärenden Text findet man unter Ameise (Turingmaschine).

Fleißiger Biber

Ein beliebtes Problem ist der Fleißige Biber: Man finde die Turingmaschine, die mit einer bestimmten Anzahl von Zuständen die maximale Anzahl von "1"-Symbolen auf das Band schreibt und dann anhält.

Beziehung Turingmaschine - Formale Sprache

Akzeptierte Sprache

Eine Turingmaschine akzeptiert eine Sprache L, wenn sie bei Eingabe eines jeden Wortes x ∈ L nach endlich vielen Schritten in einen der definierten Endzustände übergeht. Hält die Turingmaschine in einem anderen Zustand oder geht sie in eine Endlosschleife, dann wird die Eingabe x von ihr nicht akzeptiert.

Eine Sprache $L\subseteq \Sigma ^{\star }$ heißt genau dann rekursiv aufzählbar, wenn es eine deterministische Turingmaschine gibt, die L akzeptiert.

Entscheidbare Sprache

Akzeptiert eine Turingmaschine eine Sprache und hält sie zusätzlich bei allen Eingaben, die nicht zu dieser Sprache gehören, so entscheidet die Turingmaschine diese Sprache.

Eine Sprache $L\subseteq \Sigma ^{\star }$ heißt genau dann rekursiv bzw. entscheidbar, wenn es eine deterministische Turingmaschine gibt, die L entscheidet.

Allgemeines

Die Menge der Turing-berechenbaren Funktionen ist die Menge aller Funktionen, die sich mit einer Turingmaschine berechnen lassen (die Turingmaschine muss die Aktion (H) ausführen!). Es gibt noch andere Verfahren, über die man Berechenbarkeit von Funktionen definieren kann, z. B. über rekursive Funktionen. Da andere Verfahren aber nachweislich dieselbe Klasse von Funktionen beschreiben wie die der Turingmaschine, liegt die Vermutung nahe, dass alle (intuitiv) berechenbaren Funktionen bereits durch das einfache Modell der Turingmaschine berechnet werden können. Dieses Ergebnis der Berechnungstheorie wird in der Churchschen These zusammengefasst.

Erweiterung

Eine Erweiterung bildet die Church-Turing-These, die besagt, dass ein Problem, das von der Turingmaschine nicht gelöst werden kann, auch von keinem Menschen gelöst werden könnte.

Erklärung für Nicht-Mathematiker/Informatiker

Das faszinierende an einer Turing-Maschine ist, dass sie mit nur drei Operationen (lesen, schreiben und Kopf bewegen) alle lösbaren Probleme lösen kann. Sämtliche mathematischen Grundfunktionen, wie Addition und Multiplikation lassen sich mit diesen drei Operatoren simulieren. Aufbauend darauf lassen sich wiederum sämtliche restlichen vorhandenen mathematischen Funktionen erzeugen, usw.

Dieses Konzept heißt Church-Turing-These: Eine Turingmaschine kann alle intuitiv lösbaren Probleme lösen.

Ein Problem, das eine Turingmaschine nicht beantworten kann, und somit unlösbar ist, ist folgendes: „Finde eine Turingmaschine, die bestimmt, ob eine andere Turingmaschine bei einer gewissen Eingabe jemals anhält.“ So eine Turingmaschine kann es nicht geben, denn angenommen die andere Turingmaschine läuft unendlich lange (terminiert nicht), so wird unsere Turingmaschine die Frage ob sie anhält nie mit "nein" beantworten können. (siehe Halteproblem)

Ein Computer kann als eine Implementierung der Turing-Maschine angesehen werden – er operiert nur mit Nullen und Einsen (aber hier nicht unendlich vielen), und schafft es, damit die komplexesten Dinge zu berechnen.

Siehe auch

• Von-Neumann-Maschine
• Goto-Programm
• linear beschränkte Turingmaschine (LBA)
• Nichtdeterministische Turingmaschine (NTM)
• LOOP-Programm
• WHILE-Programm
• Automatentheorie

Literatur

• Oswald Wiener, Manuel Bonik, Robert Hödicke: Eine elementare Einführung in die Theorie der Turing-Maschinen, Wien / New York: Springer-Verlag 1998, ISBN 3-211-82769-2
• Turing, A., On Computable Numbers, With an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, Volume 42, 1936; reprinted in M. David (ed.), The Undecidable, Hewlett, NY: Raven Press, 1965
• Sybille Krämer, Symbolische Maschinen. Die Idee der Formalisierung im geschichtlichen Abriß, Darmstadt: Wissenschaftliche Buchgesellschaft 1988
• Rolf Herken: The Universal Turing Machine - A Half-Century Survey, Wien / New York: Springer Verlag, ISBN 3-211-82637-8
• Heinz Lüneburg: Rekursive Funktionen, Springer-Verlag, ISBN 3-540-43094-6
• Marvin Minsky: Computation: Finite and Infinite Machines, Englewood Cliffs, N.J.: Prentice-Hall 1967
• B.A. Trachtenbrot: Algorithmen und Rechenautomaten, Berlin: VEB Deutscher Verlag der Wissenschaften 1977

Weblinks

• Die Turing-Maschine - Über berechenbare Zahlen mit einer Anwendung auf das Entscheidungsproblem
• Turing-Maschine Simulator
• Theoretische Informatik
• JFLAP - Tool zum Entwerfen von Turingmaschinen