[FOM] recursion theory question

Harvey Friedman friedman at math.ohio-state.edu
Sat Feb 19 21:05:24 EST 2005


Consider the various constructions of r.e. sets of intermediate degree. They
depend on some given partial recursive enumeration of the partial recursive
functions that remains unspecified in the construction. This enumeration is
always required to be a "standard" one in a technical sense.

My question is: how does the intermediate degree obtained by any given fixed
construction, depend on the choice of the partial recursive enumeration of
the partial recursive functions that is used?

At least, can one show, for the usual constructions, that at least two of
the sets obtained have different intermediate degrees?

Harvey Friedman 




More information about the FOM mailing list