FOM: r.e. degrees versus computer science

[Stephen G Simpson]

This is a response to Stuart Kurtz 30 Aug 1999 17:03:03.

A general comment: 

Kurtz and other recursion theorists are evading Friedman's main point.
The point is that recursion theory is in need of reform, because the
advanced theory of r.e. sets and degrees is almost entirely irrelevant
to fundamental issues in f.o.m. and f.o.c.s.

If they disagree with this point, could they please explicitly state
such a fundamental issue, and then explicitly state the role of the
advanced theory of r.e. sets and degrees with respect to that issue?

Some specific comments:

1. Kurtz cites a 1961 paper of McCarthy and says:

 > McCarthy uses and defines "mathematical science of computation" and
 > "theory of computability" in substantially the same way I do.

However, this is not the case.  The thrust of McCarthy's paper
(available on-line at <http://www-formal.stanford.edu/jmc/basis.html>)
is to present a certain formalism for recursive functions as a basis
for a mathematical theory of computation.  McCarthy explicitly says
that numerical analysis cannot contribute here because ``its subject
matter is too narrow to be of much help in forming a general theory''.
Yet Kurtz 18 Aug 1999 13:02:39 says

 > I *do* mean to include numerical analysis, scientific computing,
 > computational algebra, etc.
 [my emphasis]

So, we are back to square one.  The waffling continues.  The recursion
theorists are still trying to have their cake and eat it too.  They
want to bask in the glory of recent achievements in numerical
analysis, scientific computation, computational algebra, etc, even
though r.e. sets and degrees are irrelevant to those subjects and
achievements.  Who knows what their next preposterous claim will be?

If they really believe that r.e. sets and degrees are relevant here,
could they please explicitly state a recent achievement in numerical
analysis or scientific computation or computational algebra and then
state the role of r.e. sets and degrees in that achievement?

2. Kurtz continues:

 > Simpson's conclusion forgets (and his selective quote omits) that
 > significant applications of the priority argument to computer
 > science have been presented by myself and others on this forum.

On the contrary, I have explicitly acknowledged the existence of such
applications of priority arguments.  But Fenner, one of the authors of
such applications, has also acknowledged (3 Aug 1999 12:38:58) that
such applications are at most a very small percentage of papers in
computational complexity theory.  Has Kurtz acknowledged this?

Furthermore, Kurtz and other recursion theorists have not explained
what fundamental issues in computer science are addressed by such
applications of priority arguments.  For an example of fundamental
issues in computer science, see Friedman 1 Sep 1999 04:10:03.

And, what is meant by ``the priority argument''?  Does it include
to-do lists and secretaries' work schedules?

3. Regarding the pattern described in my ``defending specialized
subjects'' posting of 28 Jul 1999 16:34:09, Kurtz says that

 > examples are wanting.  

But this is not the case.  Several mathematical examples have been
mentioned by Friedman 2 Aug 1999 11:14:00, Baldwin 2 Aug 1999
14:06:19, and Whiteley 04 Aug 1999 20:13:12, namely category theory,
general topology, non-associative algebras, lattice theory, and
invariant theory.

Moreover, I am sure that many FOM readers have seen the same pattern
in connection with a variety of specialized topics within philosophy,
computer science, mathematical logic, etc.  I am willing to let FOM
readers judge for themselves whether or not the current FOM discussion
of ``priority arguments in applied recursion theory'' fits the
pattern.

4. Kurtz and other recursion theorists probably think that, by raising
these issues, Friedman and I are singling out r.e. sets and degrees
for especially rough treatment.  But this is not the case.  Many
specialized topics in mathematical logic could be subjected to the
same kind of critical analysis.

The broader point being made is that ``it is crucial for mathematical
logic to return to its roots in the foundations of mathematics''
(Friedman, 1 Sep 1999 04:10:03).

-- Steve