Die Turingmaschine: das abstrakte Modell, das Berechnung definiert

Die Turingmaschine gehört zu den wichtigsten Konzepten der theoretischen Informatik. Dennoch ähnelt sie kaum einem modernen Computer: kein Bildschirm, kein Prozessor, keine Tastatur und in ihrem theoretischen Modell nicht einmal eine reale Grenze des Speichers.

Alan Turing entwickelte sie 1936, um eine grundlegendere Frage zu beantworten: Was ist eine Berechnung? Dazu stellte er sich eine bewusst minimale Maschine vor, die Symbole auf einem Band liest und schreibt und dabei präzisen Regeln folgt.

Trotz dieser extremen Einfachheit ist das Modell mächtig genug, um nach dem klassischen Verständnis der Berechenbarkeit jede algorithmisch ausführbare Berechnung darzustellen. Es hilft deshalb nicht nur zu verstehen, was ein Algorithmus ist, sondern auch, was Computer prinzipiell berechnen können - und warum manche Probleme unabhängig von künftiger Rechenleistung unlösbar bleiben.

Warum musste Berechnung überhaupt definiert werden?

Zu Beginn des 20. Jahrhunderts versuchten Mathematiker, die Grundlagen ihrer Disziplin zu formalisieren. David Hilberts Entscheidungsproblem fragte vereinfacht, ob es ein mechanisches Verfahren geben könne, das für jede Aussage eines logischen Systems entscheidet, ob sie beweisbar ist.

Doch was bedeutet „einem mechanischen Verfahren folgen“ genau? 1936 existierten noch keine programmierbaren elektronischen Computer. Daher musste die Idee eines Rechenverfahrens unabhängig von einer realen Maschine mathematisch beschrieben werden. Genau hier setzt Turings Modell an. Mehr zu seinem wissenschaftlichen Weg bietet die Biografie Alan Turings.

Eine bewusst sehr einfache Maschine

Eine klassische Turingmaschine besitzt nur wenige Bestandteile:

• ein in Felder unterteiltes Band;
• ein begrenztes Alphabet von Symbolen;
• einen Lese-Schreib-Kopf;
• eine endliche Menge von Zuständen;
• eine Tabelle von Übergangsregeln.

In jedem Schritt betrachtet die Maschine das Symbol unter ihrem Kopf. Aus diesem Symbol und dem aktuellen Zustand ergibt sich eine Regel: Sie kann ein Symbol schreiben, den Kopf ein Feld nach links oder rechts bewegen, den Zustand wechseln und gegebenenfalls anhalten. Danach beginnt der nächste Schritt.

Aus einer Folge solcher elementaren Operationen können komplexe Berechnungen entstehen.

Das Band: theoretisch unbegrenzter Speicher

Das Band wird als lange Folge von Feldern dargestellt. Jedes Feld kann ein Symbol aus einem festgelegten Alphabet enthalten. Im theoretischen Modell nimmt man an, dass genügend Band zur Verfügung steht, damit der untersuchte Rechenvorgang nicht aus Speichermangel scheitert.

Das bedeutet nicht, dass reale Computer unendlichen Speicher besitzen könnten. Die Annahme trennt zwei Fragen: Ist ein Problem prinzipiell berechenbar? Und stehen für die praktische Berechnung genügend physische Ressourcen zur Verfügung? Die Turingmaschine untersucht vor allem die erste Frage.

Der Lese-Schreib-Kopf und die Zustände

Der Kopf betrachtet jeweils nur ein Feld. Er liest dessen Symbol, kann es ersetzen und bewegt sich anschließend. Zusätzlich besitzt die Maschine einen aktuellen Zustand, etwa q0, q1 oder q2.

Eine Regel könnte lauten: Befindet sich die Maschine in q0 und liest 1, schreibt sie 0, bewegt sich nach rechts und wechselt nach q1.

Das Verhalten wird damit vollständig durch aktueller Zustand + gelesenes Symbol + Übergangsregel bestimmt.

