Turingmaschine Grundlagen
Die Turingmaschine geht auf den britischen Mathematiker Alan Turing zurück und ist ein von ihm entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden.
Eine Turingmaschine zeichnet folgendes aus:
- eine Zustandsmenge Z
- einen Anfangszustand z0 Element von Z
- ein Bandalphabet X
- eine partielle Zustandsüberführungsfunktion f: Z x X -> Z
- eine partielle Ausgabefunktion g: Z x X -> X
- eine partielle Bewegungsfunktion m: Z x X -> {-1,0,1}
Die Bewegungsrichtung der Bewegungsfunktion notiert man oft auch mit L (links) statt -1 und R (rechts) statt 1.
Konkret besteht eine Turingmaschine also aus:
- einem unendlich langen Speicherband mit unendlich vielen sequentiell angeordneten Feldern. Auf jedes Feld kann zu jedem Zeitpunkt genau ein Zeichen gespeichert werden. Ein leeres Feld kann durch ein sogenanntes Banksymbol gekennzeichnet werden.
- einem programmgesteuerten Lese- und Schreibkopf, der sich auf dem Speicherband feldweise bewegen und die Zeichen verändern kann.
Der Ablauf der Turingmaschine ist nun denkbar einfach. Gestartet wird an der Position des ersten Eingabezeichens. Anschließend bewegt sich der Lese-Schreib-Kopf entweder nach links oder rechts und überschreibt das entsprechende Feld mit einem neuen, anderen oder gleichen Zeichen. Eine Funktion definiert dabei, welches Zeichen geschrieben und in welche Richtung sich der Lese-Schreib-Kopf bewegen soll. Eine Turingmaschine geht somit von einem Zustand zu einem anderen über, dabei kann ein Zustand öfters durchlaufen werden.
Zwar gibt es Eingaben, für die eine Turingmaschine niemals stopp, normalerweise möchte man dies aber gerade nicht. Deswegen kann man bestimmte Zustände als Endzustände definieren. Wird dieser Endzustand dann erreicht, bleibt die Maschine stehen.
Eingesetzt werden Turingmaschine z.B. bei sogenannte „Entscheidungsprobleme“, also für Fragen, die mit „ja“ oder „nein“ zu beantworten sind. Das wäre z.B. bei der Prüfung ob das Eingabewort zu einer bestimmten Sprache gehört der Fall.