FOM: Recursion theory question

Harvey Friedman friedman at
Wed Feb 20 12:41:28 EST 2002

>> >
>> > CONJECTURE. "The set of all n such that there exists e < n
>> such that n is
>> > the largest element of W_e" is of Turing degree 0'.
>> >
>> > Is this well known, or at least known? If not, then can you
>> prove this? I
>> > am confident that an expert in recursion theory can do this.
>> >
>Since the set is d.c.e. you can use the generalized Arslanov
>criterion to show that the set is Turing complete. Interestingly
>the reduction can't be found effectively, leaving open the existence
>of a natural reduction. (This is similar to the set of descriptions
>of smallest size with an arbitrary size function that I looked at in
>Schaefer, Marcus
>A guided tour of minimal indices and shortest descriptions.
>Arch. Math. Logic 37 (1998), no. 8, 521--548.)
>There are many interesting open questions left in that area.

Thank you very much for this. Please tell us what d.c.e. is.

More information about the FOM mailing list