Eine Turing-Maschine ist ein theoretisches Modell, das von Alan Turing im Jahr 1936 entwickelt wurde. Sie besteht aus einem unendlichen Band, das in Felder unterteilt ist, auf denen Symbole aus einem bestimmten Alphabet geschrieben werden können. Der Band fungiert als Speicher, und jedes Feld kann entweder leer sein oder ein Symbol wie beispielsweise eine „1“ oder „0“ enthalten. Die Turing-Maschine hat außerdem einen Schreib-Lese-Kopf, der sich über das Band bewegen kann, um Symbole zu lesen, zu schreiben oder zu verändern.

Der Schreib-Lese-Kopf liest ein Symbol und führt eine Aktion basierend auf dem aktuellen Zustand der Maschine aus. Die Maschine ist immer in einem bestimmten Zustand, und für jeden Zustand gibt es eine Übergangsfunktion, die angibt, was passieren soll, wenn ein bestimmtes Symbol vom Schreib-Lese-Kopf gelesen wird. Diese Übergangsfunktion entscheidet, welches Symbol geschrieben wird, in welchen Zustand die Maschine übergeht und in welche Richtung sich der Schreib-Lese-Kopf bewegen soll (nach links oder rechts).

Die Turing-Maschine arbeitet Schritt für Schritt, indem sie zunächst den Zustand und das gelesene Symbol berücksichtigt und dann entsprechend der Übergangsfunktion eine Aktion ausführt. Diese Aktionen wiederholen sich, bis die Maschine zum stillstand kommt, der anzeigt, dass die Berechnung beendet ist. In diesem Zustand bleibt die Maschine stehen. Zudem ist möglich, dass die Maschine niemals zum Stillstand kommt.

Das Besondere an der Turing-Maschine ist, dass sie ein theoretisches Modell für alle berechenbaren Prozesse bietet. Sie zeigt, dass alles, was von einer Turing-Maschine berechnet werden kann, als algorithmisch lösbar gilt. Aber auch, dass es Probleme gibt, die von keiner Turing-Maschine gelöst werden können.

Insgesamt ist die Turing-Maschine ein fundamentales Konzept der Informatik, weil sie die Grenzen des Berechnens und die Prinzipien der Algorithmenformulierung in ihrer einfachsten und abstraktesten Form widerspiegelt. Sie hilft zu verstehen, was überhaupt als "berechenbar" gilt und was nicht.

• der endlichen Zustandsmenge S,
• dem endlichen Eingabealphabet Σ,
• dem Bandalphabet П mit П ⊃ Σ,
• der Zustandsübergangsfunktion δ : S × П → S × П × {←, →},
• dem Startzustand s₀,
• dem Blank-Symbol ☐ ∈ П ∖ Σ,
• der Menge der Endzustände Ε ⊆ S.

Hoffmann, D. W. (2022). Theoretische Informatik (5., aktualisierte Auflage). Carl Hanser Verlag München.

Auf dieser Seite steht dir ein Simulator zur Verfügung, mit dem du die Funktionsweise einer Turing-Maschine auf einfache und intuitive Weise nachvollziehen können.

Bevor der Simulator gestartet werden kann, müssen die folgenden Felder ausgefüllt werden:

Gieb hier das Anfangswort ein, das zu Beginn auf dem Band der Turing-Maschine steht.

Trage hier den Zustand ein, in dem die Maschine zu Beginn starten soll.

Definiere die Zustände, die ein erfolgreiches Ende der Berechnung anzeigen.

Hier werden die Übergangsfunktionen der Turing-Maschine festgelegt.

Das Format lautet:

[Aktueller Zustand] [Aktuelles Zeichen] [->] [Neuer Zustand] [Neues Zeichen] [Bewegungsrichtung L/R/N]

L = Linksbewegung, R = Rechtsbewegung, N = Neutralbewegung

Beispiel: [q0] [1] [->] [q1] [0] [R]

Der Simulator wird über sechs Schaltflächen gesteuert:

Setzt die Maschine in ihren ursprünglichen Zustand zurück.

Überträgt das Startband in den internen Speicher und initialisiert die Turing-Maschine.

Pausiert die Ausführung der aktuellen Berechnung.

Führt einen einzelnen Berechnungsschritt gemäß den Übergangsregeln aus.

Lässt das gesamte Programm ablaufen, wobei die Ausführungsgeschwindigkeit wählbar ist.

Lädt eine fertige Konfiguration und initialisiert den Simulator mit einem vorgegebenen Programm.