Turingmaschine Bedeutung, Erklärung und Definition.
Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes mathematisches Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie wurde im Rahmen des von David Hilbert im Jahr 1900 formulierten Hilbertprogramms, speziell zur Lösung des so genannten Entscheidungsproblems, in der Schrift "On Computable Numbers, with an Application to the Entscheidungsproblem" vorgestellt.
Die Turingmaschine besteht aus
Das Ergebnis der Berechnung wird manchmal als das definiert, was nach dem Anhalten auf dem Band steht. Wie die meisten Automaten wird die Turingmaschine jedoch meistens fĂŒr Entscheidungsprobleme eingesetzt, also fĂŒr Fragen, die mit "ja" oder "nein" zu beantworten sind. Dabei wird das Anhalten der TM als "ja" interpretiert, "nein" ist dem entsprechend durch das nicht-Anhalten signalisiert (Endlosschleife). Zu beachten ist dabei, dass sich jedes Problem als Entscheidungsproblem formulieren lĂ€sst, indem man fragt, ob ein bestimmter Wert eine Lösung fĂŒr ein konkretes Problem ist.
Definition
Informelle Beschreibung
Eine Turingmaschine modifiziert also eine Eingabe auf dem Band nach einem gegebenen Programm. Ist die Berechnung beendet, so befindet sich das Ergebnis auf dem Band. Es wird somit jedem Eingabewert ein Ausgabewert zugeordnet. Eine Turingmaschine muss aber nicht fĂŒr alle Eingaben stoppen. In diesem Fall ist die Funktion fĂŒr die Eingabe undefiniert. Formale Definition
Formal kann eine deterministische Turingmaschine als 7-Tupel dargestellt werden.
Die Turingmaschine arbeitet wie folgt:
In einem bestimmten (Start-)Zustand liest sie 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, bewegt den Schreib-/Lesekopf in die vorgegebene Richtung und Ă€ndert ihren internen Zustand. Dieser Vorgang wird durch die ĂberfĂŒhrungsfunktion realisiert. Damit hat die TM einen Takt ihres Arbeitszyklus' durchlaufen und steht fĂŒr einen weiteren bereit.
Erreicht die Turingmaschine einen End-Zustand, also einen Zustand der Menge , ist die Berechnung beendet. Das Ergebnis befindet sich dann auf dem Band.
Im nichtdeterministischenen Fall Ă€ndert sich die ĂberfĂŒhrungsfunktion zu . Hierbei steht wie ĂŒblich fĂŒr die Potenzmenge.
durchlÀuft zum Beispiel bei der Eingabe "11" folgende ZustÀnde, wobei die aktuelle Kopfposition fett gedruckt ist:
Schritt Zust. Band Schritt Zust. Band
------------------- -------------------
1 s1 11 9 s2 1001
2 s2 01 10 s3 1001
3 s2 010 11 s3 10010
4 s3 0100 12 s4 10011
5 s4 0101 13 s4 10011
6 s5 0101 14 s5 10011
7 s5 0101 15 s1 11011
8 s1 1101 16 s6 -halt-
Eine Turingmaschine akzeptiert eine Sprache L, wenn sie bei Eingabe eines jeden Wortes x â L nach endlich vielen Schritten in einen der definierten EndzustĂ€nde ĂŒbergeht. HĂ€lt die Turingmaschine in einem anderen Zustand oder geht sie in eine Endlosschleife, dann wird die Eingabe x von ihr nicht akzeptiert.
Eine Sprache heiĂt genau dann rekursiv aufzĂ€hlbar, wenn es eine deterministische Turingmaschine gibt, die L akzeptiert.
Akzeptiert eine Turingmaschine eine Sprache und hÀlt sie zusÀtzlich bei allen Eingaben, die nicht zu dieser Sprache gehören, so entscheidet die Turingmaschine diese Sprache.
Eine Sprache heiĂt genau dann rekursiv bzw. entscheidbar, wenn es eine deterministische Turingmaschine gibt, die L entscheidet.
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 ein 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, dass sich mehrbandige Turingmaschinen durch eine einbandige simulieren lassen.
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.
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).
Eine Erweiterung bildet die Church-Turing-These, die besagt, dass ein Problem, das von der Turingmaschine nicht gelöst werden kann, auch von keinem Menschen gelöst werden könnte.
Das faszinierende an einer Turing-Maschine ist, dass sie mit nur drei 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 drei Operatoren simulieren. Aufbauend darauf lassen sich wiederum sÀmtliche restlichen vorhandenen mathematischen Funktionen erzeugen, usw.
Dieses Konzept heisst Church-Turing-These: Eine Turingmaschine kann alle intuitiv lösbaren Probleme lösen.
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 operiert nur mit Nullen und Einsen (aber hier nicht unendlich vielen), und schafft es, damit die komplexesten Dinge zu berechnen.
Diese Seite ist ein Artikel über Turingmaschine. Seite Versuche, zum von von Beschreibung über bereitzustellen Turingmaschine. Sie konnten Tatsachen über auch finden Turingmaschine. Erklärung von Turingmaschine.Beispiel
Die folgende deterministische 1-Band-Turingmaschine erwartet eine Folge von Einsen als Eingabe auf dem Band. Sie verdoppelt die Anzahl der Einsen wobei ein Leersymbol in der Mitte stehen bleibt. Aus "111" wird beispielsweise die Zeichenfolge "1110111".
Der Schreib-/Lesekopf befindet sich initial auf der ersten Eins. Der Anfangszustand ist , der Endzustand .
Die Berechnung beginnt im Anfangszustand . Hier wird die erste Eins durch eine Null ersetzt, der Schreib-/Lesekopf bewegt sich nach rechts und neuer Zustand wird . Der Kopf wandert nun solange nach rechts, bis eine Null gelesen wird. Danach gelangt die Turingmaschine in den Zustand und ĂŒberliest alle weiteren Einsen, bis sie erneut eine Null findet. Diese wird dann durch eine Eins ersetzt. Im Zustand bewegt sich der Kopf zurĂŒck, ĂŒberliest wieder alle Einsen, bis er auf eine Null trifft, Zustandswechsel auf . Der Kopf bewegt sich nun solange nach links, bis die ursprĂŒnglich in Zustand geschriebene Null gefunden wird. Diese wird wieder durch eine Eins ersetzt, der Kopf bewegt sich ein Feld nach rechts und die Turingmaschine gelangt wieder in den Zustand . Hier beginnt ein neuer Rechenzyklus.
*
*
*
*
alter geles. schr. neuer Kopf- alter geles. schr. neuer Kopf-
Zust. Symbol Symbol Zust. richtg. Zust. Symbol Symbol Zust. richtg.
------------------------------------ ------------------------------------
s1 1 -> 0 s2 R s4 1 -> 1 s4 L
s1 0 -> 0 s6 0 s4 0 -> 0 s5 L
s2 1 -> 1 s2 R s5 1 -> 1 s5 L
s2 0 -> 0 s3 R s5 0 -> 1 s1 R
s3 0 -> 1 s4 L
s3 1 -> 1 s3 R
Wird im Zustand eine Null gelesen, so gelangt die Turingmaschine in den Endzustand , woraufhin die Berechnung beendet wird.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. (Das analoge Konzept bei Programmiersprachen ist der Interpreter). 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 (Von-Neumann-Architektur).Beziehung Turingmaschine - Formale Sprache
Akzeptierte Sprache
Entscheidbare Sprache
Allgemeines
Erweiterung
ErklĂ€rung fĂŒr Nicht-Mathematiker/Informatiker
Siehe auch
Literatur
Weblinks