https://www.faz.net/aktuell/wirtschaft/digitec/mathematik-als-kurt-goedel-die-grenzen-des-berechenbaren-entdeckte-17388864.html

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.

          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.

          Turing und Post hingegen übernahmen die traditionelle, reduktionistische, minimalistische, binäre Sichtweise des Rechnens. Ihre Maschinenmodelle erlaubten nur sehr einfache elementare Anweisungen mit konstanter Komplexität, so wie Leibniz’ frühes binäres Maschinenmodell und Konrad Zuses ebenfalls im Jahr 1936 eingereichte Patentanmeldung.

          Der Gödel-Preis für theoretische Informatik ist nach Gödel benannt. Der derzeit lukrativere ACM A. M. Turing Award wurde im Jahre 1966 für Beiträge „von dauerhafter und großer technischer Bedeutung für das Gebiet der Informatik“ geschaffen. Kurioserweise erhielt Gödel selbst ihn nie, obwohl er nicht nur die Grundlagen der modernen Informatik legte, sondern auch ihr berühmtestes offenes Problem (P=NP?) in einem Brief an John von Neumann schon im Jahr 1956 vorstellte.

          Wissen war nie wertvoller

          Lesen Sie jetzt F+ 30 Tage kostenlos und erhalten Sie Zugriff auf alle Artikel auf FAZ.NET.

          JETZT F+ LESEN

          Die formalen Modelle von Gödel (1931-34), Church (1935), Turing (1936) und Post (1936) waren theoretische Stift- & Papierkonstrukte, die sich nicht direkt als Grundlage für praktische Computer eignen. Bemerkenswerterweise stammt Konrad Zuses Patentanmeldung für den ersten praktischen programmgesteuerten Allzweckcomputer ebenfalls aus dem Jahre 1936. Sie beschreibt allgemeine digitale Schaltungen.

          Darauf aufbauend stellte Zuse im Jahr 1941 schließlich die Z3 fertig, den ersten praktischen, funktionierenden, programmierbaren Allzweckrechner der Welt. Ignoriert man die unvermeidlichen Speicherbeschränkungen eines jeden physikalischen Computers, war die Z3 tatsächlich universell im „modernen“ Sinne von Gödel, Church, Turing und Post – einfache arithmetische Tricks kompensieren das Fehlen der bei Programmierern beliebten expliziten bedingten Sprunganweisung „if … then … else …“.

          Natürlich ist die praktische KI viel älter als Gödels theoretische Analyse ihrer fundamentalen Grenzen. Im Jahr 1914 baute der Spanier Leonardo Torres y Quevedo einen funktionierenden Schach-Endspieler. Noch Jahrzehnte später beeindruckte die Maschine, als sie im Jahr 1951 gegen den KI-Pionier Norbert Wiener auf der Pariser Konferenz spielte, welche heute oft als die erste KI-Konferenz überhaupt angesehen wird — obwohl der Begriff „Künstliche Intelligenz“ erst im Jahr 1956 auf einer anderen Konferenz in Dartmouth von John McCarthy geprägt wurde. Tatsächlich nannte man 1951 vieles von dem, was heute als KI bezeichnet wird, noch Kybernetik, mit einem Schwerpunkt vergleichbar dem der modernen KI basierend auf neuronalen Netzen.

          Ebenso sollte erwähnt werden, dass die praktische Informatik viel älter ist als Gödels Grundlagen der theoretischen Informatik. Die erste bekannte praktische programmierbare Maschine war im 1. Jahrhundert ein automatisches Theater des Heron von Alexandria. Die Energiequelle seines programmierbaren Automaten bestand aus einem Fallgewicht, das eine Schnur zog, die um die Stifte eines drehbaren Zylinders gewickelt war. Komplexe Befehlssequenzen zur Steuerung von Türen und Puppen über mehrere Minuten hinweg wurden durch komplexe Umwicklungen kodiert.

          Gödel wurde oft als größter Logiker seit Aristoteles bezeichnet. Am Ende des letzten Jahrtausends bezeichnete das Time Magazine ihn als einflussreichsten Mathematiker des 20. Jahrhunderts, obwohl manche Mathematiker meinen, sein wichtigstes Ergebnis drehe sich vor allem um Logik und Berechenbarkeit und weniger um Mathematik. Andere nennen es die grundlegende Einsicht der theoretischen Informatik, einer Disziplin, die damals noch nicht offiziell existierte – aber durch Gödels Bemühungen ins Leben gerufen wurde.

          (Zu einer englischen Fassung geht es hier entlang:)

          Jürgen Schmidhuber ist wissenschaftlicher Direktor am Schweizer KI-Forschungsinstitut IDSIA und zählt zu den führenden KI-Forschern der Welt.

          Weitere Themen

          Topmeldungen

          Die Strafkolonie im russischen Pokrow. Bisher wird Alexej Nawalnyj hier festgehalten.

          Strengere Haft : Nawalnyjs Name auf der Terrorliste

          Alexej Nawalnyj bleibt als politischer Gefangener ein lauter Regime-Kritiker. Die russische Justiz verschärft nun seine Haftbedingungen – und isoliert ihn noch stärker.
          Ein Mann hält ein Baby auf dem Arm.

          Geburt des ersten Kindes : Warum junge Väter immer älter werden

          Männer sind im Schnitt bei der Geburt ihres ersten Kindes deutlich älter als Frauen. Werden sie auch in Zukunft immer älter? Die Gründe, warum die Deutschen immer später im Leben eine Familie gründen, sind gut erforscht.

          Newsletter

          Immer auf dem Laufenden Sie haben Post! Die wichtigsten Nachrichten direkt in Ihre Mailbox. Sie können bis zu 5 Newsletter gleichzeitig auswählen 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.
          Kapitalanalge
          Erzielen Sie bis zu 5% Rendite
          Sprachkurse
          Lernen Sie Englisch
          Immobilienbewertung
          Verkaufen Sie zum Höchstpreis
          Zertifikate
          Ihre Weiterbildung im Projektmanagement