FOM: computability & complexity

[Stephen G Simpson]

Martin Davis writes:
 > At 03:53 PM 8/23/98 -0400, simpson at math.psu.edu wrote:
 > >  Soare introduces himself as a computability
 > >theorist.  Wouldn't it be natural for his colleagues to assume that
 > >his focus is computation, computer science, algorithms, or something
 > >like that?  
 > 
 > No! Unless they are woefully uninformed.
 > 
 > CS departments have been giving courses in computability theory and
 > in algorithmic analysis for years; nobody confuses one with the
 > other.

CS professors wouldn't confuse one with the other, but outsiders
would.  The fact is that most people, even scientists, *are* uniformed
about what goes on in mathematics and computer science departments.
You can't blame them for being misled by misleading terminology.

In his 1995 position paper, Soare quotes from an essay by Charles
Sanders Peirce entitled "The Ethics of Terminology".  Peirce damns
misleading terminology as follows:

  The first rule of good taste in writing is to use words whose
  meaning will not be misunderstood; and if a reader does not know the
  meaning of the words, it is infinitely better that he should know he
  does not know it.

Ironically, this remark of Peirce could stand as a condemnation of
Soare's own terminological proposal, to repackage recursion theory as
computability theory.  A layman who hears the term computability
theory for the first time will naturally misinfer its meaning; he will
naturally think of computer science and algorithms, not r.e. sets and
degrees of unsolvability.  The term recursion theory is "infinitely
better" (Peirce's words), because less misleading.

Evidently Soare didn't notice this irony.

-- Steve