Turingmaschine definition and meaning

Die Turingmaschine ist ein mathematisches Konzept zur formalen Definition eines Begriffes der Berechenbarkeit. Man spricht von einer Turingmaschine als einem mathematischen Objekt, das eine Vorschrift (Algorithmus) zur Berechnung einer Funktion darstellt. Die Turingmaschine gehört zu den grundlegenden Konzepten der theoretischen Informatik und wird heute zu einer allgemein anerkannten Definition der Berechenbarkeit verwendet: Eine Funktion wird berechenbar genannt, wenn eine Turingmaschine existiert, die diese berechnet.

Der Mathematiker Alan Turing stellte die Turingmaschine 1936 im Rahmen des von David Hilbert im Jahr 1920 formulierten Hilbertprogramms speziell zur Lösung des so genannten Entscheidungsproblems in der Schrift On Computable Numbers, with an Application to the Entscheidungsproblem vor.

Informelle Beschreibung

Ein-Band-Turingmaschine

Animierte Turingmaschine

Die Turingmaschine besteht aus

einem unendlich langen Speicherband mit unendlich vielen sequentiell angeordneten Feldern. In jedem dieser Felder ist zu jedem Zeitpunkt genau ein Zeichen gespeichert. Dabei ist als Zeichen ein Blanksymbol zugelassen, was so viel bedeutet wie „leeres Feld“. Das Blanksymbol gehört nicht zu der Menge der Eingabezeichen.
einem programmgesteuerten Lese- und Schreibkopf, der sich auf dem Speicherband feldweise bewegen und die Zeichen verändern kann.

Die Turingmaschine modifiziert die Eingabe auf dem Band nach einem gegebenen Programm. Die Startposition der Turingmaschine ist am Anfang des Eingabeworts, d. h. an der Position des ersten Eingabezeichens.

Mit jedem Schritt liest der Lese-Schreib-Kopf das aktuelle Zeichen, überschreibt dieses mit einem anderen (oder dem gleichen) Zeichen und bewegt sich dann ein Feld nach links oder rechts oder bleibt stehen. Welches Zeichen geschrieben wird und welche Bewegung ausgeführt wird, hängt von dem an der aktuellen Position vorgefundenen Zeichen sowie dem Zustand ab, in dem sich die Turingmaschine gerade befindet. Dies wird durch eine zu der Turingmaschine gehörende Funktion definiert. Zu Beginn befindet sich die Turingmaschine in einem vorgegebenen Startzustand und geht bei jedem Schritt in einen neuen Zustand über. Die Anzahl Zustände, in denen sich die Turingmaschine befinden kann, ist endlich. Ein Zustand kann mehrere Male durchlaufen werden, er sagt nichts über die auf dem Band vorliegenden Zeichen aus.

Man kann bestimmte Zustände der Turingmaschine als Endzustände definieren. Sobald die Maschine in einen dieser Zustände kommt, bleibt sie stehen, unabhängig davon, welches Zeichen sich an der aktuellen Position befindet. Es gibt Eingaben, für die eine Turingmaschine niemals stoppt.

Die Turingmaschine wird (wie viele andere Automaten) auch für Entscheidungsprobleme eingesetzt, also für Fragen, die mit „ja“ oder „nein“ zu beantworten sind. Hierbei werden zum Beispiel bestimmte Zustände als „akzeptierend“ und andere als „nicht akzeptierend“ definiert, die Eingabe wird genau dann akzeptiert, wenn die Turingmaschine in einem akzeptierenden Endzustand endet. Zu jedem Problem lässt sich ein Entscheidungsproblem formulieren, indem man fragt, ob ein bestimmter Wert eine Lösung für ein konkretes Problem ist.

Bedeutung

Das von David Hilbert aufgestellte Entscheidungsproblem fragt, ob eine Formel der Prädikatenlogik allgemeingültig ist, also ob jede Interpretation einer mathematischen, d. h. formal logischen Aussage wahr ist. Das von ihm vorgeschlagene Hilbertprogramm versuchte, dieses Problem automatisch zu lösen. Die Methode, die für eine prädikatenlogische Formel bestimmt, ob sie allgemeingültig ist, soll also von einer „Maschine” durchgeführt werden können. Vor der Erfindung des Computers bedeutete dies, dass ein Mensch nach festen Regeln – einem Algorithmus – eine Berechnung durchführt.