Ein einfaches Beispiel: 1 addieren

Nehmen wir eine unäre Darstellung: Die Zahl 4 wird durch vier Einsen geschrieben.

1111

Eine Maschine soll 1 addieren. Solange sie 1 liest, bewegt sie sich nach rechts. Trifft sie auf ein leeres Feld, schreibt sie 1 und hält an.

11111

Damit hat sie 4 + 1 = 5 berechnet. Kein moderner Computer würde eine Addition so ausführen. Das Beispiel zeigt vielmehr, dass sich ein Rechenvorgang in eindeutig bestimmte mechanische Schritte zerlegen lässt.

Ist eine Turingmaschine ein echter Computer?

Nicht im üblichen Sinn. Sie ist in erster Linie ein mathematisches Objekt. Turing wollte 1936 keinen industriell baubaren Rechner entwerfen, sondern ein präzises Modell für berechenbare Verfahren schaffen.

Das unterscheidet sie etwa von Charles Babbages Analytical Engine, die tatsächlich als programmierbare mechanische Maschine gedacht war.

Von Babbage zu Turing

Babbage fragte im 19. Jahrhundert als Ingenieur, wie eine allgemeine Maschine unterschiedliche Berechnungen ausführen könnte. Lochkarten sollten Operationen und Daten darstellen.

Turing stellte eine abstraktere Frage: Was kann eine Rechenmaschine prinzipiell tun? Beide Ansätze unterscheiden sich, tragen aber zur Trennung zwischen physischer Maschine und den Anweisungen bei, die ihr Verhalten bestimmen.

Die universelle Turingmaschine

Eine der mächtigsten Ideen Turings ist die universelle Maschine. Statt für Addition, Vergleich oder andere Verfahren jeweils eine eigene Maschine zu benötigen, kann eine besondere Turingmaschine auf ihrem Band die Beschreibung einer anderen Maschine sowie deren Eingabedaten erhalten und anschließend deren Verhalten simulieren.

Das ist die universelle Turingmaschine.

Eine Maschine, viele Programme

Heute wirkt diese Idee selbstverständlich. Derselbe Computer kann Webseiten anzeigen, Fotos bearbeiten, Spiele ausführen, CSV-Dateien verarbeiten, Code kompilieren oder Videos abspielen. Wir bauen die Hardware nicht für jede Aufgabe neu, sondern wechseln das Programm.

Die universelle Maschine formalisiert genau diese Trennung zwischen einem allgemeinen Rechengerät und der Beschreibung der auszuführenden Berechnung.

Universelle Maschine und von-Neumann-Architektur sind nicht dasselbe

Beide Konzepte werden manchmal gleichgesetzt. Die universelle Turingmaschine ist jedoch ein mathematisches Modell dafür, dass eine Maschine andere Maschinen simulieren kann. Die von-Neumann-Architektur beschreibt dagegen eine praktische Organisation elektronischer Rechner, bei der Daten und Anweisungen im Speicher liegen können.

Die Ideen sind verwandt, verfolgen aber unterschiedliche Ziele: Turing untersucht Berechenbarkeit, die Entwickler früher elektronischer Rechner auch Architektur und praktische Realisierung.

Was ist ein berechenbares Problem?

Vereinfacht gilt ein Problem als berechenbar, wenn eine Turingmaschine existiert, die für die betreffenden Eingaben nach endlich vielen Schritten das erwartete Ergebnis liefert.

Damit wird aus der Intuition „Es müsste doch eine Methode geben“ eine mathematische Frage: Lässt sich ein präzises Verfahren angeben? Kann es durch mechanische Regeln beschrieben werden? Wird es eine Antwort erzeugen? Diese Fragen bilden den Kern der Berechenbarkeitstheorie.

Nicht alle Probleme sind berechenbar

