Turing-Maschine, hypothetisches Rechengerät, das 1936 von dem englischen Mathematiker und Logiker Alan M. Turing vorgestellt wurde. Turing konzipierte die Maschine ursprünglich als mathematisches Werkzeug, das unfehlbar unentscheidbare Sätze erkennen kann – also solche mathematischen Aussagen, die innerhalb eines gegebenen formalen Axiomensystems weder als wahr noch als falsch bewiesen werden können. (Der Mathematiker Kurt Gödel hatte gezeigt, dass solche unentscheidbaren Sätze in jedem System existieren, das mächtig genug ist, um Arithmetik zu enthalten.) Turing bewies stattdessen, dass es niemals eine universelle algorithmische Methode geben kann, um zu bestimmen, ob ein Satz unentscheidbar ist.
Die Turing-Maschine ist keine Maschine im gewöhnlichen Sinne, sondern ein idealisiertes mathematisches Modell, das die logische Struktur eines beliebigen Rechengeräts auf das Wesentliche reduziert. Nach Turings Vorstellung führt die Maschine ihre Funktionen in einer Folge von diskreten Schritten aus und nimmt zu jedem Zeitpunkt nur einen von einer endlichen Liste interner Zustände an. Die Maschine selbst besteht aus einem unendlich dehnbaren Band, einem Bandkopf, der in der Lage ist, verschiedene Operationen auf dem Band auszuführen, und einem modifizierbaren Steuermechanismus im Kopf, der Anweisungen aus einem endlichen Satz von Instruktionen speichern kann. Das Band ist in Quadrate unterteilt, von denen jedes entweder leer ist oder eines von einer endlichen Anzahl von Symbolen aufgedruckt hat. Der Bandkopf hat die Fähigkeit, jedes einzelne Quadrat anzufahren, zu lesen, zu schreiben und zu löschen und kann auch jederzeit in einen anderen internen Zustand wechseln. Jede solche Handlung wird durch den internen Zustand der Maschine und den Zustand des gescannten Quadrats zu einem bestimmten Zeitpunkt bestimmt. Die Ausgabe der Maschine – d. h. die Lösung einer mathematischen Frage – kann aus dem System gelesen werden, sobald die Maschine angehalten hat. (Im Fall von Gödels unentscheidbaren Sätzen würde die Maschine jedoch niemals anhalten, was als „Halteproblem“ bekannt wurde.)
Durch die Einbeziehung aller wesentlichen Merkmale der Informationsverarbeitung wurde die Turing-Maschine zur Grundlage für alle nachfolgenden Digitalcomputer, die das Grundschema der Maschine mit einem Ein-/Ausgabegerät (Band und Lesegerät), einem Speicher (Speicher des Steuermechanismus) und einer Zentraleinheit (Steuermechanismus) teilen.