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.

Formale Definition nach Hoffmann:

Eine (deterministische) Turing-Maschine ist ein 7-Tupel (S, Σ, П, δ, s₀, ◻, Ε).

Sie besteht aus:

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.

Quelle:

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

Turing-Maschinen-Simulator

Band:

🔄 ⏹ ⏭ ▶

Status:

Übergangsregeln (eine pro Zeile):

Startband:

Startzustand:

Endzustände (kommagetrennt):