https://www.faz.net/-gqe-acpc0

90 Jahre her : Als Kurt Gödel die Grenzen des Berechenbaren entdeckte

  • -Aktualisiert am

Hat die Mathematik durcheinandergewirbelt: Kurt Gödel (das Bild zeigt ihn im Jahr 1935) Bild: Picture-Alliance

Über eine wegweisende Leistung, die einst die Mathematik durchrüttelte – und letztlich die theoretische Informatik begründete. Ein Gastbeitrag.

          4 Min.

          In diesem Jahr feiern wir den 90. Jahrestag von Kurt Gödels bahnbrechender Arbeit, die 1931 die moderne theoretische Informatik und die Theorie der Künstlichen Intelligenz (KI) begründete. Gödel sandte seinerzeit Schockwellen durch die akademische Gemeinschaft, als er die fundamentalen Grenzen des Rechnens, der KI, der Logik und der Mathematik selbst aufzeigte. Dies hatte enorme Auswirkungen auf Wissenschaft und Philosophie des 20. Jahrhunderts.

          Geboren in Brünn (heute Brno), war Gödel 25 Jahre alt, als er seine Arbeit in Wien verfasste. Im Zuge seiner Studien entwarf er eine universelle Sprache zur Codierung beliebiger formalisierbarer Prozesse. Sie beruht auf den ganzen Zahlen und erlaubt, sowohl Daten darzustellen, etwa Axiome für die Grundrechenarten und beweisbare Lehrsätze (Theoreme), als auch Programme, zum Beispiel beweiserzeugende Reihen von Operationen auf den Daten. Insbesondere gestattet sie, das Verhalten eines beliebigen digitalen Computers in axiomatischer Form zu formalisieren. Gödel konstruierte berühmte, selbstbezügliche, unentscheidbare formale Aussagen, die implizieren, dass ihr Wahrheitsgehalt nicht durch eine Rechnung ermittelbar ist.

          Damit identifizierte er letztlich fundamentale Grenzen des algorithmischen Theorembeweisens, des Rechnens und jeder Art rechnender KI. Manche missverstanden sein Ergebnis sogar und dachten, er hätte gezeigt, dass der Mensch der KI überlegen sei. In der Tat beschäftigte sich ein Großteil der frühen KI der Vierziger- bis Siebzigerjahre mit Theorembeweisen und Deduktion im Gödel-Stil (im Gegensatz zum induktiven Ansatz des heute dominanten maschinellen Lernens). Dabei gelang es bis zu einem gewissen Grade, menschliche Spezialisten durch schlussfolgernde Expertensysteme zu unterstützen.

          Leibniz, Frege, Zuse, Turing

          Wie fast alle großen Wissenschaftler stand Gödel auf den Schultern anderer. Er kombinierte Georg Cantors berühmten Diagonalisierungstrick aus dem Jahre 1891 (der zeigte, dass es verschiedene Sorten der Unendlichkeit gibt) mit grundlegenden Einsichten von Gottlob Frege, der im Jahr 1879 die erste formale Sprache vorstellte, sowie von Thoralf Skolem, der im Jahr 1923 primitiv rekursive Funktionen einführte (das sind Grundbausteine des Berechenbaren), sowie von Jacques Herbrand, der die Grenzen von Skolems Ansatz erkannte. Diese Arbeiten erweiterten ihrerseits bahnbrechende Ideen, die schon viel früher der Universalgelehrte und „erste Informatiker“ Gottfried Wilhelm Leibniz hatte.

          Leibniz’ „Calculemus!“ war ein prägendes Zitat der Aufklärung: „Käme es zwischen Philosophen zur Kontroverse, so bräuchten sie nicht mehr zu streiten als Buchhalter. Sie müssten sich nur mit ihren Bleistiften und Schiefertafeln hinsetzen und zueinander sagen [...]: Lasst uns rechnen!“ Im Jahr 1931 zeigte Gödel jedoch, dass es fundamentale Grenzen dessen gibt, was durch Rechnen entscheidbar ist.

          Im Jahre 1935 leitete dann Alonzo Church ein Korollar des Gödel’schen Ergebnisses ab: Das Entscheidungsproblem hat keine allgemeine Lösung. Dazu verwendete er seine alternative universelle Sprache namens Untyped Lambda Calculus, welche die Grundlage der einflussreichen Programmiersprache LISP bildet. Im Jahr 1936 wiederum stellte Alan Turing ein weiteres universelles Modell vor: die Turing-Maschine. Damit leitete er das oben erwähnte Ergebnis abermals ab. Im selben Jahr 1936 veröffentlichte auch Emil Post ein weiteres unabhängiges Universalmodell des Rechnens. Heute kennen wir viele solcher Modelle. Angeblich war es aber Turings Arbeit, die Gödel von der Universalität seines eigenen Ansatzes überzeugte.

          F.A.Z. Newsletter Deutschland startet durch

          Donnerstags um 12.00 Uhr

          ANMELDEN

          Viele von Gödels Befehlssequenzen waren Aneinanderreihungen von Multiplikationen von codierten Speicherinhalten mit ganzen Zahlen. Gödel kümmerte sich nicht darum, dass die rechnerische Komplexität solcher Multiplikationen tendenziell mit der Speichergröße zunimmt. In ähnlicher Weise ignorierte auch Church die kontextabhängige raumzeitliche Komplexität der grundlegenden Operationen seiner Algorithmen – der Rechenaufwand, der dabei zur Ausführung einer bestimmten Operation betrieben werden muss, ist nicht von vorneherein beschränkt.

          Weitere Themen

          So funktionieren NFTs Video-Seite öffnen

          Digitaler Echtheitsnachweis : So funktionieren NFTs

          Non-Fungible Tokens (NFTs) werden immer beliebter. Sie spielen etwa beim Handel mit digitaler Kunst eine Rolle. Die Videografik erklärt, was hinter dem digitalen Echtheitszertifikat steckt und wie es funktioniert.

          Warum es die Schüler am härtesten getroffen hat

          Hanks Welt : Warum es die Schüler am härtesten getroffen hat

          Es gibt Politiker, die behaupten: Inzwischen sei für die Schüler alles wieder gut. Dabei sind die Folgen der Schulschließungen noch gar nicht absehbar. Besonders für Nicht-Akademikerkinder werden sie vermutlich dramatisch sein.

          Topmeldungen

          Lars Klingbeil (links), Vorsitzender der SPD, und Saskia Esken, Vorsitzende der SPD, äußern sich am 20. Dezember 2021 bei einer Pressekonferenz nach der konstituierenden Sitzung des Parteivorstandes im Willy-Brandt-Haus in Berlin.

          Trotz Wahlerfolgs : Die SPD verliert weiter rasant Mitglieder

          Nach dem Wahlerfolg bei der Bundestagswahl traten der Partei im September zwar mehr Neumitglieder bei als in allen anderen Monaten des Jahres. Aber sie konnten den abermaligen Verlust von etwa fünf Prozent der Mitgliedschaft nicht ausgleichen.

          Novak Djokovics Ausweisung : Schluss mit dem Ego

          Nach dem Entzug des australischen Visums für den serbischen Tennis-Star bleibt zwar ein schaler Nachgeschmack, aber für den eigenen Schaden ist er, wohl auch entsetzlich schlecht beraten, selbst verantwortlich.
          Ein Militärangehöriger am 9. Dezember 2021 bei Sentianivka in der Ostukraine

          Ukraine-Krise : Plant Russland eine False-Flag-Operation?

          Washington erhebt detaillierte Vorwürfe gegen Moskau. Und der Kreml gibt erstmals offen zu, dass der jüngste Truppenaufmarsch an der Grenze zur Ukraine dazu dient, Putins Forderungen nach „Sicherheitsgarantien“ durchzusetzen.