von A. Turing 1936 eingeführtes Modell eines abstrakten Rechenautomaten, das „berechnungsuniversell“ ist.

Formal ist eine (deterministische 1-Band-1-Kopf-) Turing-Maschine ein Tupel (∑, A, Q, δ, q₀, F), wobei ∑ ⊇ A ∪ {b} das (endliche) Bandalphabet, A das Eingabealphabet, b ∉ A ein spezielles Symbol (Leerzeichen, „blank“), Q eine endliche Zustandsmenge, q₀ ∈ Q der Anfangszustand, F ⊆ Q die Menge der Endzustände, sowie \begin{eqnarray}\delta :Q\times {\rm{\Sigma}}\to Q\times {\rm{\Sigma}}\times \{l,r\})\end{eqnarray} die Zustandsübergangsfunktion ist.

Eine Turing-Maschine arbeitet auf einem beidseitig unendlichen Band mit (abzählbar) unendlich vielen, nebeneinanderliegenden Feldern, die mit jeweils einem Zeichen beschriftet sind, und zwar fast alle Felder mit dem Zeichen δ (d. h., sie sind „leer“). Die Maschine arbeitet auf diesem Band, auf dem immer genau ein Feld markiert ist, schrittweise gemäß der Zustandsübergangsfunktion S, d. h., sie befindet sich vor und nach jedem ausgeführten Schritt in genau einem der Zustände q ∈ Q, und liest das auf dem markierten Feld befindliche Zeichen a ∈ ∑. Bei jedem Schritt geht sie in einen (ggf. neuen) Zustand q′ ∈ Q über und führt gemäß δ genau eine von drei möglichen Aktionen aus:

Ist δ(q, a) = (q′, a′, x), so vertauscht sie das aktuelle Zeichen a auf dem markierten Feld gegen das (evtl. andere) Zeichen a′ ∈ ∑. Danach wandert die Markierung einen Schritt nach rechts (sofern x = r) bzw. nach links (sofern x = l), und der Zustand geht von q nach q′ über. Die Maschine stoppt genau dann, wenn sie in einen Endzustand q ∈ F gerät, oder wenn δ(q, a) nicht definiert ist.

Eine Turing-Maschine kann in folgender Weise eine arithmetische Funktion f berechnen: Mit Hilfe des Alphabetes A werden natürliche Zahlen z. B. binär oder dezimal dargestellt. Zu Beginn der Berechnung stehen die Argumente des zu berechnenden Funktionswertes in dieser Weise codiert unmittelbar rechts von der Markierung auf dem Band; bei mehreren Argumenten jeweils durch ein „blank“ getrennt. Alle anderen Felder sind mit „blanks“ beschriftet. Außerdem befindet sich die Maschine im Anfangszustand q₀. Nun führt sie die Berechnung in obiger Weise nach der vorgegebenen Zustandsübergangsfunktion durch. Stoppt die Maschine nach endlich vielen Schritten und befindet sich dann auf dem Band unmittelbar rechts von der Markierung ein zulässiger Funktionswert, wobei alle anderen Felder leer sind, so wurde die Rechnung erfolgreich zu Ende geführt. In allen anderen Fällen bleibt der Funktionswert undefiniert (partielle Funktion).

Man nennt eine auf diese Weise von einer Turing-Maschine berechenbare arithmetische Funktion kurz eine (Turing-)berechenbare Funktion. Dieser Begriff ist unabhängig von dem zugrundegelegten Formalismus. Insbesondere ist es für den Berechnungsbegriff unerheblich, ob man eine Turing-Maschine mit einem oder mehreren (oder mehrdimensionalen) Bändern oder separatem Eingabe- und Ausgabeband verwendet, oder ein oder mehrere (oder voneinander getrennte) Schreib- und Leseköpfe zuläßt.

Ein wichtiges unentscheidbares Problem (Entscheidbarkeit) ist das Halteproblem für Turing-Maschinen.

Die Turing-Maschine ist „berechnungsuniversell“, da sich eine universelle Turing-Maschine angeben läßt, die gesteuert über einen Teil der Eingabe jede beliebige berechenbare Funktion realisieren kann.

In der Theorie der formalen Sprachen spielen Turing-Maschinen insofern eine wesentliche Rolle, als die Klasse der von einer beliebigen Turing- Maschine erkennbaren Sprachen mit der Klasse der von einer allgemeinen Grammatik erzeugbaren Sprachen zusammenfällt. Die Typ 0-Sprachen stimmen daher mit den rekursiv aufzählbaren Sprachen überein.