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

          Topmeldungen

          Xi Jinping ist auf einem großen Bildschirm zu den Feierlichkeiten des 100. Jahrestag der Gründung der Kommunistischen Partei zu sehen.

          Chinas kalter Krieg : Kontrolle ist das Ziel

          Fast täglich schickt die Regierung in Peking die Aktienkurse chinesischer Tech-Unternehmen auf Talfahrt. Dahinter steckt der Glaube, der Kampf gegen Amerika sei nur mit einer Rückkehr zu kommunistischer Politik zu gewinnen.
          Menschen in Berlin warten in der Schlange eines mobilen Impfteams.

          Coronavirus in Deutschland : Sieben-Tage-Inzidenz steigt auf 17

          Das Robert Koch-Institut meldet mit 2454 neuen Corona-Fällen abermals mehr Ansteckungen als vor einer Woche. Der Lagebericht zeigt zudem, in welchen Urlaubsländern es zu den meisten Infektionen kommt.
          Armin Laschet am 20. Juli in Bad Münstereifel

          CSU in Sorge : Kann das mit Laschet gut gehen?

          Die Werte für die Union fallen, die Nervosität wächst. In CDU und CSU hält mancher Armin Laschet für zu passiv. Und Markus Söder feuert wieder. Denn es gibt ein Schreckensszenario.
          „Die in Brüssel mögen uns nicht“, behauptet Viktor Orban. Viele zu Hause glauben ihm.

          Ungarn und die EU : „Die in Brüssel mögen uns nicht“

          Der niederländische Regierungschef und der Außenminister Luxemburgs stellen Ungarns EU-Mitgliedschaft in Frage. Ministerpräsident Orbán kann sich freuen. Er sagt ohnehin, „die in Brüssel“ wollten die Ungarn eigentlich nicht.

          Newsletter

          Immer auf dem Laufenden Sie haben Post! Abonnieren Sie unsere FAZ.NET-Newsletter und wir liefern die wichtigsten Nachrichten direkt in Ihre Mailbox. Es ist ein Fehler aufgetreten. Bitte versuchen Sie es erneut.
          Vielen Dank für Ihr Interesse an den F.A.Z.-Newslettern. Sie erhalten in wenigen Minuten eine E-Mail, um Ihre Newsletterbestellung zu bestätigen.