Turingmaschine


Turingmaschine

Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Theoretischen Informatik.

Das Modell wurde 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” vorgestellt. Alan Turing beabsichtigte, mit der Turingmaschine ein Modell des mathematisch arbeitenden Menschen zu schaffen und damit eine mathematische Definition des Begriffs „Algorithmus“ zu formulieren.

Inhaltsverzeichnis

Bedeutung in der Informatik

Das von David Hilbert aufgestellte Entscheidungsproblem fragt, ob eine Formel der Prädikatenlogik allgemeingültig ist, also ob eine mathematische Aussage gültig ist oder nicht. 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 gelang es mit seinem Modell, die Begriffe des Algorithmus und der Berechenbarkeit mathematisch zu fassen. Die Behauptung, dass eine Funktion genau dann berechenbar ist, wenn es eine Turingmaschine gibt, die sie berechnet, wird Church-Turing-These genannt und gilt gemeinhin als gültig. Ein starker Beleg dafür ist u.a. die mathematische Äquivalenz dieses Modells mit anderen Berechenbarkeits-Modellen (wie zum Beispiel dem Lambda-Kalkül und partiell-rekursive Funktionen) oder heutigen Computern. 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 bei Beweisen von algorithmischen Problemen.

Eine Turingmaschine ist praktisch viel ineffizienter als reale Computer, eine reale Implementierung von Algorithmen ist also nicht sinnvoll, die Simulation anderer Maschinenmodelle benötigt aber nur polynomiellen Mehraufwand im Sinne der O-Notation. In der Komplexitätstheorie wird deshalb üblicherweise die Turingmaschine als Maschinenmodell verwendet, um die Schwierigkeit von algorithmischen Problemen zu vergleichen.

Nicht alle mathematischen Funktionen können von einer Turingmaschine berechnet werden. So konnte Turing zeigen, dass eine Turingmaschine das Entscheidungsproblem nicht lösen kann, genau wie das Halteproblem. Auf Basis der Church-Turing-These gilt dies auch für alle anderen Maschinenmodelle. Ebenfalls unentscheidbar ist nach dem Satz von Rice jedwede nicht-triviale Eigenschaft eines Programms in einer turingmächtigen Programmiersprache. Die Berechenbarkeitstheorie beschäftigt sich mit der Frage, welche Probleme prinzipiell von Maschinen gelöst werden können.

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 turingmächtig bezeichnet.

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. Man darf sich das unendlich lange Band auch als ein endliches vorstellen, es muss jedoch lang genug sein, um die aktuelle Berechnung ungehindert ausführen zu können, d. h. der Lese- und Schreibkopf darf nicht an das Ende stoßen.
  • 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. 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 zwei Zeichen vereinbart, wobei das eine als „ja“ und das andere als „nein“ interpretiert wird. Nach dem Anhalten der Turingmaschine liegt die Antwort als eines der beiden Zeichen auf dem Ausgabeband vor. 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.

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
  • Σ ist das Eingabealphabet
  • Γ 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 q1. 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.

X1 ist das am weitesten links stehende, nicht-leere Bandsymbol und Xn 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 Xi, 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 Xi steht.

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

Berechnung

Die Überführungsfunktion δ 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 c1 zu Konfiguration c2 kann als c_1\vdash c_2 dargestellt werden.

Schreibt die Überführungsfunktion für einen Zustand q und das Eingabesymbol Xi 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 qf 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 q0.

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 qf, 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,Σ,Γ,δ,s1,0,F)

  • Q = {s1,s2,s3,s4,s5,s6}
  • Σ = {1}
  • Γ = {1,0}
  • F = {s6}

Die Überführungsfunktion δ 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.

Variationen des Turingmaschinen-Modells

Überblick über Variationsmöglichkeiten

In der Literatur findet man zahlreiche unterschiedliche Definitionen der Turingmaschine, die sich jeweils in einigen Details unterscheiden. So variiert etwa die Anzahl der Bänder, das verwendete Bandalphabet, die zusätzlich verwendeten Spezialzeichen und andere Eigenschaften. Die Vielfalt ist theoretisch durch die These von Church gerechtfertigt, welche im Hinblick auf die Berechenbarkeit die Äquivalenz aller universellen Maschinenmodelle postuliert. Selbst komplexitätstheoretisch sind die Unterschiede zwischen verschiedenen Definitionen 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 alle Arten von Variationen zu nicht mehr als polynomialen 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. Folgende Beispiele zeigen Anwendungen und Variationen des Turingmaschinen-Modells.

Universelle Turingmaschine

