Dieser Artikel enthält mathematische Symbole, die in der Tabelle mit mathematischen Symbolen erklärt werden.
Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes mathematisches Modell, um eine Klasse von berechenbaren Funktionen zu bilden und wurde zur Lösung des von Kurt Gödel formulierten Vollständigkeitsproblems erdacht.
Die Turingmaschine besteht aus
- einem unendlich langen Speicherband mit unendlich vielen Feldern. In jedem dieser Felder kann genau ein Zeichen gespeichert werden.
- einem Schaltwerk mit endlich vielen Zuständen. Es steuert das Verhalten der Turingmaschine.
- einem programm-gesteuerten Lese- und Schreibkopf, der auf dem endlosen Speicherband ein Feld nach links oder rechts rücken, ein Zeichen lesen, schreiben oder löschen und stehen bleiben kann.
Turing zeigte, dass diese Maschine jedes algorithmisierbare (berechenbare) Problem lösen kann; siehe dazu Church-Turing-These.
Definition
Eine Turingmaschine wird formal oft als 7-Tupel dargestellt.
Eine Turingmaschine besitzt ein lineares, unendliches Band, das in einzelne Felder eingeteilt ist.
Jedes Feld enthält genau ein Zeichen eines vorgegebenes Arbeitsalphabets (= Bandalphabet) , der Menge der Zeichen, die die Turingmaschine erkennt.
mit ist das Eingabealphabet. Das Leerzeichen steht für das leere Feld.
Es existiert ein Schreib-/Lesekopf, mit dem das Zeichen eines Feldes gelesen bzw. geschrieben werden kann. Die Maschine ist einem endlichen Automaten vergleichbar, wobei es eine Zustandsmenge mit , und den Startzustand (= Anfangszustand) , sowie die Menge der akzeptierenden Zustände (= Endzustandsmenge), gibt.
Alsdann gibt es eine Abbildungsvorschrift (bzw. im nichtdeterministischen Fall), die für jedes Paar aus gelesenem Zeichen und aktuellem Zustand bestimmt, welches Zeichen auf das Band geschrieben werden soll, in welchen Zustand die Maschine übergehen soll und ob sich der Lese-/Schreibkopf nach rechts ( ), links ( ) oder gar nicht ( ) bewegen soll.
Die Turingmaschine arbeitet also wie folgt: sie liest 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, ändert ihren internen Zustand und bewegt den Schreib-/Lesekopf in die vorgegebene Richtung. Erreicht die Turingmaschine einen akzeptierenden Zustand, also einen Zustand der Menge , ist die Berechnung beendet. Das Ergebnis befindet sich dann auf dem Band.
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, die 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 z.B. 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.
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.
Es macht übrigens keinen Unterschied, ob eine Turingmaschine eine oder mehrere Bänder verwendet. Auch das Bandalphabet kann beliebig groß sein, solange neben dem Leerzeichen ein weiteres Zeichen enthalten ist, ist eine Turingmaschine zur allgemeinen Turingmaschine gleich mächtig.
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. Für 1 bis 4 Zustände konnte das Problem berechnet werden, aber bereits für "nur" 5 Zustände ist der "beste" Fleißige Biber noch nicht bekannt.
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).
Siehe auch
Literatur
- Oswald Wiener, Manuel Bonik, Robert Hödicke: Eine elementare Einführung in die Theorie der Turing-Maschinen, Springer Verlag, ISBN 3-211-82769-2
- Rolf Herken: The Universal Turing Machine - A Half-Century Survey, Springer Verlag, ISBN 3-211-82637-8
- Heinz Lüneburg: Rekursive Funktionen, Springer Verlag, ISBN 3-540-43094-6
Weblinks
- Die Turing-Maschine - Über berechenbare Zahlen mit einer Anwendung auf das Entscheidungsproblem
- Turing-Maschine Simulator
- Theoretische Informatik