Turing definierte mit seinem Modell die Begriffe des Algorithmus und der Berechenbarkeit als formale, mathematische Begriffe. Im Allgemeinen wird davon ausgegangen, dass die Turing-Berechenbarkeit das intuitive Verständnis von Berechenbarkeit trifft, diese Aussage ist als Church-Turing-These bekannt. Ihr wohnt eine starke Plausibilität inne, u. a. durch die mathematische Äquivalenz des Begriffs der Turing-Berechenbarkeit mit anderen Berechenbarkeits-Begriffen (wie zum Beispiel der Ausdrückbarkeit im Lambda-Kalkül oder als partiell-rekursive Funktion, sowie die Berechenbarkeit durch Registermaschinen, welche strukturell heute verwendeten Computern nachempfunden sind). Das Besondere an einer Turingmaschine ist dabei ihre strukturelle Einfachheit. Sie benötigt nur drei Operationen (Lesen, Schreiben und Schreib-Lese-Kopf bewegen), um alle Operationen der üblichen Computerprogramme zu simulieren. Im Rahmen der theoretischen Informatik eignet sie sich deshalb besonders gut zum Beweis von Eigenschaften formaler Probleme, wie sie von der Komplexitäts- und Berechenbarkeitstheorie betrachtet werden.

Die Komplexität (etwa Laufzeit- und Speicherkomplexität) von Algorithmen werden in Bezug auf bestimmte Maschinenmodelle definiert. Auf Turingmaschinen ist etwa die asymptotische Anzahl der Zustandsübergänge in Abhängigkeit von der Eingabelänge ein mögliches Laufzeitkomplexitätsmaß eines Algorithmus. Auf anderen Modellen werden oftmals Komplexitätsmaße definiert, die einen wahlfreien Zugriff auf jede Speicherzelle oder die Ausführung arithmetischer Operationen als einzelne Schritte definieren. Diese Maße eignen sich im beschränkten Rahmen (kleiner Datenmengen bzw. kleiner Zahlen) besonders gut, um die Laufzeit vieler Algorithmen auf realen Computern abzuschätzen und sind dem entsprechend oft (insbesondere unspezifiziert) anzutreffen. Auf Grund der sequentiellen Struktur von Turingmaschinen ist daher die Laufzeitkomplexität im Sinne der asymptotischen Anzahl der Zustandsübergänge für viele Algorithmen verglichen mit Definitionen für Registermaschinen höher. Die Komplexitätstheorie befasst sich mit der Frage, für welche Probleme Algorithmen mit welcher Komplexität existieren, etwa in welchen Komplexitätsklassen Probleme liegen bzw. nicht liegen. Sofern es bei der Untersuchung der Laufzeitkomplexität nicht auf Faktoren polynomiell in der Eingabelänge ankommt, sind Turingmaschinen hier recht allgemein einsetzbar, da die Simulation vieler Registermaschinen in vielen Komplexitätsmaßen nur polynomiellen Mehraufwand bedeutet.

Nicht alle mathematischen Funktionen können von einer Turingmaschine berechnet werden, selbst wenn man sich auf wohldefinierte Funktionen mit endlicher Ein- und Ausgabe beschränkt (etwa lassen sich Funktionen zwischen beliebigen reellen Zahlen nicht durch Funktionen mit endlicher Ein- und Ausgabe repräsentieren, da die reellen Zahlen überabzählbar sind, und es gibt formal gesehen Funktionen, die sich überhaupt nicht spezifizieren lassen). So konnte Turing zeigen, dass eine Turingmaschine das Entscheidungsproblem nicht lösen kann, genau wie das Halteproblem.

