Slaman–Woodin conjecture on the complexity of the c.e. orbit relation
Let be an effective enumeration of the computably enumerable sets, and write when the two sets lie in the same orbit under automorphisms of the lattice of computably enumerable sets modulo finite sets. Slaman–Woodin conjecture. The index relation
is -complete. This conjecture concerns the descriptive-set-theoretic complexity of deciding whether two computably enumerable sets are automorphic. The source says that it was made by Ted Slaman and Hugh Woodin in 1989, but supplies no resolution.
References
Primary source
Peter A. Cholak, Rod Downey and Leo Harrington, “The Complexity of Orbits of Computably Enumerable Sets”, arXiv:0705.0125 (2007).
Additional references
2 papers in this index state this conjecture (2006–2007). The statement above is taken from the most recent of them; the others are arXiv:math/0607264.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.