FOM: Recursion theory question
Schaefer, Marcus
MSchaefer at cti.depaul.edu
Wed Feb 20 16:59:17 EST 2002
Unfortunately I made a mistake, the set
A = {n: max(W_e) = n for some e<n} is not d.c.e,
but it is 3-REA, so the result still follows.
The generalized Arslanov completeness criterion
for n-REA operators is from
Jockusch, Lerman, Soare, Solovay
Recursively enumerable sets modulo iterated jumps
and extensions of Arslanov's completeness criterion.
J. Symbolic Logic 54 (1989), no. 4, 1288--1323.
The solution is unsatisfactory in the sense that the
generalized Arslanov criterion is (provably) nonuniform,
so we still lack a natural completeness reduction for
the set A.
There are many open problems similar to the one discussed
here (minimal indices, shortest descriptions), some of
them are listed in
Schaefer, Marcus
A guided tour of minimal indices and shortest descriptions.
Arch. Math. Logic 37 (1998), no. 8, 521--548.
I'd be glad to hear about progress on any of them.
Marcus
> -----Original Message-----
> From: Bart Kastermans [mailto:bkasterm at umich.edu]
> Sent: Wednesday, February 20, 2002 3:27 PM
> To: Harvey Friedman
> Cc: fom at math.psu.edu
> Subject: RE: FOM: Recursion theory question
>
>
> > Thank you very much for this. Please tell us what d.c.e. is.
>
> Difference of computably enumerable sets (i.e. W_e - W_f).
>
> BK
> --
> http://www.math.lsa.umich.edu/~bkasterm/
>
> Obligatory quote.
>
>
>
>
>
More information about the FOM
mailing list