Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03122.jsonl.gz/2353

'

1931: Kurt Gödel, Vater der theoretischen Informatik, entdeckt die Grenzen des Berechenbaren und der künstlichen Intelligenz
Im Jahre 2021 feiern wir den 90. Jahrestag von Kurt Gödels bahnbrechender Arbeit, die 1931 den Grundstein für die moderne theoretische Informatik und die Theorie der künstlichen Intelligenz (KI) legte. Gödel sandte Schockwellen durch die akademische Gemeinschaft, als er die fundamentalen Grenzen des Theorembeweisens, des Rechnens, der KI, der Logik und der Mathematik selbst aufzeigte. Dies hatte enorme Auswirkungen auf Wissenschaft und Philosophie des 20. Jahrhunderts. Noch ein Jahrzehnt bis zur Gödel-Jahrhundertfeier 2031!
In den frühen 1930er Jahren entdeckte Kurt Gödel fundamentale Schranken der Berechenbarkeit, des Theorembeweisens und der Logik im Allgemeinen.[GOD][GOD34][GOD21,a,b] Damit wurde er zum Begründer der modernen theoretischen Informatik und der KI-Theorie.
Gödel entwarf eine universelle Sprache zur Kodierung beliebiger formalisierbarer Prozesse(1931-34).[GOD][GOD34] Sie beruht auf den ganzen Zahlen und erlaubt, sowohl Daten (z.B. Axiome und Theoreme) als auch Programme (z. B. beweiserzeugende Sequenzen von Operationen auf den Daten) darzustellen.[VAR13] Insbesondere gestatten seine sogenannte Gödelnummern, das Verhalten eines beliebigen digitalen Computers in axiomatischer Form zu formalisieren (dies inspirierte auch meine viel spätere selbstreferenzielle Gödel-Maschine[GM6]).
Gödel konstruierte famoserweise formale Aussagen, die über die Berechnung anderer formaler Aussagen sprechen—insbesondere selbstreferentielle unentscheidbare Aussagen, die implizieren, dass ihr Wahrheitsgehalt nicht ermittelt werden kann durch einen Lehrsatzbeweiser, der systematisch alle möglichen Theoreme (z.B.: "23+19=42") aus einer aufzählbaren Menge von Axiomen herleitet, die beschreiben, wie die Grundrechenarten funktionieren. Damit identifizierte er fundamentale Grenzen des algorithmischen Theorembeweisens, des Rechnens und jeder Art rechnender KI.[GOD] Manche missverstanden sein Ergebnis sogar und dachten, er hätte gezeigt, dass der Mensch der KI überlegen sei.[BIB3] In der Tat beschäftigte sich ein Großteil der frühen KI der 1940er-70er Jahre mit Theorembeweisern[ZU48][NS56] 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.
Wie fast alle großen Wissenschaftler stand Gödel auf den Schultern anderer. Er kombinierte Georg Cantors berühmten Diagonalisierungstrick aus dem Jahre 1891[CAN] (der zeigte, dass es verschiedene Sorten der Unendlichkeit gibt) mit grundlegenden Einsichten von Gottlob Frege,[FRE] der 1879 die erste formale Sprache vorstellte, sowie von Thoralf Skolem,[SKO23] der 1923 primitiv rekursive Funktionen einführte (das sind Gundbausteine des Berechenbaren), sowie von Jacques Herbrand,[GOD86] der die Grenzen von Skolems Ansatz erkannte. Diese Arbeiten erweiterten ihrerseits die formale Algebra des Denkens (1686) von Gottfried Wilhelm Leibniz,[L86][WI48] welche deduktiv äquivalent[LE18] ist zur späteren Booleschen Algebra[BOO] von 1847. Leibniz, vielleicht der "Vater der Informatik",[LEI21,a,b] wurde oft als "erster Computerwissenschaftler" bezeichnet,[LA14] und sogar als "klügster Mann, der je gelebt hat".[SMO13] 1679 beschrieb er Prinzipien von Binärcomputern, die durch Lochkarten gesteuert werden.[L79][LA14][HO66][L03][IN08][SH51][LEI21,a,b] 1673 entwarf er die erste Maschine (den Schrittzähler), die alle vier Grundrechenarten ausführen konnte, und die erste mit einem internen Speicher.[BL16] Sie wies hinaus über die ersten automatischen, getriebebasierten, datenverarbeitenden Rechenmaschinen von Wilhelm Schickard (1623) und Blaise Pascal (1642). Leibniz war zudem nicht nur der erste, der die Integralrechnung veröffentlichte,[L84] sondern verfolgte auch das überaus ehrgeizige Projekt der Klärung aller möglichen Fragen durch Rechnen. Seine durch den Gelehrten Ramon Llull des 13. Jahrhunderts[LL7] inspirierten Ideen zu einer universellen Sprache und einem allgemeinen Kalkül für das Denken (Characteristica Universalis & Calculus Ratiocinator[WI48]) waren höchst einflussreich. Leibniz' "Calculemus!" ist 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!"[RU58] 1931 zeigte Gödel jedoch, dass es fundamentale Grenzen dessen gibt, was durch Rechnen entscheidbar ist.[GOD][MIR](Sec. 18)
1935 leitete Alonzo Church ein Korollar des Gödelschen Ergebnis ab, welches zeigte, dass Hilbert & Ackermanns berühmtes Entscheidungsproblem keine allgemeine Lösung hat.[CHU] Dazu verwendete er seine alternative universelle Kodiersprache namens Untyped Lambda Calculus, welche die Grundlage der einflussreichen Programmiersprache LISP bildet.
Im Jahr 1936 stellte Alan Turing ein weiteres universelles Modell vor: die Turing-Maschine.[TUR] Damit leitete er das oben erwähnte Ergebnis erneut her.[T20](Sek. IV) Natürlich zitierte er sowohl Gödel als auch Church in seinem Aufsatz von 1936[TUR] (dessen Korrekturen 1937 erschienen). Im selben Jahr 1936 veröffentlichte Emil Post ein weiteres unabhängiges Universalmodell des Rechnens[POS] (auch er zitierte Gödel und Church). Heute kennen wir viele solcher Modelle. Nach Wang[WA74-96] war es allerdings Turings Arbeit (1936), die Gödel von der Universalität seines eigenen Ansatzes (1931-34) und dessen von Church (1935) überzeugte.
Haben Post[POS] und Turing[TUR] 1936 irgendetwas erreicht, das nicht vorher schon von Gödel[GOD][GOD34] (1931-34) und Church[CHU] (1935) erledigt worden war? Die Bedeutung eines scheinbar kleinen Unterschieds ihrer Ansätze stellte sich erst später heraus. Viele von Gödels Befehlssequenzen waren Aneinanderreihungen von Multiplikationen von zahlencodierten Speicherinhalten mit ganzen Zahlen. Gödel kümmerte sich nicht darum, dass die rechnerische Komplexität solcher Multiplikationen tendenziell mit der Speichergrösse zunimmt. In ähnlicher Weise ignorierte auch Church die raumzeitliche Komplexität der grundlegenden Operationen seiner Algorithmen—der Rechenaufwand, der 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 (1679)[L79][LA14][HO66] und Zuses ebenfalls 1936 eingereichte Patentanmeldung.[ZU36][ZUS21,a,b] Zwar nutzten sie dies damals nicht aus—Turing verwendete sein ziemlich ineffizientes Modell 1936 nur, um die Erkenntnisse von Gödel und Church zu den Grenzen der Berechenbarkeit umzuformulieren. Später jedoch machte die Einfachheit dieser Modelle sie zu einem geeigneten Werkzeug für theoretische Studien der Rechenkomplexität. (Auch ich habe sie gerne für den Fall unendlicher Berechnungen verwendet und verallgemeinert.[ALL2])
Der Gödel-Preis für theoretische Informatik ist nach Gödel benannt. Der derzeit lukrativere ACM A. M. Turing Award wurde 1966 für Beiträge "von dauerhafter und großer technischer Bedeutung für das Gebiet der Informatik" geschaffen. Es ist lustig—und gleichzeitig peinlich—dass Gödel (1906-1978) nie einen erhielt, obwohl er nicht nur die Grundlagen der "modernen" Informatik legte, sondern auch ihr berühmtestes offenes Problem "P=NP?" in seinem Brief an John von Neumann (1956) vorstellte.[GOD56][URQ10]
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[ZU36- 38][Z36][RO98][ZUS21,a,b] für den ersten praktischen programmgesteuerten Allzweckcomputer ebenfalls aus dem Jahre 1936. Sie beschreibt allgemeine digitale Schaltungen (und geht Claude Shannons 1937er Arbeit zum digitalen Schaltungsentwurf voraus[SHA37]). Darauf aufbauend stellte Zuse 1941 schliesslich 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..."[RO98] Zuse schuf in den frühen 1940ern auch die erste höhere Programmiersprache (Plankalkül).[BAU][KNU] 1945 wandte er sie auf Schach an,[KNU] 1948 aufs Theorembeweisen.[ZU48]
Natürlich ist praktische KI viel älter ist als Gödel's theoretische Analyse der fundamentalen Grenzen der KI. 1914 baute der Spanier Leonardo Torres y Quevedo als wohl erster Pionier der praktischen KI des 20. Jahrhunderts einen funktionierenden Schach-Endspieler (damals galt Schach noch als eine Tätigkeit, die intelligenten Wesen vorbehalten war). Noch Jahrzehnte später beeindruckte die Maschine, als sie 1951 gegen den KI-Pionier Norbert Wiener auf der Pariser Konferenz spielte,[AI51][BRO21] [BRU1-4] welche heute oft als die erste KI-Konferenz überhaupt angesehen wird—obwohl der Begriff "KI" erst 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.[DL1-2][DEC]
Ebenso sollte erwähnt werden, dass die praktische Informatik viel älter ist als Gödel's Grundlagen der theoretischen Informatik (vgl. auch obige Ausführungen zu Leibniz). Die erste bekannte praktische programmierbare Maschine war im 1. Jahrhundert ein automatisches Theater[SHA7a][RAU1] des Heron von Alexandria (der anscheinend auch die erste bekannte funktionierende Dampfmaschine baute—die Aeolipile). 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. Der aus dem 9. Jahrhundert stammende Musik-Automat der Brüder Banu Musa in Bagdad war vielleicht die erste Maschine mit gespeichertem Programm.[BAN][KOE1] Stifte auf einem rotierenden Zylinder stellten Anweisungen für eine dampfgetriebene Flöte dar—vergleiche Al-Jazaris programmierbare Trommelmaschine von 1206.[SHA7b] Die ersten kommerziellen programmgesteuerten Maschinen (lochkartenbasierte Webstühle) entstanden in Frankreich um 1800 durch Joseph-Marie Jacquard und andere—vielleicht die ersten "modernen" Programmierer, die die erste industrielle Software der Welt schrieben. Sie inspirierten Ada Lovelace und ihren Mentor Charles Babbage (UK, um 1840), der sich vergeblich bemühte, einen nicht-binären, dezimalen, programmierbaren Allzweckrechner zu bauen. Der erste funktionstüchtige Allzweckrechner, der nicht von Zuse selbst stammte (1941),[RO98] war Howard Aikens dezimaler MARK I (US, 1944).
Gödel wurde oft als größter Logiker seit Aristoteles bezeichnet.[GOD10] Am Ende des letzten Jahrtausends nannte TIME Magazine ihn den einflussreichsten Mathematiker des 20. Jahrhunderts, obwohl manche Mathematiker meinen, sein wichtigstes Ergebnis drehe sich vor allem um Logik und Berechenbarkeit, weniger um Mathematik. Andere nennen es die grundlegende Einsicht der theoretischen Informatik, einer Disziplin, die damals noch nicht offiziell existierte, aber durch Gödel's Bemühungen ins Leben gerufen wurde. Das mit dem Pulitzer-Preis ausgezeichnete populäre Buch "Gödel, Escher, Bach"[H79] trug dazu bei, Generationen junger Menschen für ein Informatikstudium zu begeistern.
Im Jahr 2021 feiern wir nicht nur das 90-jährige Jubiläum Gödel's bahnbrechender Arbeit (1931), sondern auch den 80. Jahrestag des des weltweit ersten funktionalen programmgesteuerten Allzweckcomputers von Zuse (1941). Es scheint kaum glaubhaft, dass binnen nicht mal eines Jahrhunderts etwas, das einst nur in den Köpfen solcher Titanen lebte, zu einem unverzichtbaren Teil der modernen Gesellschaft geworden ist. Die Welt schuldet diesen Wissenschaftlern viel. Noch 10 Jahre bis zur Gödel-Hundertjahrfeier 2031, 20 bis zur Zuse-Hundertjahrfeier 2041, und 1/4 Jahrhundert bis zur 4. Leibniz-Hundertjahrfeier 2046! Genug Zeit, um entsprechende Paraden zu planen.