FOM: r.e. degrees versus computer science

[Stuart A. Kurtz]

This is a partial reply to Simpson's FOM 9908.63/20 Aug 1999 10:59:36.

In the first place, I'd like to thank Steve Stephenson for telling
me about the following article:

	McCarthy, John.  "A Basis for a Mathematical Theory of
	Computing," in "Computer Programming and Formal Systems,"
	ed. P. Braffort and D. Hirschenberg, North Holland, 1963.

This is a wonderful article, and I'm delighted to recommend it to
the broader readership of this forum.  I cite it here because
McCarthy uses and defines "mathematical science of computation" and
"theory of computability" in substantially the same way I do.  I
believe that this very early attestation of these phrases, outside
of the confines of the present debate, and with their "modern"
definitions, argues for the naturalness and appropriateness of my
usage.

Second, I'd like to criticize Simpson's logic and/or rhetoric in the
following passage:

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

Simpson's quote from my note is selective to the point of
misrepresentation, which I find objectionable.  I said

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

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.

Furthermore, his conclusion requires an unnatural local definition,
or he has made logical blunder that would be regrettable in a
sophomore.  For, either the phrase "key importance" means "a notion
so essential that it is not possible without it to practice a
discipline," or, Simpson is inferring a universal (that no one in CS
need know the priority method) from an existential (that there
researchers in theoretical CS who do not know the priority method).

Assuming that Simpson did not make the elementary a blunder, then
his meaning of "key importance" requires that he also accept that
"mathematical logic is not of key importance to mathematics," as
there are research mathematicians who know nothing, and care still
less, about mathematical logic.  If this is his intended meaning,
o.k., but it strikes me as vacuous.

Third, consider the following:

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

This is at best a strawman.  Friedman's and Simpson's analyses were
developed in the context of the current debate.  They present an
abstracted version of the history of their attack on computability
theory and the reaction of its leaders, then tie the part of their
opposition to a pejorative conclusion.  This is supposed to be a
part of a general pattern, although examples are wanting.  Their
hypothesis is insufficiently established to be admissible as fact.

But even were we to accept this hypothesis, their application of it
to the current debate is still fallacious.  For what is claimed is
"if a field is overspecialized, then it will argue against its
detractors as follows...  ." And the application is to infer from
"computability theory argues against its detractors as follows..." 
to "computability theory is overspecialized."  A -> B, B, therefore
A!?

I would like to conclude by recommending another source,

	Walton, Douglas, "Informal Logic, A Handbook for Critical
	Argumentation," Cambridge University Press, 1989.

I found this to be well written, lively, and a useful introduction to
the obligations of debate and to fallacies in argumentation.

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