Turing-Maschine ist ein Begriff aus der Informatik. Eine Turingmaschine ist eher ein System von Regeln, Zuständen und Übergängen als eine reale Maschine. Sie wurde erstmals 1936 von dem englischen Mathematiker und Informatiker Alan Turing beschrieben. Es gibt zwei Zwecke für eine Turingmaschine: formale Sprachen zu entscheiden und mathematische Funktionen zu lösen. Turingmaschinen sind eines der wichtigsten formalen Modelle im Studium der Informatik.
Turingmaschine
Allgemeine Grundlagen
Eine Turing-Maschine besteht aus den folgenden Komponenten (vereinfacht):
- Ein begrenzter Satz von Zuständen (wobei ein Zustand als Startzustand markiert ist; während des Betriebs hat eine Turingmaschine immer einen aktuellen Zustand)
- Ein unendliches Band mit Speicherzellen und einem Lese-/Schreibgerät, das sich auf dem Band bewegen kann
- Eine Definition einer sogenannten Übergangsfunktion
Außerdem muss ein Arbeitsalphabet (Zeichensatz) definiert werden.
Wenn eine Turing-Maschine gestartet wird, muss auf dem unendlichen Band der Maschine ein Wort (aus dem Arbeitsalphabet) vorhanden sein. Das Lese-/Schreibgerät auf dem ersten Zeichen liest nun das erste Zeichen und je nach aktuellem Zustand der Turingmaschine überschreibt das Lese-/Schreibgerät das Zeichen mit einem neuen oder verschiebt eine Zelle nach links oder rechts. Darüber hinaus kann der aktuelle Zustand der Maschine umgeschaltet werden.
Turing-Maschinen, die über Sprachen entscheiden
Für die Entscheidbarkeitstheorie sagt man, dass eine Turingmaschine eine Sprache entscheidet, wenn sie immer in der Lage ist, zu bestimmen, ob ein bestimmtes Wort in einer bestimmten Sprache enthalten ist oder nicht. Daher hat die Maschine normalerweise zwei spezielle Zustände, die als Annehmen und Ablehnen gekennzeichnet sind. Nach einer Weile wird einer der beiden Zustände erreicht (abhängig vom Eingabewort) und die Maschine wird angehalten. Wenn nur einer der beiden Zustände jemals erreicht wird, soll die Turingmaschine eine Sprache halb entscheiden.
Turingmaschinen, die Funktionen berechnen
Wenn eine Turing-Maschine für die Berechnung von Funktionen verwendet wird, hat sie nur einen Endzustand. Wenn die Maschine in diesen Zustand kommt, wird sie angehalten und das Ergebnis der Funktion (abhängig von der Eingabe) kann auf dem Band gefunden werden.
Auswirkungen von Turingmaschinen
Turingmaschinen wurden nicht erfunden, um in der Realität gebaut zu werden, aber sie sind sehr wichtig für die theoretische Informatik, da sie eines der einfachsten Modelle für Computer sind. Die Church-Turing-These besagt, dass alle Computer nur so leistungsfähig sind wie Turingmaschinen. Damit lässt sich beweisen, ob ein Problem mit einem Computer lösbar ist oder nicht.
Variationen
- Eine Turing-Maschine kann aus mehreren Endlosbändern (und mehreren Lese-/Schreibgeräten) bestehen. Es ist jedoch erwiesen, dass solche Maschinen nur so leistungsfähig sind wie Einzelbandmaschinen. Maschinen mit mehreren Bändern sind nützlich, wenn es um komplexere Probleme geht.
- Wenn eine Turing-Maschine eine nichtdeterministische Übergangsfunktion hat, kann es beim Lesen eines Zeichens mehrere Übergänge von einem Zustand in viele andere geben. Auch dies erhöht nicht die Leistungsfähigkeit von Turingmaschinen. Allerdings können nichtdeterministische Turingmaschinen (wie sie dann genannt werden) die Rechenzeit möglicherweise stark verringern. Diese Frage wird in der P versus NP-Diskussion behandelt und ist noch nicht gelöst. Die meisten Wissenschaftler gehen jedoch davon aus, dass nichtdeterministische Maschinen bei bestimmten Problemen wesentlich schneller arbeiten können.
- Eine universelle Turingmaschine ist eine Variante, die mit einer Eingabe eine Turingmaschine simulieren kann.