Wie Gödel und Turing die Grenzen von KI vorgezeichnet haben

Im Studium begegnen einem Namen wie Kurt Gödel und Alan Turing meist mit derselben Mischung aus Respekt und leichter Resignation. Man liest, was sie bewiesen haben, akzeptiert es als beeindruckend und legt das Wissen anschließend in jenes mentale Archiv, das man irgendwo zwischen „interessant“ und „werde ich nie wieder brauchen“ verortet. Dass die Unvollständigkeit der Arithmetik oder die Unentscheidbarkeit des Halteproblems eines Tages mit der Frage zusammenfallen könnten, warum mir ein Chatbot gerade einen Buchtitel halluziniert hat, hätte ich vor einigen Jahren niemandem geglaubt.

Genau das ist aber passiert. Mehrere wissenschaftliche Arbeiten der letzten drei Jahre zeigen, dass die Halluzinationen von Sprachmodellen kein Implementierungsfehler sind, den man mit mehr Daten oder besserer Architektur wegtrainieren könnte. Sie folgen aus denselben theoretischen Grenzen, an denen einmal das ehrgeizigste Projekt der modernen Mathematik zerbrochen ist. Wer diese Verbindung einmal gesehen hat, liest die aktuelle Debatte um die Zukunft der KI mit deutlich nüchternerem Blick.

Das Versprechen von 1928

Um zu verstehen, warum die Forschungslandschaft der KI heute so ist, wie sie ist, lohnt sich ein Umweg über den Internationalen Mathematikerkongress in Bologna im Jahr 1928. Dort formulierte David Hilbert, einer der einflussreichsten Mathematiker seiner Zeit, gemeinsam mit Wilhelm Ackermann ein Forschungsprogramm, das die gesamte Mathematik auf eine vollkommen neue Grundlage stellen sollte. Drei Eigenschaften sollten dieses Fundament tragen:

1. Konsistenz, also die Gewissheit, dass aus den Axiomen keine widersprüchlichen Aussagen abgeleitet werden können.
2. Vollständigkeit, also die Garantie, dass jede wahre Aussage innerhalb des Systems auch bewiesen werden kann.
3. Und Entscheidbarkeit, also die Existenz eines Verfahrens, mit dem sich für jede beliebige Aussage in endlich vielen Schritten entscheiden lässt, ob sie aus den Axiomen folgt.

Die dritte Forderung ist als Entscheidungsproblem in die Geschichte eingegangen. Hinter ihr stand eine konkrete Vision. Mathematik sollte mechanisierbar werden. Eine Maschine, die endlich viele Regeln auf endlich vielen Zeichen anwendet, müsste jede mathematische Frage prinzipiell beantworten können. Wer in dieser Vision den Schatten dessen erkennt, was wir heute Computer nennen, liegt nicht falsch. Hilbert dachte den Computer mit, lange bevor es ihn gab.

Sein Optimismus war ungebrochen. Im September 1930 hielt er in Königsberg eine berühmt gewordene Radioansprache, die er mit dem Satz beendete: „Wir müssen wissen, wir werden wissen.“ Es war die letzte große Verkündigung einer Mathematik, die sich selbst noch alles zutraute. Wenige Tage zuvor hatte am selben Ort, auf einer parallel laufenden erkenntnistheoretischen Tagung, ein junger Mann namens Kurt Gödel in einer beiläufigen Bemerkung erstmals jene Ergebnisse skizziert, die Hilberts Programm in den Grundfesten erschüttern sollten. Dass die beiden Ereignisse so dicht beieinander lagen, ist eine historische Pointe, der man nicht zu viel symbolisches Gewicht aufladen sollte. Aber interessant ist sie allemal.

Gödel ohne Formeln

Was Gödel 1930 vorgestellt und 1931 ausführlich publiziert hat, lässt sich erstaunlich gut ohne mathematische Notation erklären. Sein Trick beruht auf einem Verfahren, das jeder verständlich findet, der einmal eine sich selbst aufrufende Funktion gesehen hat: Selbstreferenz. Stellen Sie sich ein hinreichend mächtiges formales System vor, in dem sich arithmetische Aussagen formulieren lassen. Gödel hat gezeigt, wie sich innerhalb eines solchen Systems eine Aussage konstruieren lässt, die in etwa besagt: „Diese Aussage ist im vorliegenden System nicht beweisbar.“

