FOM: what is computability theory?

Martin Davis martind at
Wed Aug 19 14:39:16 EDT 1998

From: Steve Simpson

>Here are two reasons why I'm so indignant about Soare's 1995 position
>1. Recursion theory as practiced by Soare and his group is concerned
>exclusively with the study and classification of *non-computable* sets
>(both semi-computable and otherwise).  To insist on calling this
>subject "computability theory" (if that's what Soare is doing) strikes
>me as extremely odd and perhaps intentionally misleading terminology.
>It's as if classifiers of rocks and other inanimate objects were to
>try to increase the prestige of their subject by renaming it

Curiously I heard the same objection from G\"odel (in ~1953), but ir was to
the (then current) term "recursive function theory". He objected to using it
for the study of non-recursive things. He mentioned Rosza Peter's work as
properly being recursive function theory.

Steve: Do you also then object to Roger's title for a book that is largely
about non-computable things?


More information about the FOM mailing list