FOM: response to Shipman

[Stephen G Simpson]

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