90 Jahre her

Als Kurt Gödel die Grenzen des Berechenbaren entdeckte

Von Jürgen Schmidhuber
16.06.2021
, 11:24
Hat die Mathematik durcheinandergewirbelt: Kurt Gödel (das Bild zeigt ihn im Jahr 1935)
Über eine wegweisende Leistung, die einst die Mathematik durchrüttelte – und letztlich die theoretische Informatik begründete. Ein Gastbeitrag.
ANZEIGE

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.

ANZEIGE

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.

ANZEIGE

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.

ANZEIGE

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.

ANZEIGE

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.

ANZEIGE

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.

Quelle: F.A.Z.
  Zur Startseite
Verlagsangebot
Verlagsangebot
ANZEIGE