Universalität

Programme als Daten

Turing zeigte 1936: Man kann eine Turingmaschine als Zeichenkette aufschreiben – Regel für Regel. Und man kann eine Maschine bauen, die eine solche Zeichenkette liest und Schritt für Schritt ausführt. Das Feld links ist so eine Beschreibung, und dieser Simulator ist die universelle Maschine. Ändere die Regeln und schau, was passiert:

Zwei Dinge fallen auf. Erstens: Der Simulator selbst ändert sich nie – nur die Daten, die man ihm gibt. Zweitens: Bei der Endlosschleife bricht er nach 2000 Schritten ab. Er kann nicht wissen, ob die Maschine mit Schritt 2001 vielleicht doch angehalten hätte. Dass sich das grundsätzlich nicht vorab entscheiden lässt, ist der Inhalt von G4 Berechenbarkeit.

Von Turing zu von Neumann

Die frühen Rechner wurden für jede Aufgabe neu verkabelt: Beim ENIAC (1945) bedeutete ein neues Programm tagelanges Umstecken. John von Neumann beschrieb 1945 im Entwurf zum EDVAC einen Rechner, der das Programm wie Daten im Speicher hält – die Idee der universellen Maschine, in Röhren gegossen. Ein Programm zu wechseln hieß nun: andere Zahlen in den Speicher laden.

Diese Idee hat sich durch alle Schichten fortgepflanzt. Jede Ebene ist eine universelle Maschine, die die nächste als Daten behandelt:

Darauf beruhen auch virtuelle Maschinen, Emulatoren, die alte Spielkonsolen auf dem Handy laufen lassen, und JIT-Compiler, die zur Laufzeit neuen Maschinencode erzeugen und ausführen.

Was „Turing-vollständig“ heißt

Ein System ist Turing-vollständig, wenn es jede Turingmaschine simulieren kann – meist zeigt man das, indem man darin eine einfachere, bekannt universelle Maschine nachbaut. Die Zutaten sind überraschend bescheiden: Speicher, der bei Bedarf wachsen kann, und eine Möglichkeit, abhängig von Daten unterschiedlich weiterzumachen und Dinge zu wiederholen. Deshalb taucht Universalität an unerwarteten Stellen auf. Tippe:

Streng genommen ist kein echter Rechner Turing-vollständig, weil sein Speicher endlich ist. Man sagt es trotzdem, wenn die einzige Grenze der Speicher ist – nicht die Sprache selbst.

Das Prinzip der geringsten Mächtigkeit

Universalität klingt nach einem Vorteil, hat aber einen Preis: Über ein Turing-vollständiges Programm kann man im Allgemeinen nicht vorab sagen, ob es anhält, wie lange es läuft oder was es tun wird – man muss es ausführen. Für Daten und Konfiguration ist das ein Nachteil. Tim Berners-Lee formulierte daraus das Prinzip der geringsten Mächtigkeit: Wähle die schwächste Sprache, die für die Aufgabe ausreicht. Deshalb ist JSON eine reine Datenbeschreibung, deshalb prüft der Linux-Kern eBPF-Programme vor dem Laden darauf, dass sie terminieren, und deshalb sind deklarative Formate wie SQL ohne Rekursion oder Build-Beschreibungen in YAML oft leichter zu prüfen als ein Skript.

Für Entwickler übersetzt

Die JVM ist eine universelle Maschine im Lehrbuchsinn: Programme kommen als Daten herein – als Bytes einer .class-Datei – und werden ausgeführt. Java kann das sogar mit sich selbst:

// Bytecode zur Laufzeit laden – das Programm ist ein byte[]
class AusBytes extends ClassLoader {
    Class<?> lade(String name, byte[] code) {
        return defineClass(name, code, 0, code.length);
    }
}

// Java-Quelltext zur Laufzeit übersetzen – der Compiler als Bibliothek
JavaCompiler javac = ToolProvider.getSystemJavaCompiler();
int ergebnis = javac.run(null, null, null, "Generiert.java");

// Das Interpreter-Muster: eine eigene kleine Sprache, deren Programme Objekte sind
sealed interface Ausdruck permits Zahl, Plus, Mal {}
record Zahl(int wert) implements Ausdruck {}
record Plus(Ausdruck l, Ausdruck r) implements Ausdruck {}
record Mal(Ausdruck l, Ausdruck r) implements Ausdruck {}

static int werte(Ausdruck a) {
    return switch (a) {
        case Zahl z -> z.wert();
        case Plus p -> werte(p.l()) + werte(p.r());
        case Mal m  -> werte(m.l()) * werte(m.r());
    };
}

Dieser kleine Interpreter ist übrigens nicht Turing-vollständig – er hat weder Verzweigungen noch Schleifen, jede Auswertung endet garantiert. Genau das kann gewollt sein: Lässt man Nutzer Formeln eingeben, ist eine Sprache, die immer terminiert, viel sicherer als ein eingebetteter Skriptinterpreter.

Häufige Irrtümer

Verwandte Begriffe