Ebenfalls unentscheidbar ist nach dem Satz von Rice jedwede nicht-triviale Eigenschaft eines Programms in einer turingmächtigen Programmiersprache. Selbst wenn man sich auf terminierende Turingmaschinen beschränkt, ist es unentscheidbar, ob zwei terminierende Turingmaschinen dieselbe Sprache akzeptieren. Die Berechenbarkeitstheorie beschäftigt sich mit der Frage, welche Probleme von welchen Maschinenmodellen berechenbar bzw. nicht berechenbar sind.

Systeme, Computer bzw. Programmsprachen, die unter der Annahme, dass sie über einen unendlich großen Speicher verfügen können, eine Turingmaschine emulieren können, werden als turingvollständig bezeichnet.

Formale Definition

Formal kann eine deterministische Turingmaschine als 7-Tupel $M=(Q, \Sigma, \Gamma, \delta, q_0, \square, q_f)$ dargestellt werden (siehe auch nichtdeterministische Turingmaschine).

$Q$ ist die endliche Zustandsmenge
$\Sigma$ ist das endliche Eingabealphabet
$\Gamma$ ist das endliche Bandalphabet und es gilt $\Sigma \subset \Gamma$
$\delta\colon (Q \setminus \{q_f\})\times \Gamma \to Q \times \Gamma \times \{L, 0, R\}$ ist die (partielle) Überführungsfunktion
$q_0 \in Q$ ist der Anfangszustand
$\square \in \Gamma\setminus\Sigma$ steht für das leere Feld (Blank)
$q_f \in Q$ ist der akzeptierende Zustand

Konfigurationen

Konfiguration einer Turingmaschine im Zustand $q_1$ . Der Lese-Schreibkopf befindet sich über dem letzten $\square$ -Symbol vor der eigentlichen Eingabe. $\square$ wird hier durch $0$ dargestellt.

Die Konfiguration einer Turingmaschine beschreibt nicht nur den ihr eigenen momentanen Zustand $q \in Q$ , sondern auch die Position des Lese-Schreib-Kopfes und die gerade auf dem Band vorhandenen Symbole.

Die Symbole befinden sich in einem endlichen Bereich des Bandes, der von unendlich vielen leeren Symbolen umgeben ist. Es genügt deshalb, diesen Bereich zu betrachten.

Formal kann eine Konfiguration einer Turingmaschine durch eine Folge $X_1X_2\cdots X_{i-1}qX_iX_{i+1}\cdots X_n$ beschrieben werden.

$X_1$ ist das am weitesten links stehende, nicht-leere Bandsymbol und $X_n$ das am weitesten rechts stehende, nicht-leere Bandsymbol. Bewegt sich der Lese-Schreib-Kopf über den Rand hinaus, sind der Konfiguration noch weitere $\square$ -Symbole hinzuzufügen.

Der Lese-Schreibkopf befindet sich über dem Zeichen $X_i$ , seine Position lässt sich also auch kurz mit $i$ notieren. Diese Position ist dadurch gekennzeichnet, dass $q \in Q$ , der Zustand der Turingmaschine, in der Konfiguration vor dem Symbol $X_i$ steht.

Durch eine Startkonfiguration wird das Eingabewort festgelegt. Eine übliche Startkonfiguration ist $q_0X_1\cdots X_n$ mit Startzustand $q_0$ und Eingabewort $X_1\cdots X_n$ .

Berechnung

Die Überführungsfunktion $\delta$ gibt zu einer Startkonfiguration den Ablauf einer Turingmaschine vor. Sie wechselt in einem Schritt von der aktuellen Konfiguration in die Nachfolgekonfiguration. Ein solcher Schritt von Konfiguration $c_1$ zu Konfiguration $c_2$ kann als $c_1\vdash c_2$ dargestellt werden.

Schreibt die Überführungsfunktion für einen Zustand $q$ und das Eingabesymbol $X_i$ zum Beispiel vor, dass $Y$ geschrieben wird, der Lese-Schreibkopf sich nach links bewegt und der Nachfolgezustand $p$ ist, so bedeutet dies folgenden Schritt: $X_1\cdots X_{i-1}qX_iX_{i+1}\cdots X_n \vdash X_1\cdots pX_{i-1}YX_{i+1}\cdots X_n$ .

