Turingmaschine
Eine Turingmaschine ist ein von Alan Turing 1936 eingeführtes mathematisches Konstrukt, um eine Klasse von berechenbaren Funktionen zu bilden.
| Table of contents |
|
2 Funktionsweise 3 Allgemeines |
Jedes Feld enthält genau ein Zeichen eines vorgegebenes Bandalphabets B, in dem ein Zeichen, das sog. Leerzeichen z, das für das leere Feld steht, ausgezeichnet ist.
Es existiert ein Schreib-/Lesekopf, mit dem das Zeichen eines Feldes gelesen bzw. geschrieben werden kann. Die Maschine ist ein endlicher Automat mit der Zustandsmenge Z und dem Anfangszustand
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).Definition
Eine Turing-Maschine besitzt ein lineares, unendliches Band, das in einzelne Felder eingeteilt ist. 
1-Band Turingmaschine
aus dieser Zustandsmenge, sowie einer Teilmenge Z' von Z, die Menge der akzeptierenden Zustände. Weiterhin beinhaltet eine Turingmaschine das Arbeitsalphabet B, die Menge der Zeichen, die die TM erkennt.
Alsdann gibt es eine Abbildungsvorschrift δ:Z×B
Z×B×{-1,0,1}, 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(1), links(-1) oder gar nicht(0) bewegen soll. Funktionsweise
Die Turing-Maschine 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 Z', 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.
