FOM: "The Mathematical Science of Computation"

[Stuart A. Kurtz]

Simpson, in FOM 13 Aug 1999 15:03:02 writes:

> This is a partial response to Stuart Kurtz, FOM 6 Aug 1999 11:08:47.
> 
> Kurtz says:
> 
>  > Point 1.  While computability theory originated in the study of the
>  > foundations of mathematics, it is now a part of the foundations of
>  > other applied fields.
> 
> The term ``computability theory'' is somewhat ambiguous (see for
> instance FOM 23 Aug 1998 13:36:53) but for discussion let's take it to
> be the subject sometimes known as recursive function theory, defined
> by Martin Davis's classic textbook ``Computability and
> Unsolvability'': Turing machines, general recursive functions, the
> rudiments of partial recursive functions and r.e. sets, etc.

"Computability theory" refers to what was formerly known as
recursion theory on the natural numbers.  The cited article FOM 23 Aug
1998 13:36:53 is Simpson's, and the only ambiguity he indicates in
that article is as to whether the term "computability theory" is
intended to subsume complexity theory.  In my opinion, computability
theory and complexity theory are separate, but related disciplines,
with the former serving a foundational role with respect to the
later.

> With the above definition of ``computability theory'', point 1 is
> indisputable.  Turing's fundamental work on unsolvability of the
> halting problem and related results are firmly entrenched in the
> computer science curriculum, and deservedly so.  This stuff is part of
> the foundations of computer science and is basic for every theoretical
> computer scientist.

Thank you.  But your definition of computability theory is too
limited.  The leaders of the field mean it to include all work on
c.e. sets and degrees; and the more modern ideas and techniques do
find significant application in theoretical computer science (as I
have shown), even if they are not a part of the common background of
every theoretical computer scientist.

>  > The mathematical science of computation, founded in large part on
>  > computability theory, overlaps the current disciplinary boundaries
>  > of mathematics and computer science.
> 
> The phrase ``mathematical science of computation'' is again ambiguous.
> Does it include numerical analysis?  Numerical linear algebra?  The
> finite element method?  At any rate, it is certainly true that both
> computability theory (as defined above) and numerical analysis etc
> overlap the disciplinary boundary between mathematics and computer
> science.

The phrase the "mathematical science of computation" is not
ambiguous.  Rather, and this is not the same thing, Simpson does not
understand my meaning.  Let me clarify.

When I use the phrase the "mathematical science of computation," I
do mean to include numerical analysis, scientific computing,
computational algebra, etc.  I am pleased to have a numerical
analyst, a combinatorialist, a computability theorist, a
computational geometer, a computational scientist, and a several
complexity theorists in my department.  I also have computationally
oriented colleagues in mathematics, statistics, and even
linguistics, whose work is deeply based in the synergy between
mathematics and computation.  We share a technical vocabulary and a
distinctive point of view.  I am happy to include them as
co-participants in a common intellectual culture.  My intent in
coining the phrase the "mathematical science of computation" is to
name that culture.

Respectfully,

Stu
---------------
Stuart A. Kurtz
Professor and Chair
Department of Computer Science
The University of Chicago

web:   http://www.cs.uchicago.edu/~stuart
email: stuart at cs.uchicago.edu
phone: (773)-702-3493
fax:   (773)-702-8487