An diesem Punkt sollte man kurz innehalten, weil die Konsequenz unausweichlich ist. Ist die Aussage wahr, dann gibt es eine wahre arithmetische Aussage, die das System nicht beweisen kann. Damit ist das System unvollständig. Ist die Aussage falsch, dann beweist das System eine Aussage, die behauptet, nicht beweisbar zu sein, obwohl sie es offenbar doch ist. Damit ist das System inkonsistent. Es gibt keinen dritten Weg.

Wer den Lügner aus der antiken Philosophie kennt, der sich selbst der Lüge bezichtigt, erkennt das Muster wieder. Was Gödel jedoch geleistet hat, war keine philosophische Spielerei, sondern ein streng formaler Beweis innerhalb der Arithmetik selbst. Er zeigte, dass die Selbstreferenz nicht auf gemeinsprachliche Aussagen beschränkt bleibt, sondern in jedem hinreichend ausdrucksstarken formalen System auftaucht.

Gödel hat damit nicht gezeigt, dass die Mathematik kaputt ist. Er hat gezeigt, dass es prinzipielle Grenzen gibt, an denen jede ausreichend mächtige Theorie auf sich selbst zurückgeworfen wird. Hilberts Vision einer mechanisierbaren, in sich abgeschlossenen Mathematik bekam damit einen Riss, den niemand mehr kitten konnte. Die Konsequenz wurde später so formuliert: Jedes System, das genug Ausdrucksstärke hat, um über sich selbst zu sprechen, hat blinde Flecken, die sich nicht wegoptimieren lassen.

Besonders bemerkenswert an Gödels Ergebnis ist, dass es nicht von einer bestimmten Theorie abhängt. Es gilt für die Arithmetik, für die Mengenlehre, für jede formale Theorie, die ausreichend Ausdrucksstärke besitzt, um die natürlichen Zahlen mitsamt Addition und Multiplikation zu beschreiben. Wer das System tauscht, tauscht nur das Gewand der Grenze, nicht die Grenze selbst. In den Jahrzehnten nach Gödel wurden zahlreiche weitere Sätze bewiesen, die zeigen, dass die Selbstreferenz an erstaunlich (oder erschreckend) vielen Stellen ihren Tribut fordert. Das Halteproblem ist nur das bekannteste Beispiel dafür.

Turing macht Gödel praktisch

Sechs Jahre nach Gödels Beweis erschien in den Proceedings of the London Mathematical Society eine Arbeit, die heute zu den Gründungsdokumenten der Informatik zählt: Alan Turings Aufsatz „On Computable Numbers, with an Application to the Entscheidungsproblem“. Turing hatte sich gefragt, was es eigentlich heißt, dass ein Verfahren mechanisch ausführbar ist. Er entwarf dafür ein gedankliches Konstrukt, das wir heute Turing-Maschine nennen, und nutzte es, um Hilberts dritter Forderung den Garaus zu machen. Im selben Jahr und unabhängig von Turing kam Alonzo Church zu einem entsprechenden Ergebnis auf dem Weg über den Lambda-Kalkül.

Turings Resultat ist als Halteproblem bekannt. Es lässt sich in einem Satz zusammenfassen: Es gibt kein allgemeines Verfahren, das für ein beliebiges Programm und eine beliebige Eingabe entscheiden kann, ob das Programm jemals zum Ende kommt. Diese Aussage klingt zunächst harmlos, ist aber von erheblicher Tragweite. Sie sagt nicht, dass wir bisher kein solches Verfahren gefunden haben. Sie sagt, dass es ein solches Verfahren niemals geben kann.

Wer heute in der Softwareentwicklung arbeitet, lebt mit den Konsequenzen dieses Beweises, ohne sich dessen jeden Tag bewusst zu sein. Statische Codeanalyse stößt bei substanziellen Fragen über das Programmverhalten auf prinzipielle Grenzen. Compiler-Optimierer müssen Heuristiken einsetzen, weil eine vollständige Analyse mancher Codepfade unentscheidbar bleibt. Formale Verifikation funktioniert nur dort wirklich gut, wo man das untersuchte Problem auf entscheidbare Fragmente einschränkt. Wir haben uns daran gewöhnt, mit den Folgen einer mathematischen Grenze umzugehen, ohne sie noch jedes Mal benennen zu müssen.