Eine der tiefsten Erkenntnisse lautet: Es gibt Probleme, die kein Algorithmus in allen Fällen lösen kann. Das ist keine vorübergehende Grenze der Computertechnik der 1930er Jahre und lässt sich nicht durch schnellere Prozessoren oder mehr Speicher beseitigen.

Das bekannteste Beispiel ist das Halteproblem.

Das Halteproblem

Stellen wir uns ein Programm HALT vor. Es erhält ein beliebiges Programm und dessen Eingabedaten und soll entscheiden: Wird dieses Programm irgendwann anhalten oder für immer weiterlaufen?

Für manche Programme ist das offensichtlich. Ein Programm, das nur „Hallo“ ausgibt und endet, hält an; eine absichtliche Endlosschleife nicht. HALT soll aber für jedes mögliche Programm und jede Eingabe korrekt entscheiden.

Turing zeigte, dass ein solcher universeller Algorithmus nicht existieren kann.

Warum ist das so wichtig?

Das Halteproblem zeigt eine fundamentale Grenze der Automatisierung. Werkzeuge zur Programmanalyse können viele Fehler erkennen, bestimmte Schleifen identifizieren oder Eigenschaften für bestimmte Programmklassen beweisen. Aber kein Werkzeug kann das Halteproblem für alle denkbaren Programme perfekt lösen.

Der Unterschied zwischen „sehr schwierig“ und „im Allgemeinen unmöglich“ ist entscheidend.

Eine Grenze unabhängig von der Hardware

Selbst ein milliardfach schnellerer Rechner, gigantischer Speicher oder ein idealisierter Computer ändern nichts an der Unentscheidbarkeit des Halteproblems.

Damit lassen sich drei Arten von Grenzen unterscheiden: Zeit, Speicher und Berechenbarkeit. Die ersten beiden betreffen benötigte Ressourcen. Die dritte betrifft die Frage, ob überhaupt ein allgemeiner Algorithmus existiert.

Berechenbarkeit und Komplexität

Diese Begriffe werden häufig verwechselt. Berechenbarkeit fragt: Existiert ein Algorithmus für dieses Problem? Algorithmische Komplexität fragt: Wenn er existiert, wie viel Zeit oder Speicher benötigt er?

Ein Problem kann berechenbar und trotzdem praktisch extrem teuer sein. Ein unentscheidbares Problem besitzt dagegen keinen allgemeinen Algorithmus, der stets die richtige Antwort liefert.

Alonzo Church und der Lambda-Kalkül

Alan Turing war nicht der einzige Forscher auf diesem Gebiet. Alonzo Church entwickelte den Lambda-Kalkül, ein ganz anderes formales Modell von Berechnungen. Trotz ihrer unterschiedlichen Form charakterisieren beide Ansätze dieselbe Klasse berechenbarer Funktionen.

Diese unabhängige Konvergenz stärkte die Vorstellung, dass hier etwas Grundlegendes über den Begriff des Rechnens erfasst wurde.

Die Church-Turing-These

Vereinfacht besagt sie: Jede Berechnung, die durch ein effektives Verfahren ausgeführt werden kann, kann von einer Turingmaschine ausgeführt werden.

Es handelt sich um eine These und nicht um einen gewöhnlichen mathematischen Satz, weil „effektives Verfahren“ zunächst ein intuitiver Begriff ist. Ihre Stärke liegt auch darin, dass viele später entwickelte Rechenmodelle dieselbe Berechnungsmächtigkeit besitzen.

Ist ein moderner Computer eine Turingmaschine?

Nicht wörtlich. Reale Rechner besitzen endlichen Speicher, komplexe Prozessoren, Caches, Peripherie und häufig mehrere Kerne. Für die Untersuchung dessen, was prinzipiell berechenbar ist, werden klassische Universalrechner unter den üblichen Ressourcenannahmen jedoch als dem Turingmodell entsprechend betrachtet.

Ein anderer Prozessor oder eine andere Programmiersprache kann eine Berechnung schneller oder praktischer machen, verschiebt aber nicht plötzlich die grundlegende Grenze der Berechenbarkeit.

