Harrington's conjecture on representatives of c.e. set orbits

About 19 years old · traced to

Let AA be a computably enumerable set and let d\boldsymbol{d} be a Turing degree. Write A′A' for the Turing jump of AA, and let L∗(A)\mathcal{L}^*(A) denote the lattice structure associated with AA modulo finite sets. Harrington's conjecture. If

A′≤Td′,A' \leq_T \boldsymbol{d}',

then there is a computably enumerable set A^∈d\hat{A}\in\boldsymbol{d} such that

L∗(A)≅L∗(A^).\mathcal{L}^*(A)\cong\mathcal{L}^*(\hat{A}).

This asks whether the jump inequality is sufficient to find, within the degree d\boldsymbol{d}, a representative whose orbit-invariant lattice structure agrees with that of AA. The source presents it as a conjecture of Harrington; no resolution is supplied here.

References

Primary source

Peter A. Cholak, Rod Downey and Leo Harrington, “The Complexity of Orbits of Computably Enumerable Sets”, arXiv:0705.0125 (2007).

Progress summary

Never refreshed

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.