FOM: Recursion theory question

[Robert M. Solovay]

Here is a remark and question concerning Friedman's posting:

Question: What does "DNR" mean [and what do the letters stand for]?

Remark: Call the set in the conjecture F. It obviously depends on the
Godel numbering of the partial recursive functions. [I presume that W_e is
the domain of phi_e]. As usual we call such an enumeration acceptable if
it satisfies the enumeration and S_m_n theorems.

Assertion: there is an acceptable enumeration such that the corresponding
F has degree 0'.

It would be amusing to construct a different acceptable enumeration such
that F has degree less than 0'; this seems much more difficult, but
perhaps is possible.

The enumeration of the assertion is rather pathological. [Roughly, most of
the phi_e's are under my personal control.] It would be easy to give an
example of a standard enumeration [coming from a reasonable encoding of
the one-tape Turing machines, say]. For such a standard enumeration, I
have nothing, as yet, to say.

	--Bob Solovay

On Sat, 16 Feb 2002, Harvey Friedman wrote:

> The following is well known.
>
> THEOREM. "The set of all n such that there exists e < n with phi_e(0) = n"
> is of Turing degree 0'.
>
> Normally, one easily proves that this is effectively simple, and quotes
> Donald Martin's theorem that every effectively simple set is of Turing
> degree 0', whose usual proof is to use Donald Martin's theorem about DNR.
> However, there is a simple direct proof of this Theorem that does not
> involve this interesting machinery. This is also probably well known.
>
> But now what about
>
> 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.
>
>
>
>