Verschärft wird die Lage durch ein Ergebnis, das Henry Gordon Rice 1953 bewiesen hat. Sein Satz besagt, dass jede nicht-triviale semantische Eigenschaft eines Programms unentscheidbar ist. Damit ist nicht nur die Frage nach dem Terminieren prinzipiell offen, sondern praktisch jede interessante Frage über das Verhalten von Programmen. Ob ein bestimmter Codepfad jemals durchlaufen wird, ob zwei Programme funktional äquivalent sind, ob ein Programm eine bestimmte Ausgabe niemals produziert: Für all das gibt es kein allgemeines Entscheidungsverfahren. Was dem Berufsalltag in der Softwareentwicklung als zähe Heuristik begegnet, ist im Kern dieselbe Grenze, an die Hilbert 1928 gehofft hatte, nicht zu stoßen.

Mit Turings Arbeit war Hilberts Programm in seiner ursprünglichen Form endgültig erledigt. Konsistenz und Vollständigkeit hatte Gödel zerlegt, die Entscheidbarkeit nahmen Turing und Church mit nach Hause. Das ehrgeizigste mathematische Forschungsprogramm des frühen 20. Jahrhunderts war an seinen eigenen Voraussetzungen gescheitert. Was übrig blieb, war die nüchterne Einsicht, dass auch die Mathematik mit Grenzen leben muss, die sie nicht selbst aufgehoben hat, sondern an denen sie sich vorfindet.

Dieselbe Mauer, neuer Anstrich

Damit kehre ich zu der Frage zurück, die diesen Text ausgelöst hat. Was hat das alles mit Sprachmodellen zu tun?

Im Januar 2024 reichten Ziwei Xu, Sanjay Jain und Mohan Kankanhalli von der National University of Singapore eine Arbeit mit dem Titel „Hallucination is Inevitable: An Innate Limitation of Large Language Models“ ein. Sie formalisieren das Problem in einer formalen Welt, in der Halluzination als Inkonsistenz zwischen einem berechenbaren Sprachmodell und einer berechenbaren Wahrheitsfunktion definiert ist. Ihr zentrales Ergebnis stützt sich auf die Lerntheorie und auf ein Argument, das in seiner Struktur direkt mit den Diagonalisierungsverfahren Cantors und Turings verwandt ist: Sprachmodelle können nicht alle berechenbaren Funktionen lernen. Sobald sie ein breites Spektrum an Problemen lösen sollen, werden sie zwangsläufig halluzinieren. Es gibt keine Trainingsmethode, keine Architekturvariante und keinen Datenumfang, der diese Grenze verschiebt.

Wenige Monate später, im September 2024, legten Sourav Banerjee, Ayushi Agarwal und Saloni Singla mit „LLMs Will Always Hallucinate, and We Need to Live With This“ eine zweite, unabhängige Argumentationslinie vor. Sie gehen direkter zur Sache und stützen sich ausdrücklich auf Gödels ersten Unvollständigkeitssatz sowie auf die Unentscheidbarkeit von Halteproblem, Emptiness-Problem und Acceptance-Problem. Ihre Schlussfolgerung ist noch entschiedener formuliert: Halluzinationen lassen sich nicht durch architektonische Verbesserungen, Datenanreicherung oder Fact-Checking eliminieren, weil sie aus der fundamentalen mathematischen und logischen Struktur dieser Modelle folgen. Sie führen dafür den Begriff der Structural Hallucination ein, der das Phänomen nicht als Fehler, sondern als strukturelle Eigenschaft beschreibt.

An dieser Stelle ist Vorsicht geboten, denn beide Arbeiten verwenden den Begriff der Halluzination in einer formal definierten Weise, die sich nicht vollständig mit dem alltagssprachlichen Gebrauch deckt. Die Aussagen bedeuten nicht, dass jeder zweite Satz eines Sprachmodells falsch sein muss. Sie bedeuten, dass eine perfekte Wahrheitsmaschine, die in beliebigen Domänen zuverlässig korrekte Antworten liefert, mathematisch unmöglich ist. Was die alltägliche Halluzinationsrate angeht, ist mit weiteren Verbesserungen zu rechnen. Was die prinzipielle Eliminierbarkeit angeht, ist mit nichts dergleichen zu rechnen.