Ändert die Programmiersprache, was berechenbar ist?

Python, Java, C, JavaScript und C++ unterscheiden sich stark in Syntax, Abstraktionen, Leistung und Ökosystem. Eine allgemeine Turing-vollständige Sprache kann theoretisch und mit genügend Ressourcen jedoch jede Berechnung ausdrücken, die eine Turingmaschine ausführen kann.

Theoretische Berechnungsmächtigkeit ist daher nur eine von vielen Eigenschaften einer Sprache.

Was bedeutet Turing-vollständig?

Ein System heißt im Allgemeinen Turing-vollständig, wenn es unter den üblichen theoretischen Speicherannahmen eine universelle Turingmaschine simulieren kann. Der Begriff wird auf Programmiersprachen, virtuelle Maschinen, Umschreibesysteme und gelegentlich sogar Spiele oder Software angewandt, in denen Nutzer allgemeine Rechenmechanismen konstruieren.

Turing-vollständig bedeutet weder schnell noch praktisch. Es bezeichnet vor allem ausreichende Ausdrucksmächtigkeit für allgemeine Berechnungen.

Eine sehr einfache Maschine kann universell sein

Für Universalität sind nicht Hunderte verschiedener Instruktionen nötig. Selbst sehr einfache Varianten von Turingmaschinen können universell sein. Komplexes Verhalten kann aus der wiederholten Kombination weniger elementarer Operationen entstehen.

Diese Erkenntnis beeinflusst bis heute unsere Sicht auf Computer und Programmiersprachen.

Daten und Anweisungen werden zu Information

Bei einer universellen Maschine wird die Beschreibung der zu simulierenden Maschine selbst als Symbolfolge dargestellt. Anweisungen werden also zu Daten, die eine Maschine lesen kann.

Texte, Zahlen, Bilder, Programme und Instruktionen lassen sich allgemein in maschinenverarbeitbarer Form repräsentieren. Der Artikel über die Informationstheorie beleuchtet eine andere Seite dieser Abstraktion: wie Information gemessen und codiert werden kann.

Die Turingmaschine beschreibt keine Computerleistung

Das Modell soll nicht direkt die Geschwindigkeit realer Rechner vergleichen. Eine Turingmaschine kann eine Berechnung unglaublich langsam ausführen. Entscheidend ist die Frage: Kann diese Berechnung überhaupt durch ein algorithmisches Verfahren ausgeführt werden?

Für die praktische Nutzbarkeit müssen anschließend Komplexität, Algorithmen und reale Hardware betrachtet werden.

Und Quantencomputer?

Quantencomputer können für bestimmte Problemklassen erhebliche Geschwindigkeitsvorteile bieten und beruhen auf anderen physikalischen Prinzipien. Im üblichen theoretischen Rahmen machen sie jedoch Probleme, die im Turing-Sinn grundsätzlich nicht berechenbar sind, nicht plötzlich berechenbar.

Sie können die Effizienz bestimmter Berechnungen verändern, nicht notwendigerweise die fundamentale Grenze zwischen berechenbar und nicht berechenbar.

Warum wird die Turingmaschine noch gelehrt?

Ein abstraktes Band mag 2026 weit vom modernen Software Engineering entfernt wirken. Das Modell macht jedoch zentrale Ideen sichtbar:

• was ein Algorithmus ist;
• den Unterschied zwischen Programm und Maschine;
• universelle Berechnung;
• die Existenz unentscheidbarer Probleme;
• den Unterschied zwischen Berechenbarkeit und Komplexität;
• theoretische Grundlagen von Programmiersprachen.

Wie idealisierte Modelle in der Physik vereinfacht die Turingmaschine die Realität, um fundamentale Prinzipien sichtbar zu machen.

Von der Turingmaschine zu modernen Computern

