Wie ist der Unvollständigkeitssatz von Gödel zu verstehen?
Coole Frage! Ich will das mal versuchen, so einfach und in sich abgeschlossen wir möglich zu beantworten. Dabei bin ich, das sage ich gleich, nicht mathematisch korrekt, sondern versuche, das Wesentliche allgemeinverständlich darzustellen. Also:
Gödel sagt: "Du hast ein Symbolsystem, in dem du Aussagen formulieren und darüber 'räsonieren' kannst, ob eine Aussage wahr oder falsch ist. Dann kannst du in diesem Symbolsystem immer Aussagen formulieren, die sowohl syntaktisch korrekt als auch inhaltlich sinnvoll sind, bei denen du aber nach den 'Räsonierregeln' deines Symbolsystems nicht entscheiden kannst, ob die Aussage wahr oder falsch ist. Dies gilt für jedes solche Symbolsystem." Das Symbolsystem ist also bezüglich des Wahrheitsgehalts über alle in ihm formulierbaren Aussagen unvollständig - deshalb "Unvollständigkeitssatz".
Ein "Symbolsystem" kann beispielsweise die Zeichen "0" bis "9", "+", "-", "*" , "/", "=" sein, dazu weitere Symbole wie "für alle", "es gibt", "daraus folgt", "nicht", "und", "oder"; dazu kommen dann noch einige als "wahr" angenommene Aussagen, die die innere Struktur definieren: "Für alle a: a + 0 = a", "für alle a: es gibt a + 1", "für alle a: a * 1 = a", "für alle a,b: a ist wahr und b ist wahr, daraus folgt: a und b ist wahr" etc. Gödel verlangt für das "Symbolsystem" bestimmte Eigenschaften, die jedes System erfüllt, mit dem sich mehr als Trivialitäten ausdrücken lassen.
Ein einfaches Beispiel für so eine Aussage ist die Russell'sche Antinomie. Eine umgangssprachliche Version davon ist das Barbierparadoxon: "In einem Dorf rasiert der Barbier alle Männer, die sich nicht selbst rasieren. Wer rasiert den Barbier?" Behauptung: Der Barbier rasiert sich selbst. Dann gehört er aber nicht zur Menge der Männer, die sich nicht selbst rasieren, rasiert sich also nicht selbst. Kann also nicht sein. Also gegenteilige Behauptung: Der Barbier rasiert sich nicht selbst. Dann gehört er aber genau zu der Menge von Männern, die sich nicht selbst rasieren und wird also vom Barbier - also von sich selbst - rasiert. - Sowohl die erste Behauptung als auch ihr genaues Gegenteil führen zu einem in sich widersprüchlichen Ergebnis bei der Frage, welche von beiden wahr ist. Man kann also keine Aussage über den Wahrheitsgehalt dieser Aussagen treffen.
Diese logischen Widersprüchlichkeiten waren in der Mathematik unterschwellig schon seit langem bekannt. Russell war der erste, dem es gelungen war, sie streng formal aufzuschreiben. Das war Ende des 19. Jahrhunderts. Die Mathematik behalf sich damit, dass sie das Symbolsystem so erweiterte, dass Aussagen dieses Typs nicht mehr "möglich" waren, mit anderen Worten: Es wurde ein neues Symbolsystem geschaffen. Die Hoffnung war seinerzeit, dass es ein Symbolsystem gäbe, in dem (a) alle für eine allumfassende Mathematik nötigen Aussagen formulierbar sind und (b) alle diese Aussagen eindeutig als wahr oder falsch aus den Regeln des Symbolsystems selbst heraus bestimmt werden können. Die Suche der Mathematiker des frühen 20. Jahrhunderts nach einem solchen Symbolsystem das sogenannte "Hilbertprogramm", hat Gödel Anfang der 1930er Jahre beendet - und zwar leider mit der Antwort, dass es ein solches Symbolsystem nicht geben kann.
Ich will jetzt nicht tiefer in den Beweis einsteigen, Im Grundsatz macht Gödel nicht anderes, als oben in dem Barbierparadoxon: Er konstruiert eine Aussage so, dass sowohl die Aussage ("Barbier rasiert sich selbst") als auch ihr Gegenteil ("Barbier rasiert sich nicht selbst") aus den Regeln des Symbolsystems hergeleitet werden können. Das Bahnbrechende war, dass er Symbolsystem und Aussage so allgemeingültig formal hinschreiben konnte, dass die Aussage für jedes Symbolsystem gilt.
Eng verwandt mit dem Unvollständigkeitssatz ist Turings Halteproblem. Alan Turing hat - ebenfalls in den 1930er Jahren - das Konzept der Rechenmaschine formalisiert. Die "Turingmaschine" ist ein (theoretischer) Automat, der Rechenvorschriften streng formal und deterministisch abarbeiten kann. Das entspricht dem "Räsonieren" in Gödels Symbolsystemen. Die Turingmaschine beendet das Abarbeiten von Rechenvorschriften, wenn sie in einem bestimmten Zustand angekommen ist. Das entspricht dem Finden der Antwort, ob eine Aussage wahr oder falsch ist. Und genau wie Gödel seine Symbols konnte Turing seine Maschine derart mit einer Liste von Rechenvorschriften und internen Zuständen ausstatten, dass es keine Turingmaschine geben kann, die mit Hilfe eines Programms (Gödel: "innerhalb des Symbolsystems") berechnen kann, ob die erste Maschine jemals in einen solchen finalen Zustand kommen wird oder nicht - sprich: Ob sie anhält oder endlos weiterläuft; deshalb heißt das ganze "Halteproblem". Auch dieser Beweis arbeitet mit selbstbezüglichen Strukturen.
Turingmaschinen sind als mathematisches Modell aller heute existierenden Computer anerkannt: Genau alles, was prinzipiell mit einer Turingmaschine berechenbar ist, kann auch mit einem real existierenden Computer berechnet werden. Insofern zeigen das Halteproblem und der Unvollständigkeitssatz prinzipielle Grenzen von theoretischer und praktischer Berechenbarkeit auf: Es gibt keine Möglichkeit, ein Programm für einen Computer zu schreiben, mit dem alle anderen Programme auf Korrektheit geprüft werden können. Die Betonung liegt dabei auf "alle", denn für Spezialprobleme geht das durchaus. Und das ist auch kein Widerspruch zu Gödel und Turing, denn diese Spezialprobleme sind dann in einem "Symbolsystem" (oder einer Turingmaschine) definiert, die die nötige Allgemeingültigkeit nicht mehr haben.
Ich finde, der Gödel'sche Unvollständigkeitssatz ist eines der faszinierendsten Resultate, die die Mathematik jemals hervorgebracht hat.