Turingmaschine
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.
Table of contents |
2 Universelle Turingmaschine 3 Allgemeines 4 Erklärung für Nicht-Mathematiker/Informatiker 5 Siehe auch 6 Literatur 7 Weblinks |
Formale Definition
Formal kann eine deterministische Turingmaschine als 7-Tupel dargestellt werden.
- ist die endliche Zustandsmenge
- ist das endliche Eingabealphabet
- ist das endliche Bandalphabet
- steht für das leere Feld
- ist der Anfangszustand
- ist die Überführungsfunktion
- ist die Menge der akzeptierenden Zustände
Im nichtdeterministischenen Fall ändert sich die Überführungsfunktion zu .
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. Außerdem ist beweisbar, das sich mehrbandige Turingmaschinen durch eine einbandige simulieren lässt.
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).
Der zentrale Satz ist also: Ein Problem, das man mit einer Turingmaschine nicht lösen kann, gilt auch allgemeinhin als unlösbar.
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 opertiert nur mit Nullen und Einsen (aber hier nicht unendlich viele) und schafft es damit die komplexesten Dinge zu berechnen.
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. Erklärung für Nicht-Mathematiker/Informatiker
Das faszinierende an einer Turing-Maschine ist, das sie mit nur 3 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 3 Operatoren simulieren. Aufbauend darauf lassen sich wiederum sämtliche restlichen vorhandenen mathematischen Funktionen erzeugen, usw.Siehe auch
Literatur
Weblinks