FOM: Godel, f.o.m.

Martin Davis martin at
Fri Jan 21 14:03:35 EST 2000

At 12:36 AM 1/21/00 -0800, Matt Insall wrote:

>I tend to agree with this type of reasoning about the history of computers
>and their programming.  Even if one does not strictly consider Gödel to have
>invented Computer Science, one must concede that it was Gödel and his
>contemporary Mathematicians who invented that discipline, a fairly long time
>before the first digital computer was built.  I have had disagreements with
>Computer Scientists and Engineers about this:  Some claim that Computer
>Science began as an Engineering discipline.  These people, I contend, are
>not looking far enough back in the history of their subject, and are
>neglecting the significance of foundational studies (to use Professor
>Friedman's term).
I not only agree, but have written a book for the general public (out later 
this year) pushing this idea very hard. Look for THE UNIVERSAL COMPUTER: 

My chapter on Goedel does discuss the sense in which he was a computer 
programmer before there were computers:

"The keystone in Gödel's proof of the existence of undecidable
propositions is the fact that provability in PM [Principia Mathematica] can be
expressed in PM itself. Gödel knew very well that he would be
presenting his revolutionary results to a highly skeptical audience,
and he wanted to eliminate any doubt. Thus he faced the problem of
breaking down complex operations on the codes of the strings of
symbols corresponding to the axioms and rules of inference of
viewed from the {\em outside}, and transforming them into
expressions written in the symbolic language of . To solve
this problem, Gödel created what amounted to a special language in
which the operations needed could be developed in a step-by-step
fashion. Each step consisted of a definition of an operation
on numbers that, via the code Gödel was using, corresponded to a
parallel operation on expressions of PM. The definitions were
expressed in Gödel's special language in terms of items that had
already been defined in previous steps. The special language was so
designed that operations introduced by such a definition were
guaranteed to be appropriately expressible inside PM. "

And in a footnote to this paragraph:

"The programming languages that are mainly in use in the
software industry (like C and FORTRAN) are usually described as being
{\em imperative}. This is because the successive lines of programs
written in these languages can be thought of as {\em commands} to be
executed by the computer. Object oriented languages like C++ are also
imperative. In the so-called {\em functional} programming languages
(like LISP) the lines of a program are definitions of operations.
Rather than telling the computer what to do, they {\em define} what
it is that the computer is to provide.  Gödel's special language is
very much like a functional programming language."


                           Martin Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at
                          (Add 1 and get 0)

More information about the FOM mailing list