Turingmaschine

Eine Turingmaschine (Universeller Automat) ist ein von Alan M. Turing (1912-1954) entworfenes (und nach ihm benanntes) Gedankenmodell einer universellen Rechenmaschine mit einem unendlich grossen Speicher.

Kommentare

Die Steuereinheit der Turingmaschine besteht wie bei den Kellerautomaten aus endlich vielen Zuständen. Der Kellerspeicher wird ersetzt durch ein beidseitig unbegrenztes Arbeitsband, welches als Eingabe-, Ausgabe- und Speichermedium benutzt wird. Das Arbeitsband ist unterteilt in Felder, die jeweils ein Zeichen eines Bandalphabets aufnehmen können. Der Lese-Schreib-Kopf (LS-Kopf) kann sich beliebig über das Band bewegen und ein Feld lesen oder neu beschreiben. Arbeitsweise der Turing-Maschine: ein Symbol auf dem Arbeitsfeld wird gelesen, abhängig vom gelesenen Symbol und dem aktuellen Zustand schreibt der LS-Kopf ein Symbol auf das Arbeitsfeld, läuft entweder ein Feld nach links oder rechts oder verharrt auf dem Feld, und die Maschine bleibt in demselben Zustand oder geht in einen anderen über.

Hinsichtlich der Äquivalenz zwischen Automaten und Grammatiken von natürlichen Sprachen entspricht die Turing-Maschine den allgemeinen Sprachen (Typ 0 der Chomsky-Hierarchie) und ist somit die mächtigste Maschine aller Automaten, da sie eine rekursiv aufzählbare Menge von Ketten (Sätzen) zu erzeugen vermag.

REF	This article has no reference(s) or source(s). Please remove this block only when the problem is solved.