 |
powered by 
|
| Nachrichten | Lexikon | Protokolle | Bücher | Foren | Montag, 28. Mai 2012 |
TuringmaschineDieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier. Dieser Artikel enthält mathematische Symbole die der Tabelle mit mathematischen Symbolen erklärt werden.
Die Turingmaschine ist ein von dem britischen Mathematiker Turing 1936 entwickeltes mathematisches Konstrukt um eine Klasse von berechenbaren Funktionen zu bilden und wurde zur Lösung von Kurt Gödel formulierten Vollständigkeitsproblems erdacht. Die Turingmaschine besteht aus
DefinitionEine Turingmaschine <math>\mathcal{M}</math> wird formal oft 7- Tupel <math>\mathcal{M} = \left( Q \Sigma \Gamma q_0 \square F \right)</math> dargestellt.
Eine Turingmaschine besitzt ein lineares unendliches das in einzelne Felder eingeteilt ist. Jedes Feld enthält genau ein Zeichen vorgegebenes Arbeitsalphabets (= Bandalphabet) <math>\Gamma</math> der Menge Zeichen die die Turingmaschine erkennt. <math>\Sigma \sub \Gamma</math> mit <math>\left| \Sigma < \infty</math> ist das Eingabealphabet. Das Leerzeichen \in \Gamma - \Sigma</math> steht für das Feld. Es existiert ein Schreib-/Lesekopf mit dem Zeichen eines Feldes gelesen bzw. geschrieben werden Die Maschine ist einem endlichen Automaten vergleichbar wobei es eine Zustandsmenge <math>Q</math> <math>\left| Q \right| < \infty</math> und den (= Anfangszustand) <math>q_0 \in Q</math> sowie die <math>F \sub Q</math> der akzeptierenden Zustände (= gibt. Alsdann gibt es eine Abbildungsvorschrift <math>\delta Q \times \Gamma \rightarrow Q \times \Gamma \{ -1 0 1 \}</math> (bzw. <math>\delta Q \times \Gamma \rightarrow \mathcal{P} \left( Q \Gamma \times \{ -1 0 1 \} im nichtdeterministischen Fall) die für jedes Paar aus Zeichen und aktuellem Zustand bestimmt welches Zeichen das Band geschrieben werden soll in welchen die Maschine übergehen soll und ob sich Lese-/Schreibkopf nach rechts (<math>1</math>) links (<math>-1</math>) oder nicht (<math>0</math>) bewegen soll. Die Turingmaschine arbeitet also wie folgt: liest ein Zeichen vom Band. In Abhängigkeit gelesenen Zeichen und dem Zustand in dem sie sich gerade befindet sie ein Zeichen auf das Band ändert internen Zustand und bewegt den Schreib-/Lesekopf in vorgegebene Richtung. Erreicht die Turingmaschine einen akzeptierenden also einen Zustand der Menge <math>F</math> ist Berechnung beendet. Das Ergebnis befindet sich dann dem Band.
Universelle TuringmaschineIn der obigen Definition ist das fest in die Maschine eingebaut und kann verändert werden. Man kann aber eine universelle Turingmaschine definieren die die Kodierung einer Turingmaschine Teil ihrer Eingabe nimmt und das Verhalten kodierten Turingmaschine auf der ebenfalls gegebenen Eingabe Aus der Existenz einer solchen universellen Turingmaschine z.B. die Unentscheidbarkeit des Halteproblems . Eine ähnliche Idee bei der das als ein Teil der veränderbaren Eingabedaten betrachtet liegt auch fast allen heutigen Rechnerarchitekturen zugrunde.
AllgemeinesDie Menge der Turing-berechenbaren Funktionen ist Menge aller Funktionen die sich mit einer berechnen lassen (die Turingmaschine muss die Aktion ausführen!). Es gibt noch andere Verfahren über man Berechenbarkeit von Funktionen definieren kann z. B. über rekursive Funktionen . Da andere Verfahren aber nachweislich dieselbe von Funktionen beschreiben wie die der Turingmaschine die Vermutung nahe dass alle (intuitiv) berechenbaren bereits durch das einfache Modell der Turingmaschine werden können. Dieses Ergebnis der Berechnungstheorie wird in der Churchschen These zusammengefasst.Es macht übrigens keinen Unterschied ob Turingmaschine eine oder mehrere Bänder verwendet. Auch Bandalphabet kann beliebig groß sein solange neben Leerzeichen ein weiteres Zeichen enthalten ist ist Turingmaschine zur allgemeinen Turingmaschine gleich mächtig. Ein beliebtes Problem ist der Fleißige Biber : Man finde die Turingmaschine die mit bestimmten Anzahl von Zuständen die maximale Anzahl "1"-Symbolen auf das Band schreibt und dann Für 1 bis 4 Zustände konnte das berechnet werden aber bereits für "nur" 5 ist der "beste" Fleißige Biber noch nicht Chris Langtons Ameise ist eine Turingmaschine zweidimensionalem Band mit sehr einfachen Regeln und verblüffenden Ergebnissen. Eine Abbildung und einen erklärenden findet man unter Ameise (Turingmaschine) .
Siehe auch
Literatur
Externe Verweise
| |||
| Impressum • Lesezeichen setzen • Seite versenden • Seite drucken |
<a href="http://www.uni-protokolle.de/Lexikon/Turingmaschine.html">Turingmaschine </a>