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

          Die Faltung der Welt

          Klimakrise : Die Faltung der Welt

          Wachstum und Vielfalt in einer endlichen Welt: Wie sich mit dem mathematischen Blick auf die bestehenden Probleme die Klimakrise lösen ließe. Ein Gastbeitrag.

          Topmeldungen

          Ein Airbus der Lufthansa landet im November 2020 auf dem Berliner Flughafen Tegel.

          Klimaschutz : Rettet die Inlandsflüge

          Ein Verbot von Inlandsflügen, wie es zuletzt in Frankreich beschlossen wurde, ist der falsche Weg zum Klimaschutz. Es gibt andere, bessere Möglichkeiten.
          Wichtiger Wert: Wie viele Covid-Kranke auf  Intensivstationen liegen.

          Kennwerte der Corona-Pandemie : Neue Zahl, neues Glück?

          Die Zahl der Neuinfektionen bestimmte in den vergangenen Monaten den Alltag. Damit soll nun Schluss sein. Doch die neuen Pläne der Regierung gehen Wissenschaftlern nicht weit genug – denn Entscheidendes wurde in Deutschland versäumt.
          Am 18. Juni in Teheran: Ebrahim Raissi winkt den Medien zu, nachdem er seine Stimme in einem Wahllokal abgegeben hat. Die Wahl gewann er.

          Irans neuer Präsident : Schlächter und Schneeflocke

          Nächste Woche tritt Ebrahim Raissi sein Amt als iranischer Präsident an. Mit ihm zerbricht der Mythos vom reformfähigen Regime. Weiß der Westen, mit wem er es zu tun bekommt? Ein Gastbeitrag.

          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.