FOM: r.e. degrees versus computer science

[Stephen G Simpson]

Simpson 13 Aug 1999 15:03:02 

 > > 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. ...

Kurtz 18 Aug 1999 13:02:39

 > 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 ...

[ I am grateful to Kurtz 18 Aug 1999 13:02:39 for publicly and clearly
explaining what he means by ``computability theory'' and his much
broader term ``mathematical science of computation'' and where he
thinks computational complexity theory fits in.  These distinctions
are too important to ignore and they will certainly come up again.  In
the past there has been some waffling on these issues. ]

In that case I must retract my endorsement of Kurtz's point 1.
Advanced work on r.e. sets and degrees (priority methods etc) is
certainly *not* in a standard computer science curriculum, and it
doesn't deserve to be there, because it's too specialized and remote.
It isn't even useful to most *researchers* in computer science.  Kurtz
implicitly acknowledges this by saying:

 > they are not a part of the common background of every theoretical
 > computer scientist.

Once again, the part of recursion theory that is of key importance for
computer science is in the work of Turing, G"odel, Church, and some of
Kleene's work.  It consists of the rudiments of partial recursive
functions and not much more than that.

To mention this obvious distinction is not pleasant, and I will
probably be subject to some criticism and/or retaliation for doing so.
But it is necessary, because some of the leaders have tried to
artificially puff up the importance of some aspects of recursion
theory.  For example, they have argued that priority methods are of
the essence in core computer science subjects such as operating
systems.  Tacit acceptance of such preposterous ideas has led to an
unjusified downgrading of genuine foundational research.

This entire FOM discussion of applications of recursion theory is an
almost perfect illustration of general patterns that often appear in
the evolution of academic subjects.  See my ``defending specialized
subjects'' posting of 28 Jul 1999 16:34:09 and Harvey's ``evolution''
posting of 2 Aug 1999 11:14:00.

-- Steve