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.
Danksagung
Dank an Moshe Vardi, Herbert Bruderer, Jack Copeland, Wolfgang Bibel, Teun Koetsier, Scott Aaronson, Dylan Ashley, Sebastian Oberhoff, Kai Hormann, und weiteren Gutachtern für nützliche Kommentare. Da sich Wissenschaft um Selbstkorrektur dreht, lassen Sie es mich unter juergen@idsia.ch wissen, falls Sie irgendwo einen Fehler finden. Der Inhalt dieses Artikels darf für erzieherische und nicht-kommerzielle Zwecke verwendet werden, auch für Wikipedia und ähnliche Seiten, unter der "Creative Commons Namensnennung—Nicht-kommerziell—Weitergabe unter gleichen Bedingungen 4.0 International (CC BY-NC-SA 4.0) Lizenz".
Referenzen
[GOD]
K. Gödel. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik, 38:173-198, 1931.
In the early 1930s,
Gödel founded theoretical computer science. He identified fundamental limits of mathematics and theorem proving and computing and Artificial Intelligence.
[GOD34]
K. Gödel (1934).
On undecidable propositions of formal mathematical
systems. Notes by S. C. Kleene and J. B. Rosser on lectures
at the Institute for Advanced Study, Princeton, New Jersey, 1934, 30
pp. (Reprinted in M. Davis, (ed.), The Undecidable. Basic Papers on Undecidable
Propositions, Unsolvable Problems, and Computable Functions,
Raven Press, Hewlett, New York, 1965.)
Gödel introduced the first universal coding language.
[GOD56]
R. J. Lipton and K. W. Regan.
Gödel's lost letter and P=NP.
Link.
[GOD86]
K. Gödel.
Collected works Volume I: Publications 1929-36,
S. Feferman et. al., editors, Oxford Univ. Press, Oxford, 1986.
[GOD10]
V. C. Nadkarni.
Gödel, Einstein and proof for God. The Economic Times, 2010.
[URQ10]
A. Urquhart. Von Neumann, Gödel and complexity theory. Bulletin of Symbolic Logic 16.4 (2010): 516-530.
Link.
[BIB3]
W. Bibel (2003).
Mosaiksteine einer Wissenschaft vom Geiste. Invited talk at
the conference on AI and Gödel, Arnoldsheim, 4-6 April 2003.
Manuscript, 2003.
[CHU]
A. Church (1935). An unsolvable problem of elementary number theory. Bulletin of the American Mathematical Society, 41: 332-333. Abstract of a talk given on 19 April 1935, to the American Mathematical Society.
Also in American Journal of Mathematics, 58(2), 345-363 (1 Apr 1936).
First explicit proof that the Entscheidungsproblem (decision problem) does not have a general solution.
[TUR]
A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, 41:230-267. Received 28 May 1936. Errata appeared in Series 2, 43, pp 544-546 (1937).
2nd explicit proof that the Entscheidungsproblem (decision problem) does not have a general solution.
[POS]
E. L. Post (1936). Finite Combinatory Processes - Formulation 1. Journal of Symbolic Logic. 1: 103-105.
Link.
[WA74]
H. Wang (1974). From Mathematics to Philosophy, New York: Humanities Press.
[WA96]
H. Wang (1996). A Logical Journey: From Gödel to Philosophy, Cambridge, MA: MIT Press.
[H79]
Douglas R. Hofstadter (1979). Gödel, Escher, Bach: An Eternal Golden Braid. Basic Books, ISBN 0-465-02656-7, 1979.
[FRE] G. Frege (1879).
Begriffsschrift: eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle an der Saale: Verlag Louis Nebert.
[The first formal language / formal proofs—basis of modern logic and programming languages.]
[SKO23] T. Skolem (1923). Begründung der elementaren Arithmetik
durch die rekurrierende Denkweise ohne Anwendung scheinbarer
Veränderlichen mit unendlichem Ausdehnungsbereich. Skrifter utgit av
Videnskapsselskapet i Kristiania, I. Mathematisk-Naturvidenskabelig
Klasse 6 (1923), 38 pp.
[CAN]
G. Cantor (1891). Ueber eine elementare Frage der Mannigfaltigkeitslehre. Jahresbericht der Deutschen Mathematiker-Vereinigung, 1:75-78. [English translation: W. B. Ewald (ed.). From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, Volume 2, pp. 920-922. Oxford University Press, 1996.]
[L03]
G. Leibniz (1703). In: Explication de l'Arithmetique Binaire / Die Mathematischen Schriften, ed. C. Gerhardt, Berlin 1879, vol.7, p.223. English link.
Leibniz documented the binary arithmetics which allow for greatly simplifiying computing hardware and are employed by virtually all modern computers. Binary number encodings per se, however, seem to date back over 4000 years.
[L79]
G. Leibniz.
De Progressione dyadica Pars I. 15 March 1679.
Principles of binary computers governed by punch cards.
[L84]
G. Leibniz (1684).
Nova Methodus pro Maximis et Minimis.
First publication on infinitesimal calculus.
[L86]
G. Leibniz (1686). Generales Inquisitiones de analysi notionum et veritatum.
Also in
Leibniz: Die philosophischen Schriften VII, 1890, pp. 236-247; translated as "A Study in the Calculus of Real Addition" (1690) by G. H. R. Parkinson, Leibniz: Logical Papers—A Selection, Oxford 1966, pp. 131-144.
[LEI21] J. Schmidhuber (AI Blog, 2021). 375th birthday of Leibniz, founder of computer science.
[LEI21a]
J. Schmidhuber (2021). Der erste Informatiker. Wie Gottfried Wilhelm Leibniz den Computer erdachte.
(The first computer scientist. How Gottfried Wilhelm Leibniz conceived the computer.)
Frankfurter Allgemeine Zeitung (FAZ), 17/5/2021. FAZ online:
19/5/2021.
[LEI21b] J. Schmidhuber (AI Blog, 2021). 375. Geburtstag des Herrn Leibniz, dem Vater der Informatik.
[BOO]
George Boole (1847). The Mathematical Analysis of Logic, Being an Essay towards a Calculus of Deductive Reasoning.
London, England: Macmillan, Barclay, & Macmillan, 1847.
[LL7]
A. Bonner (2007). The art and logic of Ramon Llull. Brill Academic Pub, p. 290, 2007.
[RU58]
B. Russell (1958). The Philosophy of Leibniz. London: George Allen and Unwin, 1958.
[LE18]
W. Lenzen.
Leibniz and the Calculus Ratiocinator. Technology and Mathematics, pp 47-78, Springer, 2018.
[LA14]
D. R. Lande (2014).
Development of the Binary Number System and the Foundations of Computer Science. The Mathematics Enthusiast, vol. 11(3):6 12, 2014.
Link.
[BL16]
L. Bloch (2016). Informatics in the light of some Leibniz's works.
Communication to XB2 Berlin Xenobiology Conference.
[HO66]
E. Hochstetter et al. (1966): Herrn von Leibniz' Rechnung mit Null und Eins. Berlin: Siemens AG.
[IN08]
R. Ineichen (2008). Leibniz, Caramuel, Harriot und das Dualsystem. Mitteilungen der deutschen Mathematiker-Vereinigung. 16(1):12-15.
[SH51]
J. W. Shirley (1951). Binary Numeration before Leibniz. American Journal of Physics 19 (452-454).
[WI48]
N. Wiener (1948).
Time, communication, and the nervous system. Teleological mechanisms. Annals of the N.Y. Acad. Sci. 50 (4): 197-219.
Quote: "... the general idea of a computing machine is nothing but a mechanization of Leibniz's calculus ratiocinator."
[SMO13]
L. Smolin (2013). My hero: Gottfried Wilhelm von Leibniz. The Guardian, 2013.
Link.
Quote: "And this is just the one part of Leibniz's enormous legacy: the philosopher Stanley Rosen called him "the smartest person who ever lived"."
[T20] J. Schmidhuber (2020). Critique of 2018 Turing Award.
[HIN] J. Schmidhuber (2020). Critique of 2019 Honda Prize.
[GOD21] J. Schmidhuber (AI Blog, 2021). 90th anniversary celebrations: 1931: Kurt Gödel, founder of theoretical computer science, shows limits of math, logic, computing, and artificial intelligence. This was number 1 on Hacker News.
[GOD21a]
J. Schmidhuber (2021). Als Kurt Gödel die Grenzen des Berechenbaren entdeckte.
(When Kurt Gödel discovered the limits of computability.)
Frankfurter Allgemeine Zeitung, 16/6/2021.
[GOD21b]
J. Schmidhuber (AI Blog, 2021). 80. Jahrestag: 1931: Kurt Gödel, Vater der theoretischen Informatik, entdeckt die Grenzen des Berechenbaren und der künstlichen Intelligenz.
[ALL2]
J. Schmidhuber (2000).
Algorithmic theories of everything.
ArXiv:
quant-ph/ 0011122.
More.
See also:
Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit.
International Journal of Foundations of Computer Science 13(4):587-612, 2002.
