Turingmaschine

Turings Idee

Alan Turing suchte 1936 eine Antwort auf eine Frage des Mathematikers David Hilbert: Gibt es ein mechanisches Verfahren, das für jede mathematische Aussage entscheidet, ob sie beweisbar ist? Dazu musste er erst einmal festlegen, was „mechanisches Verfahren“ überhaupt heißt. Er stellte sich einen Menschen vor, der mit Bleistift auf kariertem Papier rechnet – und strich alles weg, was nicht nötig ist:

Das Ergebnis ist eine Maschine, die so einfach ist, dass man über sie mathematisch exakte Aussagen beweisen kann – und gleichzeitig so mächtig, dass niemand seither ein Verfahren gefunden hat, das sie nicht nachbilden könnte.

Eine Turingmaschine zum Mitklicken

Drei kleine Programme. Gelesen wird immer das hervorgehobene Feld unter dem Kopf; in der Tabelle ist die Regel markiert, die als Nächstes greift.

Bei aⁿbⁿ sieht man den Unterschied zum endlichen Automaten: Der Automat scheiterte, weil er nicht beliebig weit zählen kann. Die Turingmaschine zählt gar nicht – sie markiert auf dem Band: ein a abhaken, das passende b suchen und abhaken, zurück, von vorn. Der Speicher wächst mit der Eingabe.

Einfach, aber langsam

Der Preis für die Einfachheit: Der Kopf muss ständig hin- und herlaufen. Für aⁿbⁿ braucht die Maschine ungefähr 2n² Schritte – ein Java-Programm mit einem Zähler käme mit einem Durchlauf aus:

Das ist kein Mangel des Modells, sondern Absicht: Für die Frage, ob etwas berechenbar ist, spielt die Geschwindigkeit keine Rolle. Und für die Frage, wie schnell, gilt eine beruhigende Tatsache: Turingmaschine und echter Rechner simulieren einander mit höchstens polynomiellem Mehraufwand. Ein Problem, das auf dem einen in Polynomialzeit lösbar ist, ist es auch auf dem anderen – deshalb kann die Komplexitätstheorie die Klasse P mit der Turingmaschine definieren.

Die Church-Turing-These

Fast gleichzeitig mit Turing entwickelte Alonzo Church den Lambda-Kalkül – ein Modell ganz ohne Band und Kopf, nur aus Funktionen, die Funktionen anwenden. Kurt Gödel und andere hatten die rekursiven Funktionen definiert. Es stellte sich heraus: Alle diese Modelle können genau dasselbe berechnen. Später kamen weitere hinzu, mit demselben Ergebnis:

Die These lautet: Alles, was intuitiv „berechenbar“ ist, kann eine Turingmaschine berechnen. Beweisen lässt sie sich nicht, weil „intuitiv berechenbar“ kein mathematischer Begriff ist. Aber in neunzig Jahren hat niemand ein Gegenbeispiel gefunden – auch Quantencomputer nicht: Sie können manche Probleme schneller lösen, aber keine, die eine Turingmaschine grundsätzlich nicht lösen kann.

Der fleißige Biber

Wie viel kann eine Maschine mit n Zuständen tun, bevor sie anhält? Die Frage klingt harmlos, aber ihre Antworten wachsen schneller als jede berechenbare Funktion. Gemeint sind Maschinen mit zwei Zeichen, die auf einem leeren Band starten und irgendwann anhalten – gezählt wird die größte erreichbare Schrittzahl:

Dass diese Werte so schwer zu finden sind, ist kein Zufall: Man müsste für jede der Maschinen entscheiden, ob sie irgendwann anhält. Und genau das ist im Allgemeinen unmöglich – das Halteproblem, Thema von G4.

Für Entwickler übersetzt

Eine Turingmaschine in Java passt auf eine Bildschirmseite – das Band als Map, damit es in beide Richtungen wachsen kann:

record Regel(char schreibe, int richtung, String neu) {}   // richtung: -1 links, +1 rechts

class Turingmaschine {
    private final Map<String, Regel> regeln = new HashMap<>();   // Schlüssel: Zustand + gelesenes Zeichen

    void regel(String zustand, char lies, char schreibe, int richtung, String neu) {
        regeln.put(zustand + lies, new Regel(schreibe, richtung, neu));
    }

    String laufe(String eingabe, String start, Set<String> halt) {
        Map<Integer, Character> band = new HashMap<>();
        for (int i = 0; i < eingabe.length(); i++) band.put(i, eingabe.charAt(i));
        String z = start;
        int kopf = 0;
        while (!halt.contains(z)) {
            char c = band.getOrDefault(kopf, '_');
            Regel r = regeln.get(z + c);
            if (r == null) return "abgelehnt";          // keine Regel: Maschine bleibt stehen
            band.put(kopf, r.schreibe());
            kopf += r.richtung();
            z = r.neu();
        }
        return z;
    }
}

Bemerkenswert ist die Umkehrung: Diese Klasse ist eine Turingmaschine, die andere Turingmaschinen ausführt – die Regeln sind nur Daten. Das ist die Idee der universellen Maschine, Thema von G3. Und es zeigt, warum man von einer Sprache sagt, sie sei Turing-vollständig: wenn man darin eine Turingmaschine simulieren kann. Dafür genügt erstaunlich wenig – bedingte Sprünge und unbegrenzt erweiterbarer Speicher.

Häufige Irrtümer

Verwandte Begriffe