Der Anlass für die Turingmaschine war das so genannte Halteproblem, mit welchem sich Alan Turing befasste. Um dieses zu lösen entwarf er eine gedankliche Maschine, mit welcher er einen Beweis liefern konnte. Diese gedankliche Maschine ist als Turingmaschine bekannt. In den allgemeinen Funktions-Komponenten ist eine Turingmaschine mit heutigen Computern zu vergleichen.
Aufbau
Im Grunde genommen ist jede Komponente aus einem modernen Computer auch in der Turingmaschine zu finden. Eine Turingmaschine hat ein Band, auf das es Lesen und schreiben kann. Dieses Band ist unendlich groß in jede Richtung und besteht aus einzelnen Zellen. In jeder Zelle kann ein bestimmter Wert drinnen stehen. Welche Werte alle drinnen stehen können, wird im Eingabealphabet festgelegt. Ein unbeschriebenes Feld wird, wie beim Kellerautomaten durch ein Leerzeichen, wie in unserem Fall dem | dargestellt. Dies ist heute als Speicher, wie RAM oder Festplatte zu finden.
Ebenfalls hat die Maschine einen Lesekopf, welcher sich auf dem Band hin-und-her bewegen kann. Dabei kann er den Wert auf dem Band einlesen und einen neuen Wert schreiben.
Gesteuert wird der Lese- und Schreibkopf von der Steuereinheit, welche ein vorher bestimmtes Programm ausführt. So ein Programm wird wieder als Folge von Zuständen mit Übergängen, also als Automat dargestellt. Dabei kann der Automat bei jedem Übergang ein Zeichen einlesen, ein (neues) Zeichen schreiben und dann den Kopf nach Links, Rechts, oder gar nicht bewegen.
Im Unterschied zum Kellerautomaten kann eine Turingmaschine auch Kontextfreie Grammatiken akzeptieren, da diese auf das gesammte Eingabewort zugreifen kann und nicht nur auf das oberste Kellersymbol beschrängt ist.
Beispielprogram
Den Automaten kann man auch wieder als Tabelle von Übergängen darstellen:
| Zeichen Zustand |
| | 1 | + | = |
|---|---|---|---|---|
| q0 | - | 1 R q0 | 1 R q0 | | L q1 |
| q1 | - | | N q2 | - | - |
| q2 | - | - | - | - |
Syntax
Ein Übergang ist durch folgende Syntax definiert:
ZuLesendesZeichen;ZuSchreibendesZeichen,Kopfbewegung