| Die Turingmaschine
ist ein von dem britischen Mathematiker Alan Turing 1936
entwickeltes mathematisches Konstrukt, um eine Klasse
von berechenbaren Funktionen zu bilden und wurde zur Lösung
des von Kurt Gödel formulierten Vollständigkeitsproblems
erdacht.
Die Turingmaschine besteht aus
- einem unendlich langen Speicherband mit unendlich
vielen Feldern. In jedem dieser Felder kann genau
ein Zeichen gespeichert werden.
- einem Schaltwerk mit endlich vielen Zuständen.
Es steuert das Verhalten der Turingmaschine.
- einem programm-gesteuerten Lese- und Schreibkopf,
der auf dem endlosen Speicherband ein Feld nach links
oder rechts rücken, ein Zeichen lesen, schreiben
oder löschen und stehen bleiben kann.
Turing zeigte, dass diese Maschine jedes algorithmisierbare
(berechenbare) Problem lösen kann.
| 
