| |
|
| Table of contents |
|
2 Allgemeines 3 Siehe auch |
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.
Allgemeines
Die Menge der Turing-berechenbaren Funktionen ist die Menge aller Funktionen, die sich mit einer Turing-Maschine berechnen lassen (die Turing-Maschine 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 Turing-Maschine eine oder mehrere Bänder verwendet. Auch das Bandalphabet kann beliebig groß sein, solange neben dem Leerzeichen ein weiteres Zeichen enthalten ist, ist eine Turing-Maschine zur allgemeinen Turing-Maschine gleichmächtig.
Ein beliebtes Problem ist der Fleißige Biber: man finde die Turing-Maschine, die mit einer bestimmten Anzahl von Zuständen die maximale Anzahl von "1"-Symbolen auf das Band schreibt und dann anhält. 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).