Die Berechnung einer Turingmaschine ist eine endliche oder unendliche Folge von Konfigurationsschritten. Eine Turingmaschine akzeptiert ein durch die Startkonfiguration gegebenes Wort, wenn die Berechnung in dieser Startkonfiguration beginnt und in einer Konfiguration endet, in der die Turingmaschine im Zustand $q_f$ ist. Endet die Berechnung in einer anderen Konfiguration, verwirft die Turingmaschine das Eingabewort. Ist die Berechnung der Turingmaschine unendlich, wird das Wort weder akzeptiert noch verworfen.

Intuition

Die Turingmaschine führt eine Berechnung aus, indem sie schrittweise eine Eingabe in eine Ausgabe umwandelt. Ein-, Ausgabe und Zwischenergebnisse werden auf dem unendlich langen Band gespeichert.

Zu Beginn steht ein Wort als Eingabe auf dem Band (pro Bandfeld ein Zeichen des Eingabewortes), der Rest des Bandes besteht aus leeren Feldern $\square$ . Der Lese-Schreib-Kopf steht auf dem ersten Zeichen der Eingabe und die Turingmaschine befindet sich im Startzustand $q_0$ .

Die Überführungsfunktion gibt an, wie die Turingmaschine schrittweise den Bandinhalt liest und beschreibt, ihren Zustand wechselt und die Position des Lese-Schreib-Kopfes ändert. Diese Funktion nimmt als Argument den aktuellen Zustand und das Zeichen, das sich in der aktuellen Konfiguration unter dem Lese-Schreib-Kopf befindet. Als Ergebnis liefert sie dann genau einen Zustand (dieser wird zum Nachfolgezustand der Turingmaschine), ein Zeichen (mit diesem wird der Inhalt des Feldes, auf welches der Lese-Schreib-Kopf weist, überschrieben) und entweder das Symbol L (in diesem Fall bewegt sich der Lese-Schreib-Kopf um ein Feld nach links), R (in diesem Fall bewegt er sich ein Feld nach rechts) oder 0 (dann verharrt er auf demselben Feld). Damit hat die Turingmaschine einen Schritt ihres Arbeitszyklus durchlaufen und steht für einen weiteren bereit.

Da die Überführungsfunktion partiell ist, muss sie nicht für jeden Zustand und jedes Eingabezeichen einen Übergang definieren. Der Endzustand hat beispielsweise für kein Eingabezeichen einen Nachfolgezustand. Erreicht die Turingmaschine den Endzustand $q_f$ , kann die Turingmaschine deshalb keine weiteren Aktionen durchführen, und die Berechnung ist beendet. Die Ausgabe ist dann der Inhalt des Bandes (wobei die Felder, die mit Symbolen aus $\Gamma\setminus\Sigma$ gefüllt sind, insbesondere dem Symbol $\square$ , nicht berücksichtigt werden).

Je nach Bandalphabet können Ein-/Ausgaben und Zwischenspeicherungen unterschiedlich kenntlich gemacht werden.

Beispiel

Die folgende deterministische Ein-Band-Turingmaschine $M$ 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 $s1$ , der Endzustand $s6$ . Die Null steht für das leere Feld und das Band ist bis auf die darauf geschriebenen Einsen mit leeren Feldern gefüllt.

$M = (Q, \Sigma, \Gamma, \delta, s1, 0, F)$

$Q = \{s1, s2, s3, s4, s5, s6\}$
$\Sigma = \{1\}$
$\Gamma = \{1,0\}$
$F = \{s6\}$

Die Überführungsfunktion $\delta$ ist wie folgt definiert:

aktueller Zustand	geles. Symbol		schr. Symbol	neuer Zustand	Kopf- richtung
s1	1	→	0	s2	R
s1	0	→	0	s6	0
s2	1	→	1	s2	R
s2	0	→	0	s3	R
s3	1	→	1	s3	R
s3	0	→	1	s4	L
s4	1	→	1	s4	L
s4	0	→	0	s5	L
s5	1	→	1	s5	L
s5	0	→	1	s1	R

