FOM: Recursive vs Computable
Stephen G Simpson
simpson at math.psu.edu
Tue Aug 25 12:03:35 EDT 1998
Joseph Shoenfield writes:
> The dispute over replacing "recursive" by "computable" has irrupted
> in fom just as it was quiting down in recursion-theoretic circles.
Yes. But my impression is that the discussion in recursion-theoretic
circles was rather barren. I feel that the discussion here on the FOM
list is exciting, because we are delving into some substantial issues:
What is recursion theory anyway? Does it include complexity theory?
What are and what should be the key issues and programs in recursion
theory? Where is recursion theory heading? What is the relationship
between recursion theory and "applications" such as recursive algebra?
Etc etc. The FOM list is a forum where such issues can be discussed
from a perspective of general intellectual interest and relevance to
f.o.m. (= foundations of mathematics).
> Bob Soare was the first to seriously propose the change. He was (I
> think) motivated to consider the change by some events which seemed
> to show that recursion theory was not receiving its just share of
> resources and the observation that anything connected with
> computers generally received at least its just share.
Thanks for candidly stating Bob Soare's apparent reason for pushing
the change. One of the questions on my mind is, how much does
recursion theory actually have to do with computers?
I like your comments on "semirecursive" and the appropriate
terminology for higher type recursion.
More information about the FOM