FOM: response to Shipman
Stephen G Simpson
simpson at math.psu.edu
Tue Aug 25 09:09:33 EDT 1998
JoeShipman at aol.com writes:
> I believe that the situation is the same for higher degrees: that
> is, that no natural example is known of a set whose degree of
> unsolvability is not in {0, 0', 0'', ....} [where the ....'s run
> through recursive ordinals], except for sets whose degree is
> obviously greater than all of these.
I think this can be extended even farther, at least through the Turing
degrees of constructible reals, using Jensen's master codes. The
appropriate hierarchy 0^alpha, alpha < omega_1^L (L = the
constructible universe of G"odel) is discussed e.g. in my paper
Stephen G. Simpson, The hierarchy based on the jump operator, in:
Kleene Symposium, edited by J. Barwise, H. J. Keisler and
K. Kunen, North-Holland, Amsterdam, 1980, pp. 203-212.
It probably extends still farther under large cardinal hypotheses,
using more recent fine structure results of Steel and others.
> to legitimately classify both computational complexity theory and
> recursion theory under the name "computability theory" without
> offending anyone one had better be a respected researcher in BOTH
> areas; such researchers exist and their conclusive opinion on this
> terminological controversy is awaited)
This request for expert opinion seems very sensible. Martin Davis
could be regarded as an authority in both areas. I myself was
certainly not trying to play the role of an authority here. I was
only asking the question, i.e. whether complexity theory is part of
computability theory or not. I would appreciate a conclusive answer
to this question.
The existence of incomparable but natural complexity classes would
be very interesting indeed.
-- Steve
More information about the FOM
mailing list