FOM: Godel, f.o.m.

Vaughan Pratt pratt at CS.Stanford.EDU
Fri Jan 21 13:47:43 EST 2000

From: Vladimir Sazonov <sazonov at>
>Here is not so much of contradiction because mathematics is just
>a kind of formal engineering. In a sense, computers as some
>(physically realized) formal systems belong to mathematics.

>From here it is only a short step to the inference that foundations
of computation is a branch of foundations of mathematics, so perhaps
something should be said about this.

It is true that a few computer science departments had their origins in
science departments rather than engineering.  For example Stanford's
computer science department was originally a department within
the School of Humanities and Sciences, spun off from mathematics.
Berkeley's computer science department began in the late 1960's in the
College of Letters and Science.  And Sydney University's Basser Computing
Department, was originally a department of Sydney's huge (7-department)
School of Physics within the Faculty of Science.

But most computer science departments began in electrical engineering,
and most of those that originated elsewhere have become primarily
engineering disciplines.

That is not to say however that they now belong to electrical engineering.

Certainly mathematicians have made important and fundamental contributions
not only to computer science but to computer engineering (von Neumann
for example).  But modern computer science is an astonishingly
vital subject in its own right.  While it owes much to its parents,
electrical engineering and mathematics, as well as to its teachers,
including physics, philosophy, psychology, and mechanical engineering,
that debt is an intellectual one only, not an indenture.

Computer science belongs to no one, it is its own subject.  And for
the past third of a century the responsibility for its foundations has
been taken neither by electrical engineers nor mathematicians but by
computer scientists.

There is more at stake here than a mere definition.  Mathematicians take
pride in exploring questions for their own sake.  Were computer science
to operate like mathematics, it would focus on internally well-motivated
questions and on perfecting the shape of mathematics like a sculptor
seeking the perfect human form.

Computer science is more like an engineering subject, in that while it
respects the independent interest of good questions, its most important
questions, whether practical or theoretical, have for the half-century
of our experience with usable computers found their driving force in
the constantly changing landscape of technology.

One may say that P=NP is really a mathematical question, but who would
have thought to even ask it had there been no users demanding better
performance?  The same holds for whether classical computation can
simulate quantum computation within polynomial time, a more recently
motivated question.  Networking in the 1980's inspired many knotty
synchronization problems in distributed computation, while the internet
of the 1990's has inspired search problems in enormous databases.
The imminent use of wireless to cut the Gordian knot of cables on your
desktop within the next three years will inspire yet further problems,
and so on.

You may grant that computer science is now independent but insist that
this newfound independence does not change the basic nature of the
computer as essentially a formal system.  But this view of computers
greatly underestimates the modern computer system, which is no more a
formal system than you are.  Aspects of you can be modeled formally,
and perhaps some superior being is able to model the whole of you as one
giant formal system, but we cannot, you are much too complex and animated.

Today's computers are like you in that respect.  Perhaps the same
superior being can also model them formally, but we cannot and must
settle for aspects.

Modern computer systems and networks have emerged as an alien life form,
friendly only when it suits them and beyond mortal comprehension.

Vaughan Pratt

More information about the FOM mailing list