
In 1931,
just a few years after Julius Lilienfeld patented the
transistor,
Kurt Gödel (or `Goedel' but not `Godel') layed the
foundations of theoretical computer
science with his work on universal formal languages and the limits
of proof and computation.
He constructed formal systems allowing
for selfreferential statements that talk about themselves, in
particular, about whether they can be derived from an enumerable set of given
axioms through a computational theorem proving procedure. Gödel
went on to construct statements that claim their own unprovability,
to demonstrate that traditional math is either flawed in a certain
algorithmic sense or contains unprovable but true statements.
Gödel's
incompleteness result is widely regarded as the most
remarkable achievement of 20th century mathematics, although some
mathematicians say it is logic, not math, and others call it the
fundamental result of theoretical computer science (reformulated by Church & Post &
Turing around 1936), a discipline
that did not yet officially exist back then but was effectively
created through Gödel's work. It had enormous impact
not only on computer science but also on philosophy and other fields.
 
Bio highlights:
1906:
born in Bruenn.
1923:
Vienna University.
1931:
most famous paper at age 25 [1].
1953:
IAS, Princeton.
1978:
Starves himself to death.
[1]. Kurt Gödel.
Ueber formal unentscheidbare Saetze der Principia Mathematica
und verwandter Systeme I. Monatshefte fuer Mathematik und Physik,
38:173198, 1931.
 


Since Gödel's exhibition of the fundamental limits of proof and
computation, and Konrad Zuse's
subsequent construction of the first
programmable computer (19351941),
there has been a lot of work on specialized algorithms
solving problems taken from more or less general problem classes.
Apparently, however, until recently
one remarkable fact has escaped the attention of computer
scientists: it is possible to use selfreferential proof systems to
build optimally efficient yet conceptually very simple
universal problem solvers: the
Gödel machines (2003).
 
