Melvin Henriksen – emeritierter Professor für Mathematik am Harvey Mudd College – bietet diese Erklärung an:
Eine mathematisch präzise Erklärung von Godels Unvollständigkeitssatz zu geben, würde nur seinen wichtigen intuitiven Inhalt vor fast jedem verbergen, der kein Spezialist für mathematische Logik ist. Daher werde ich ihn stattdessen in der Sprache der Computer neu formulieren und vereinfachen.
Stellen Sie sich vor, dass wir Zugang zu einem sehr leistungsfähigen Computer namens Oracle haben. Wie die Computer, mit denen wir vertraut sind, verlangt Oracle, dass der Benutzer Anweisungen „eingibt“, die präzisen Regeln folgen, und es liefert die „Ausgabe“ oder Antwort auf eine Weise, die ebenfalls diesen Regeln folgt. Die gleiche Eingabe wird immer die gleiche Ausgabe erzeugen. Die Eingabe und die Ausgabe werden als ganze Zahlen geschrieben und Oracle führt nur die üblichen Operationen wie Addition, Subtraktion, Multiplikation und Division (wenn möglich) durch. Im Gegensatz zu gewöhnlichen Computern gibt es keine Bedenken hinsichtlich Effizienz oder Zeit. Oracle führt korrekt gegebene Anweisungen aus, egal wie lange es dauert, und es hört erst auf, wenn sie ausgeführt sind – selbst wenn es mehr als eine Million Jahre dauert.
Betrachten wir ein einfaches Beispiel. Erinnern Sie sich, dass eine positive ganze Zahl (nennen wir sie N), die größer als 1 ist, als Primzahl bezeichnet wird, wenn sie durch keine positive ganze Zahl außer 1 und N teilbar ist. Sagen Sie ihm, dass es N durch jede ganze Zahl zwischen 1 und N-1 teilen soll und dass es aufhören soll, wenn die Division gleichmäßig ausfällt oder N-1 erreicht. (Eigentlich können Sie aufhören, wenn es die Quadratwurzel von N erreicht. Wenn es zu diesem Zeitpunkt keine geraden Teilungen von N gegeben hat, dann ist N prim.)
Das Godelsche Theorem besagt, dass es richtig gestellte Fragen gibt, die nur die Arithmetik der ganzen Zahlen betreffen, die Oracle nicht beantworten kann. Mit anderen Worten, es gibt Aussagen, die – obwohl sie korrekt eingegeben wurden – Oracle nicht auswerten kann, um zu entscheiden, ob sie wahr oder falsch sind. Solche Aussagen nennt man unentscheidbar, und sie sind sehr kompliziert. Und wenn Sie Dr. Godel eine solche Aussage bringen würden, würde er Ihnen erklären, dass es solche Aussagen immer geben wird.
Selbst wenn man Ihnen ein „verbessertes“ Modell von Oracle geben würde, nennen wir es OracleT, in dem eine bestimmte unentscheidbare Aussage, UD, für wahr erklärt wird, würde eine andere unentscheidbare Aussage erzeugt werden, die ihren Platz einnimmt. Noch rätselhafter ist, dass Sie auch ein anderes „verbessertes“ Modell von Oracle erhalten könnten, nennen wir es OracleF, in dem UD als falsch dekretiert wird. Unabhängig davon würde auch dieses Modell andere unentscheidbare Aussagen generieren und könnte Ergebnisse liefern, die sich von denen von OracleT unterscheiden, aber genauso gültig sind.
Findet ihr das schockierend und fast paradox? Noch schockierender war es für die mathematische Welt im Jahr 1931, als Godel seinen Unvollständigkeitssatz enthüllte. Godel formulierte sein Ergebnis nicht in der Sprache der Computer. Er arbeitete in einem bestimmten logischen System und die Mathematiker hofften, dass sein Ergebnis von den Eigenheiten dieses Systems abhing. Aber im nächsten Jahrzehnt oder so, eine Reihe von Mathematikern – einschließlich Stephen C. Kleene, Emil Post, J.B. Rosser und Alan Turing – zeigten, dass dies nicht der Fall war.
Die Forschung über die Konsequenzen dieses großen Theorems dauert bis heute an. Jeder, der einen Internetzugang hat und eine Suchmaschine wie Alta Vista benutzt, kann mehrere hundert Artikel von sehr unterschiedlicher Qualität über Godels Theorem finden. Zu den besten Lektüren gehört jedoch Godel’s Proof von Ernest Nagel und James R. Newman, 1958 veröffentlicht und 1983 als Taschenbuch bei New York University Press erschienen.