FOM: Recursion theory question

[Schaefer, Marcus]

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.
> 
> 
> 
> 
>