$M$ durchläuft zum Beispiel bei der Eingabe „11“ folgende Zustände, wobei die aktuelle Kopfposition fett gedruckt ist:

Schritt	Zust.	Band
1	s1	11000
2	s2	01000
3	s2	01000
4	s3	01000
5	s4	01010
6	s5	01010
7	s5	01010
8	s1	11010

Schritt	Zust.	Band
9	s2	10010
10	s3	10010
11	s3	10010
12	s4	10011
13	s4	10011
14	s5	10011
15	s1	11011
16	s6	-halt-

Die Berechnung beginnt im Anfangszustand $s1$ . Hier wird die erste Eins durch ein leeres Feld ersetzt, der Schreib-Lese-Kopf bewegt sich nach rechts und neuer Zustand wird $s2$ . Der Kopf wandert nun solange nach rechts, bis ein leeres Feld gelesen wird. Danach gelangt die Turingmaschine in den Zustand $s3$ und überliest alle weiteren Einsen, bis sie erneut ein leeres Feld findet. Dieses wird dann durch eine Eins ersetzt. Im Zustand $s4$ bewegt sich der Kopf zurück, überliest wieder alle Einsen, bis er auf ein leeres Feld trifft, Zustandswechsel auf $s5$ . Der Kopf bewegt sich nun solange nach links, bis das ursprünglich in Zustand $s1$ geschriebene leere Feld gefunden wird. Dieses wird wieder durch eine Eins ersetzt, der Kopf bewegt sich ein Feld nach rechts und die Turingmaschine gelangt wieder in den Zustand $s1$ . Hier beginnt ein neuer Rechenzyklus.
Wird im Zustand $s1$ ein leeres Feld gelesen, so gelangt die Turingmaschine $M$ in den Endzustand $s6$ , woraufhin die Berechnung beendet wird.

Äquivalente Varianten der Turingmaschine

In der Literatur findet man zahlreiche unterschiedliche Definitionen und Varianten der Turingmaschine, die sich jeweils in einigen Details unterscheiden. So variiert etwa das verwendete Bandalphabet, die zusätzlich verwendeten Spezialzeichen, die Definition von Akzeptanz und andere Eigenschaften. Zudem gibt es Erweiterungen mit mehreren Bändern oder zusätzlichen Stapelspeichern, die ebenfalls hinsichtlich der Berechenbarkeit äquivalent zu Turingmaschinen sind. Selbst komplexitätstheoretisch sind die Unterschiede zwischen vielen der Varianten weitgehend zu vernachlässigen. So lässt sich etwa jede f(n)-zeitbeschränkte k-Bandmaschine mit beliebig großem k durch eine nur O(f²(n))-zeitbeschränkte 1-Bandmaschine simulieren. Für die Simulation beliebig vieler Bänder kommt es also zu einem maximal quadratischen Mehraufwand. Insgesamt führen sehr viele Varianten zu nicht mehr als polynomialem Aufwandsunterschieden (wobei Aufwand hier eine beliebige Ressource meint) und sind daher für viele komplexitätstheoretische Untersuchungen vernachlässigbar. Man passt in Abhängigkeit von den Zielen der jeweiligen Analyse das verwendete Modell so an, dass die Analyse möglichst einfach durchgeführt werden kann. Es gibt jedoch auch hinsichtlich der Berechenbarkeit, nicht aber der Komplexität (im Sinne von „bis auf polynomiellen Mehraufwand“) äquivalente Erweiterungen der Turingmaschine, wie zum Beispiel bestimmte Orakel-Turingmaschinen.

Vergessliche Turingmaschine

Eine Turingmaschine wird vergesslich^[1] (oder auch bewegungsuniform^[2]) genannt, falls die Kopfbewegungen nicht vom Inhalt der Eingabe abhängen, sondern nur von der Länge. Jede Turingmaschine kann durch eine vergessliche simuliert werden^[3].

Universelle Turingmaschine

In der obigen Definition ist das Programm fest in die Maschine eingebaut und kann nicht verändert werden. Kodiert man die Beschreibung einer Turingmaschine als hinreichend einfache Zeichenkette, so kann man eine sogenannte universelle Turingmaschine – selbst eine Turingmaschine – konstruieren, welche eine solche Kodierung einer beliebigen 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 zum Beispiel 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).

