FOM: what is computability theory?

Martin Davis martind at cs.berkeley.edu
Wed Aug 19 00:41:51 EDT 1998


The short answer to this question is it is the same subject hat used to be
called "recursive function theory" and then metamorphosed to "recursion
theory". But the term "computability theory" for the subject has also been
in common use all along. In 1958 my book COMPUTABILITY & UNSOLVABILITY,
which e.g. Rogers cites extensively, appeared. Roger's book is called
THEORY OF RECURSIVE FUNCTIONS AND EFFECTIVE COMPUTABILITY. Turing's epochal
paper was called "On Computable Numbers". Beginning courses on the subject
have been taught in computer science departments for almost three decades
under the c-word name. 

In my old book I favored "semi-computable" rather than r.e. as a more
appropriate term. (E.g. what enumerates the empty set? Kleene's IM doesn't
accept the empty set as being r.e..) (I don't at all like Soare's "c.e.")

Soare quite explicitly believes that it is important that the genuine
connection between this subject and and the concept of computation should be
reflected in its name. I doubt that this is as important as he thinks it is.
But I fail to understand why Steve is so exorcised over the matter.

Martin




More information about the FOM mailing list