About
Kurt Gödel (1906–1978) was born in Brünn, Austria-Hungary (now Brno), and studied in Vienna, where he took part in the Vienna Circle and learned his logic from Rudolf Carnap and Hans Hahn. His 1929 dissertation proved the completeness theorem for first-order logic; two years later his incompleteness theorems showed that any consistent formal system rich enough for arithmetic contains true statements it cannot prove, and cannot prove its own consistency — ending the hope that all of mathematics could be secured inside one complete, self-certifying system. He later showed that the axiom of choice and the continuum hypothesis cannot be disproved from the standard axioms of set theory, and found rotating-universe solutions to Einstein's equations (1949). Fleeing Nazi-annexed Austria, he joined the Institute for Advanced Study in Princeton in 1940, where Einstein said he came to the Institute late in life merely for 'the privilege of walking home with Gödel'; convinced his food was poisoned, he starved to death in 1978. In a 1956 letter to John von Neumann he asked whether finding mathematical proofs could be mechanized efficiently — the question now called P versus NP — and arguments about whether a mind can be captured by a formal system still run through his theorems.
Key Contributions
- Proved the completeness theorem for first-order logic in his 1929 doctoral dissertation
- Proved the incompleteness theorems (1931): consistent formal systems containing arithmetic leave true statements unprovable, and cannot prove their own consistency
- Showed that the axiom of choice and the continuum hypothesis cannot be disproved from the standard axioms of set theory
- Found rotating-universe solutions to Einstein's field equations (1949) that permit closed timelike paths
- Asked von Neumann in a 1956 letter whether theorem-proving could be done in linear or quadratic time — an early statement of P versus NP
Connections
Douglas Hofstadter
InfluencedProfessor of Cognitive Science, Indiana University
Gödel, Escher, Bach takes Gödel's construction — a formal system that, through numbering, comes to make statements about itself — and turns it into a theory of the self: consciousness as a strange loop emerging from meaningless lower-level activity. Hofstadter insisted the book is not about mathematics, art and music but about how a mind arises from neurons. Gödel showed self-reference can be built from mechanism; Hofstadter bet that is exactly what a self is.
en.wikipedia.org · en.wikipedia.org · youtube.com
Alan Turing
InfluencedMathematician & Computer Science Pioneer
Turing learned of Gödel's 1931 incompleteness proof from Max Newman's lectures in 1935, and his 1936 answer to Hilbert's decision problem used the same diagonal move to show that no machine can settle every question about what machines will do. Gödel himself was convinced by Turing's analysis that an absolute concept of mechanical computability had been found. Turing's 1938 ordinal logics then asked what a mind is doing when it sees a Gödel sentence to be true that the system cannot prove — the question every argument about machine minds still circles.
plato.stanford.edu · en.wikipedia.org
John von Neumann
In conversationMathematician & Computer Architecture Pioneer
Von Neumann heard Gödel announce the first incompleteness theorem at Königsberg in September 1930, wrote within a month to point out the second — that such systems cannot prove their own consistency — and found Gödel had already proved it; he acknowledged the priority and stopped working on foundations altogether. Twenty-six years later Gödel wrote to him asking whether finding proofs could be done in linear or quadratic time, which would let mathematical discovery be automated: the P versus NP question, posed before it had a name. Von Neumann once said he would be forgotten while Gödel was remembered with Pythagoras.
en.wikipedia.org · plato.stanford.edu · en.wikipedia.org
Jürgen Schmidhuber
InfluencedDirector, KAUST AI Initiative & Scientific Director, IDSIA
Schmidhuber's Gödel machine (2003) is built directly on Gödel's self-referential formulas: a problem solver that rewrites any part of its own code once it has proved the rewrite will help. Gödel's own theorem sets its limit — a self-improver bound to proof must pass over every improvement it cannot prove useful. The Darwin Gödel Machine kept the name and traded the proofs for empirical benchmarks, because proving most changes beneficial is impossible in practice — its own comment on where that limit leaves us.
arxiv.org · en.wikipedia.org · youtube.com · arxiv.org