Formal ist eine universelle Turingmaschine eine Maschine $UTM_\phi$ , die eine Eingabe $w\|x$ liest. Das Wort $w$ ist hierbei eine hinreichend einfache Beschreibung einer Maschine $M_w$ , die zu einer bestimmten Funktion mit Eingabe $x$ die Ausgabe berechnet. $\|$ ist ein Trennzeichen zwischen Programmbeschreibung und Eingabe. $UTM_\phi$ simuliert also das Verhalten von $M_w$ mit Hilfe der Funktionsbeschreibung $w$ und der Eingabe $x$ . Der Index $\phi$ in $UTM_\phi$ zeigt an, dass es nicht nur eine einzige universelle Turingmaschine gibt. So könnten z. B. $UTM_1$ und $UTM_2$ verschiedene Wörter verstehen. Das Wort $w$ muss dabei in einer Sprache codiert sein, die die $UTM_\phi$ versteht.

Bekannte Turingmaschinen

Fleißiger Biber

Als Fleißige Biber (engl. Busy Beaver) werden die deterministischen Turingmaschinen bezeichnet, die bezogen auf alle terminierenden, deterministischen Turingmaschinen mit der selben Anzahl von Zuständen und Symbolen die maximale Anzahl eines bestimmten Symbols auf das Band schreiben und dann anhalten. Es existiert keine berechenbare Funktion, die einer gegebenen Anzahl von Symbolen und Zuständen einen entsprechenden Fleißigen Biber, die Anzahl der von ihm am Ende geschriebenen Symbole (die sogenannte Radó-Funktion) oder die Anzahl der Schritte, die er braucht, um zu terminieren, zuordnet.

Ameise

Chris Langtons Ameise ist eine Turingmaschine mit zweidimensionalem Band und sehr einfachen Regeln, dessen Bandinhalt zunächst (als zweidimensionales Bild) chaotisch aussieht, jedoch nach über 10.000 Schritten eine gewisse sichtbare Struktur herausbildet.

An Turingmaschinen angelehnte Maschinenmodelle

Orakel-Turingmaschine

→ Hauptartikel: Orakel-Turingmaschine

Orakel-Turingmaschinen sind Verallgemeinerungen der Turingmaschine, bei der die Turingmaschine in einem Schritt bestimmte zusätzliche Operationen durchführen kann, etwa die Lösung unentscheidbarer oder nur mit hohem Aufwand entscheidbarer Probleme. Somit erlauben Orakel-Turingmaschinen eine weitere Kategorisierung unentscheidbarer Probleme, siehe hierzu Turinggrad, oder auch die Definition zusätzlicher Komplexitätsklassen.

Probabilistische Turingmaschine

Probabilistische Turingmaschinen erlauben für jeden Zustand und jede Eingabe zwei (oder äquivalent dazu endlich viele) mögliche Übergänge, von denen bei der Ausführung – intuitiv ausgedrückt – einer zufällig ausgewählt wird, und dienen der theoretischen Beschreibung randomisierter Algorithmen.^[4]

Quanten-Turingmaschine

Quanten-Turingmaschinen dienen in der Quanteninformatik als abstrakte Maschinenmodelle zur theoretischen Beschreibung der Möglichkeiten von Quantencomputern. Quantenschaltungen sind in diesem Kontext als anderes verbreitetes Modell zu nennen.

Persistente Turingmaschine

Um interaktive Modelle (im Sinne von „Modellen mit Gedächtnis“) durch eine Turingmaschine darzustellen, ist eine Erweiterung derselben um eben dieses Gedächtnis notwendig.

