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.