Kleines Nachschlagewerk Informatik
Turing-Maschinen
Worum geht es?
Bei den linear beschränkten Automaten hatte der Automat zwar wahlfreien Zugriff auf den Speicher, der die Eingabe enthält, aber mehr Speicher wurde ihm nicht zugestanden. Diese Einschränkung soll nun aufgehoben werden.
Die Turingmaschine
Die Turingmaschine ist ein endlicher Automat, der mit einem beliebig großem Speicher ausgestattet ist. Die Eingabe liest er von diesem Speicher. Man kann sogar mehrere Speicherbänder zulassen, das ändert jedoch nichts an der damit verbundenen Leistungsfähigkeit.
Darstellung von Turingmaschinen
Zur Darstellung braucht man wieder einen Automatengraphen, wie er von endlichen und Kellerautomaten bekannt ist. Weiterhin gibt es ein Speicherband, das üblicherweise aus Nullen und Einsen besteht. Die Turingmaschine liest also bitweise.

Genau wie alle anderen Automaten braucht der Graph einen Anfangs- und mindestens einen Endzustand. Bei den Übergängen steht nun, welches Zeichen gelesen, welches geschrieben und wie danach der Lesekopf bewegt wird. Der Lesekopf steht am Anfang meist bei der ersten Eins auf der linken Seite, sofern nichts anderes vereinbart wurde.





Diese Turingmaschine löscht alle Einsen. Liest sie im Zustand q0 eine Eins, so schreibt sie eine Null und geht einen Schritt nach Rechts. Liest sie eine Null, hat sie das Ende erreicht und stoppt.
Beispiel - Addition
Ein weiteres Beispiel zeigt eine einfache Addition. Zwei und drei sollen addiert werden. Die Zwei ist durch zwei Einsen, die Drei durch drei Einsen gegeben. Die Summanden werden durch eine Null getrennt.

Die Addition geschieht wie folgt: Solange eine Eins steht, gehe nach rechts und verändere die Eins nicht. Kommt eine Null, überschreibe sie mit einer Eins. Dann gehe bis zum Ende und nimm die letzte Eins weg. Es bleibt ein Band von fünf Einsen.



Zahlendarstellung
Die Zahlendarstellung im Beispiel der Addition ist nicht ungewöhnlich. Man hat ein Speicherband mit Nullen und Einsen, Trennzeichen gibt es nicht. Für das Binärsystem braucht man eine Rasterung. Somit ist dieses System sehr einfach.

Legt man weiterhin fest, dass die Eins aus zwei Einsen, die Zwei aus drei Einsen besteht, kann man sogar die Null darstellen.

Die Idee "Einsen sind Daten, Nullen sind Trennzeichen" lässt sich natürlich auch auf andere Probleme anwenden.
Computer
Computer sind Turingmaschinen.