Die Turingmaschine von 1936 ist nicht direkt die Architektur heutiger Rechner. Babbage entwarf im 19. Jahrhundert eine programmierbare mechanische Maschine; Lochkarten zeigten, dass Anweisungen und Daten auf einem externen Medium dargestellt werden können; Turing formalisierte die Idee einer universellen Maschine; in den 1940er Jahren wurden elektronische Stored-Program-Rechner gebaut.

Die von-Neumann-Architektur wurde anschließend zu einem der einflussreichsten Modelle für die praktische Organisation von Prozessor, Speicher, Daten und Anweisungen. Diese Entwicklung war keine gerade Linie und das Werk vieler Forscher, zeigt aber, wie eine abstrakte Frage über die Natur des Rechnens mit realen Computern verbunden wurde.

Ein weiterhin präsentes Erbe

Fast neunzig Jahre nach Turings Aufsatz steht sein Modell weiterhin im Zentrum der theoretischen Informatik. Fragen danach, ob ein Problem automatisierbar ist, ob Programme andere Programme vollständig analysieren können, ob eine Sprache allgemeine Berechnungen ausdrücken kann oder wo die intrinsischen Grenzen von Algorithmen liegen, führen direkt oder indirekt zur Berechenbarkeitstheorie zurück.

Computer sind unvorstellbar leistungsfähiger geworden. Doch mehr Leistung hebt mathematische Grenzen nicht auf. Darin liegt vielleicht das tiefste Erbe der Turingmaschine.

Das Wichtigste in Kürze

Die Turingmaschine ist ein mathematisches Berechnungsmodell, das Alan Turing 1936 vorstellte. Sie besteht aus Band, Lese-Schreib-Kopf, Symbolen, Zuständen und Übergangsregeln.

Die universelle Maschine zeigt, dass eine einzige Maschine viele andere simulieren kann, wenn ihre Beschreibung als Daten vorliegt. Konzeptuell weist dies auf die moderne Trennung von Hardware und Software voraus.

Gleichzeitig zeigt das Halteproblem, dass kein universeller Algorithmus für alle Programme entscheiden kann, ob sie anhalten werden.

Die Turingmaschine lehrt daher zwei scheinbar gegensätzliche Dinge: Eine sehr einfache Maschine kann eine enorme Vielfalt von Berechnungen ausführen, aber keine algorithmische Maschine kann alles berechnen.

Häufige Fragen

Wer erfand die Turingmaschine?

Der britische Mathematiker Alan Turing stellte das Modell 1936 in On Computable Numbers, with an Application to the Entscheidungsproblem vor.

Wurde eine Turingmaschine tatsächlich gebaut?

Das ursprüngliche Konzept ist ein mathematisches Modell und kein Bauplan für einen Computer. Physische Demonstrationsmodelle wurden später zu Lehrzwecken gebaut.

Was ist das Band einer Turingmaschine?

Es ist der theoretische Speicher des Modells: eine Folge von Feldern, die Symbole enthalten können und vom Lese-Schreib-Kopf bearbeitet werden.

Was ist eine universelle Turingmaschine?

Sie ist eine Turingmaschine, die die Beschreibung einer anderen Turingmaschine und deren Eingabe lesen und anschließend deren Verhalten simulieren kann.

Was ist das Halteproblem?

Es fragt, ob ein allgemeiner Algorithmus für jedes beliebige Programm und jede Eingabe entscheiden kann, ob das Programm irgendwann anhält. Turing zeigte, dass ein solcher Algorithmus nicht existiert.

Sind moderne Computer Turing-vollständig?

Allgemeine moderne Rechner und die meisten allgemeinen Programmiersprachen werden im theoretischen Sinn als Turing-vollständig betrachtet, wenn man die üblichen Annahmen über verfügbaren Speicher zugrunde legt.

Können Quantencomputer die Grenzen der Turingmaschine überwinden?

Sie können bestimmte berechenbare Probleme wesentlich effizienter lösen, machen aber nach dem üblichen theoretischen Verständnis grundsätzlich nicht berechenbare Probleme nicht berechenbar.