Laut Definition (Goldin et al., 2003: Turing Machines, Transition Systems and Interaction) ist eine Persistente Turingmaschine (PTM) eine nichtdeterministische 3-Band-Turingmaschine mit einem Eingabe-, einem Arbeits- und einem Ausgabeband. Die Eingabe wird auf dem Arbeitsband verarbeitet und erst nach vollständiger Bearbeitung gelangen die Ergebnisse auf dem Ausgabeband zurück in die „Umwelt“. Danach kann eine erneute Eingabe aus der Umwelt verarbeitet werden. Zwischen zwei Arbeitsschritten bleiben die Inhalte des Arbeitsbandes als „Gedächtnis“ erhalten.

Beziehung zwischen einer Turingmaschine und einer formalen Sprache

Akzeptierte Sprache

Eine Turingmaschine akzeptiert eine Sprache $L$ , wenn sie bei Eingabe eines jeden Wortes $x \in L$ nach endlich vielen Schritten in einen definierten Endzustand übergeht („hält“) und bei Eingabe eines jeden Wortes $x \not\in L$ in einem anderen Zustand oder überhaupt nicht hält.

Eine Sprache $L \subseteq \Sigma^{\star}$ heißt genau dann rekursiv aufzählbar bzw. semientscheidbar (Typ 0 der Chomsky-Hierarchie), wenn es eine Turingmaschine gibt, die $L$ akzeptiert.

Entscheidbare Sprache

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 $L \subseteq \Sigma^{\star}$ heißt rekursiv oder entscheidbar genau dann, wenn es eine Turingmaschine gibt, die L entscheidet.

Literatur

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society. 42, 1936 - 37, S. 230–65, doi:10.1112/plms/s2-42.1.230 (http://plms.oxfordjournals.org/content/s2-42/1/230).
Marvin Minsky: Computation: Finite and Infinite Machines, Englewood Cliffs, N.J.: Prentice-Hall 1967
John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. 2. Auflage. Addison-Wesley, 2000, ISBN 978-0201441246.
Juraj Hromkovič: Theoretische Informatik. Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie. 3. Auflage. Teubner Verlag, Wiesbaden 2007, ISBN 978-3-8351-0043-5.
Heinz Lüneburg: Rekursive Funktionen. Springer, Berlin 2002, ISBN 3-540-43094-6.
Oswald Wiener, Manuel Bonik, Robert Hödicke: Eine elementare Einführung in die Theorie der Turing-Maschinen. Springer, Wien 1998, ISBN 3-211-82769-2.
Rolf Herken: The Universal Turing Machine : A Half-Century Survey. Springer, Wien, New York, ISBN 3-211-82637-8.
Sybille Krämer, Symbolische Maschinen. Die Idee der Formalisierung im geschichtlichen Abriß, Darmstadt: Wissenschaftliche Buchgesellschaft 1988
B.A. Trachtenbrot: Algorithmen und Rechenautomaten, Berlin: VEB Deutscher Verlag der Wissenschaften 1977
Charles Petzold, The Annotated Turing, John Wiley & Sons, Inc., ISBN 0-470-22905-5

Weblinks

Commons: Turing Machine – Album mit Bildern und/oder Videos und Audiodateien

Eintrag In: Edward N. Zalta (Hrsg.): Stanford Encyclopedia of Philosophy
Die Turing-Maschine
Varianten universeller Turingmaschinen
A Turing Machine In Conway’s Game of Life
Simulation einer Turingmaschine (Java-Applet)
Einband / Mehrband Turingmaschine Simulation der Grundrechenarten (Javascript)
Webseite über eine physikalische Turing-Maschine inklusive Video – Gebaut von Mike Davey, funktioniert auch so wie Turing es definiert hat
Sumulation einer Einband-Einkopf Turing-Maschine in Javascript

Einzelnachweise

↑ auf englisch: oblivious, http://www.cs.princeton.edu/theory/complexity/, Abschnitt 2.3.4
↑ Karl Rüdiger Reischuk: Komplexitätstheorie. 2 Auflage. Band I: Grundlagen, Teubner, 1999, ISBN 978-3519122753. Seite 103
↑ http://www.cs.princeton.edu/theory/complexity/, Remark 1.10
↑ [1] Eintrag auf der Seite des NIST zur probabilistischen Turingmaschine.

Definition and meaning of Turingmaschine

Definition

Phrases

Turingmaschine

Inhaltsverzeichnis