In der obigen Definition ist das Programm fest in die Maschine eingebaut und kann nicht verändert werden. Man kann eine universelle Turingmaschine konstruieren, welche 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 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ϕ, die eine Eingabe w\|x liest. Das Wort w ist hierbei eine beliebige Beschreibung einer Maschine Mw, die zu einer bestimmten Funktion mit Eingabe x die Ausgabe berechnet. \| ist ein Trennzeichen zwischen Programmbeschreibung und Eingabe. UTMϕ simuliert also das Verhalten von Mw mit Hilfe der Funktionsbeschreibung w und der Eingabe x. Der Index ϕ in UTMϕ zeigt an, dass es nicht nur eine einzige universelle Turingmaschine gibt. So könnten z. B. UTM1 und UTM2 verschiedene Wörter verstehen. Das Wort w muss dabei in einer Sprache codiert sein, die die UTMϕ versteht.

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 Input-, einem Arbeits- und einem Output-Band. Der Input wird auf dem Arbeitsband verarbeitet und erst nach vollständiger Bearbeitung gelangen die Ergebnisse auf dem Output-Band zurück in die „Umwelt“. Danach kann ein erneuter Input aus der Umwelt verarbeitet werden. Zwischen zwei Arbeitsschritten bleiben die Inhalte des Arbeitsbandes als „Gedächtnis“ erhalten.

Ameise

Chris Langtons Ameise ist eine Turingmaschine mit zweidimensionalem Band, sehr einfachen Regeln und verblüffenden Ergebnissen.

Fleißiger Biber

Ein beliebtes Problem ist der Fleißige Biber: Man finde die Turingmaschine, die mit einer bestimmten Anzahl von Zuständen die maximale Anzahl eines bestimmten Symbols (meist „1“) auf das Band schreibt und dann anhält (d.h. eine Endlosschleife ist ausgeschlossen).

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].

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 deterministische 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 deterministische Turingmaschine gibt, die L entscheidet.

Literatur

  • Turing, A., On Computable Numbers, With an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, Volume 42, 1936; reprinted in M. David (ed.), The Undecidable, Hewlett, NY: Raven Press, 1965
  • 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

Einzelnachweise

  1. auf englisch: oblivious, http://www.cs.princeton.edu/theory/complexity/, Abschnitt 2.3.4
  2. Karl Rüdiger Reischuk: Komplexitätstheorie. 2 Auflage. Band I: Grundlagen, Teubner, 1999, ISBN 978-3519122753. Seite 103
  3. http://www.cs.princeton.edu/theory/complexity/, Remark 1.10

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Turingmaschine — Tu|ring|ma|schi|ne auch: Tu|ring Ma|schi|ne 〈[tju: ] f. 19〉 theoretisches Modell einer Rechenmaschine mit unendlich großem Speicher, in dem sich diese von ihrer momentanen Position nur um eine Position vor od. zurück bewegen kann [nach dem engl.… …   Universal-Lexikon

  • Turingmaschine — Tu|ring|ma|schi|ne auch: Tu|ring Ma|schi|ne 〈[tju: ] f.; Gen.: , Pl.: n; Math.〉 idealisierte Rechenmaschine mit unendlich großem Speicher [Etym.: nach dem engl. Mathematiker Alan Mathison Turing, 1912 1952] …   Lexikalische Deutsches Wörterbuch

  • Turingmaschine — Tu|ring|ma|schi|ne [ tjuəriŋ...] die; , n <nach dem brit. Mathematiker A. M. Turing, 1912 1954> mathematisches Modell einer Rechenmaschine …   Das große Fremdwörterbuch

  • Turingmaschine mit Zusatzeingabe — Eine Turingmaschine mit Zusatzeingabe ist ein zu Nichtdeterministischen Turingmaschinen äquivalentes Berechnungsmodell der Theoretischen Informatik. Inhaltsverzeichnis 1 Informelle Beschreibung 2 Definition 2.1 Turingmaschine mit Zusatzeingabe …   Deutsch Wikipedia

  • Turingmaschine Typ 2 — Eine Turingmaschine Typ 2 ist eine Erweiterung einer Turingmaschine. Sie entstand aus dem Bestreben heraus, das effektive Rechnen mit reellen Zahlen auf eine ähnlich verlässliche Grundlage zu stellen, wie dies für das Rechnen mit natürlichen… …   Deutsch Wikipedia

  • Universelle Turingmaschine — Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Informatik. Das Modell wurde im Rahmen des von… …   Deutsch Wikipedia

  • Orakel-Turingmaschine — Eine Orakel Turingmaschine ist eine Turingmaschine, die mit einem Orakel verbunden ist. Bildhaft kann man sich ein Orakel als eine black box vorstellen, die von der Turingmaschine befragt werden kann und ein Problem in einem Schritt löst. Der… …   Deutsch Wikipedia

  • Nichtdeterministische Turingmaschine — Eine nichtdeterministische Turingmaschine (NTM, NDTM) in der Theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet. Inhaltsverzeichnis 1 Informelle Beschreibung 2 Formale Definition …   Deutsch Wikipedia

  • Alternierende Turingmaschine — In der theoretischen Informatik ist eine alternierende Turing Maschine (ATM) eine nichtdeterministische Turingmaschine, welche die üblichen Regeln für die Akzeptanz einer Eingabe erweitert. Dabei werden die Zustände der Maschine in existentielle… …   Deutsch Wikipedia

  • Linear beschränkte Turingmaschine — Eine linear beschränkte Turingmaschine (auch LBA = Linear Bounded Automaton) ist eine Turingmaschine, die den Eingabebereich nicht verlässt. Das bedeutet, dass sie nur den Teil des Bandes benutzt, auf dem zu Beginn das Eingabewort steht. Eine LBA …   Deutsch Wikipedia