Turing-Maschine

eine von dem britischen Mathematiker Alan Mathison Turing (1912-1954) zur Lösung des von Gödel formulierten Vollständigkeitsproblems erdachte Maschine, bestehend aus einem programmgesteuerten Lese- und Schreibkopf, der auf einem endlosen Papierband ein Feld nach links oder rechts rücken, ein Zeichen lesen, schreiben oder löschen und schließlich stehen bleiben kann. Turing zeigte, dass diese Maschine jedes algorithmisierbare Problem lösen kann. Sie wird als universale Turing-Maschine bezeichnet und liegt fast allen heutigen Computerarchitekturen zugrunde.