Konkret heißt das Folgendes: Selbst wenn ein Sprachmodell auf einer perfekten Datenbasis trainiert würde und über beliebig viele Parameter verfügte, gäbe es immer Fragen, auf die es plausibel klingende, aber falsche Antworten liefern würde. Banerjee, Agarwal und Singla zeigen darüber hinaus, dass jede Stufe des Verarbeitungsprozesses, von der Zusammenstellung der Trainingsdaten über die Faktenwiederherstellung bis zur eigentlichen Textgenerierung, eine von Null verschiedene Fehlerwahrscheinlichkeit aufweist. Diese Fehler summieren sich auf, lassen sich aber an keiner Stelle vollständig vermeiden. Das ist keine empirische Beobachtung, die sich durch bessere Verfahren widerlegen ließe. Es ist ein Ergebnis derselben Art wie die Unmöglichkeit, einen allgemeinen Halteprüfer zu bauen.

Bemerkenswert ist, dass beide Arbeiten unabhängig voneinander zu demselben Schluss gelangen, allerdings über unterschiedliche Wege. Xu, Jain und Kankanhalli argumentieren über die Lerntheorie. Banerjee, Agarwal und Singla argumentieren über die klassische Berechenbarkeitstheorie. Es ist dieselbe Mauer, an die beide Gruppen laufen. Wer mit den Ergebnissen Gödels und Turings vertraut ist, erkennt sie sofort wieder.

Damit gewinnt auch die populäre Forderung, das Problem der Halluzinationen einfach durch mehr Trainingsdaten oder größere Modelle zu lösen, einen anderen Beiklang. Sie ist nicht falsch in dem Sinne, dass größere Modelle nicht besser werden würden. Sie übersieht nur, dass eine Skalierung an dieser Stelle nicht das Problem berührt, das die zitierten Arbeiten beschreiben. Eine Funktion, die nicht lernbar ist, wird nicht durch mehr Parameter lernbar. Eine Frage, die unentscheidbar ist, wird nicht durch mehr Daten entscheidbar. Die Grenze ist keine Frage des Maßstabs, sondern eine Frage der Natur des Verfahrens.

Eine alte Erkenntnis in neuem Gewand

Hilbert hat sein Programm bis zum Lebensende nicht völlig aufgegeben. Auch nachdem Gödel und Turing seine Voraussetzungen widerlegt hatten, hielt er an dem Glauben fest, dass der wissenschaftliche Geist letztlich jede Frage werde beantworten können. Heute klingt diese Haltung beinahe rührend, gewiss aber als historische Anekdote. Man kann sich darin gefallen, sie etwas belustigt zu betrachten und nachsichtig zu schmunzeln über einen großen Geist, der eine bewiesene Grenze nicht akzeptieren wollte.

Bei aller Belustigung sollte man sich dabei aber fragen, was die Forschungslandschaft der nächsten Jahre über uns selbst erzählen wird. Wir bauen mit erheblichem Aufwand Systeme, die immer mehr Sprache aus der Welt aufsaugen und auf immer mehr Parameter verteilen, in der erkennbaren Hoffnung, dass irgendwann die Halluzinationen verschwinden, wenn man nur lange genug skaliert. Die Mathematik der letzten 90 Jahre legt nahe, dass dieser Weg an genau jene Wand stoßen wird, an die Hilbert gestoßen ist. Nicht weil die Modelle zu klein wären, sondern weil das, was wir uns von ihnen erhoffen, in der gewählten Form nicht zu haben ist.

Vielleicht stellt sich in einigen Jahren heraus, dass der heutige Ansatz für KI nicht der richtige war. Vielleicht auch nicht. Aber dass es sich lohnt, die Frage zu stellen, ob wir gerade ein zweites Mal dabei sind, eine bewiesene Grenze zu ignorieren, kann ich nur empfehlen. Die alten Studieninhalte sind vielleicht doch nicht so trocken, wie sie damals schienen.

(mro)