Turingmaschinen

Turingmaschinen spielen in der theoretischen Informatik eine große Rolle. Es handelt sich um einfache mathematische Modelle für eine Maschine oder einen Automaten. Es kann jede, im intuitiven Sinn berechenbare Funktion mit einer Turingmaschine berechnet werden. "Im intuitiven Sinn" ist natürlich nicht widerlegt, allerdings wurde in all den Jahren nicht das Gegenteil bewiesen. Deshalb gibt es auch kein leistungsfähigeres Berechnungsmodell.

Eine b-Band Turingmaschine M kann als 5-Tupel definiert werden:
M = (Z,A, δ,z₀,E)
Z ist dabei eine endliche Zustandsmenge
A bezeichnet das Bandalphabet
δ bezeichnet eine Übergangsfunktion
z₀ ist der Startzustand
z_e ist der Endzustand
E bezeichnet die Menge von Endzuständen

Turingmaschinen unterscheiden sich in der Anzahl Ihrer Bänder. 1-Band-Turingmaschinen können Zeichen aus einem endlichen Alphabet lediglich auf 1 unendlich langes Speicherband legen. Mehrband-Turingmaschinen haben allerdings mehrere unendlich langen Bänder, die jeweils einen eigenen Lese- und Schreibkopf besitzen.
Die Menge der berechenbaren Funktionen ist allerdings bei 1-Band und Mehrband-Turingmaschinen identisch. Lediglich die Zeit zur Berechnung der Funktionen kann bei Mehrband-Turingmaschinen schneller sein.

Leere Felder des Bandes werden mit einem Initialisierungszeichen gefüllt. Zudem besitzt die Maschine einen Lesekopf, der genau ein Feld lesen und schreiben kann. Der Lesekopf bzw. der Zeiger kann auf dem Band nach links und nach rechts bewegt werden. Somit hat man beliebigen Zugriff auf jedes Zeichen, das sich auf dem Band befindet. Endliche Automaten oder Kellerautomaten können im Gegensatz nur ein Eingabewort von links nach rechts durchlaufen, um zu entscheiden ob ein Wort zu einer Sprache gehört.

Eine Turingmaschine arbeitet in Abhängigkeit vom aktuellen Zustand und durch die Köpfe gelesenen Bandsymbole. Gleichzeitig nimmt sie einen neuen Zustand an, die Bandfelder werden ggf. neu beschrieben und jeder der Köpfe wird um maximal ein Feld bewegt. Die sogenannte Zustands-(Übergangsfunktion) legt das Verhalten einer Turingmaschine in einem Arbeitsschritt fest.

Eine b-Band Turingmaschine besteht aus b linearen, beidseitig unendlichen Bändern. Die Felder des Bandes können mit jedem beliebigen Zeichen aus einem endlichen Alphabet A beschriftet werden. Ein Alphabet sollte zumindest die Zeichen 0, 1, # und das Initialisierungszeichen ☒ beinhalten. Um Felder auf einem Band bearbeiten zu können, weißt jedes Band einen Kopf auf, der dafür zuständig ist genau ein Feld zu lesen oder zu schreiben. Des Weiteren besteht eine Turingmaschine aus einer Steuereinheit, welche Zustände aus einer endlichen Zustandsmenge Z annehmen kann. Hierzu gehört unter anderem der Startzustand und eine Menge von Endzuständen.