FOM: Concepts of Recursion Theory

[Joseph Shoenfield]

     Thanks to Steve for his friendly reply to my posting with the above
title.   I think that by using an argument of his as an introduction, I
may have given the impression that my object was to refute his argument.
This is not the case.   I had three objects in mind: (i) to put forward my
belief that computability, some kind of definability, and recursion are
the three central concepts of present day recursion theory; (ii) to
encourage recursion theorists to be on the outlook for new central
concepts; (iii) to spread the word about the large amount of interesting
work which has been done on recursions in recent work.   My impression is
that this is not as well-known to recursion theorists as it should be.
Note that I still consider computability to be one of the central
concepts; if I emphasized the amount of work which does not concern
complexity, it was to point out the need for further central concepts.
   I would also like to make it clear that my original posting was
not an attempt to defend my opposition to changing the name of Recursion
Theory to Computability Theory (or to anything else>.   I think this
should be decided on much more trivial grounds.   In any case, I think the
name-change issue is of little importance, and am glad that several people
(such as Lempp) have expressed the same opinion.
     I am glad that my posting was instrumental in getting a posting from
Wayne Richter, who is one of the reseachers on recursions referred to
anonomously in my posting.    For some reason not clear to me, I have not
taken much interest in Finite Model Theory; Wayne's posting convinced me
that I was mistaken.   But the part of his posting I liked best was the
final questin: Why don't we just wait and see what happens?   I think that
this question should be posed much more often on fom.   For example, I
think it is appropriate at this point in my discussion with Steve and
Harvey of the foundational significance of Harvey's undecidabilty result.