The highness–tracing correspondence for computable limit ordinals

At least 12 years old · documented by

Let α\alpha be a computable limit ordinal, possibly with additional closure properties such as closure under addition. For an oracle AA, let High⁡(MLR,α−Demuth)\operatorname{High}(\text{\rm \textsf{MLR}},\alpha-\text{\rm \textsf{Demuth}}) denote the class of oracles that make every Martin-Löf random real α\alpha-Demuth random, and let AA be α\alpha-c.a. tracing when it traces every α\alpha-c.a. function with the corresponding AA-c.e. bounds. The highness–tracing conjecture.

A∈High⁡(MLR,α−Demuth)⟺A is α-c.a. tracing.A\in\operatorname{High}(\text{\rm \textsf{MLR}},\alpha-\text{\rm \textsf{Demuth}})\quad\Longleftrightarrow\quad A\text{ is }\alpha\text{-c.a. tracing}.

This is proposed as an extension of the known correspondences between highness for pairs of randomness notions and tracing properties, including the cases of ω\omega-c.a. tracing and Δ20\Delta^0_2 tracing. The required closure properties of α\alpha and the equivalence in this intermediate setting are not established here.

References

Primary source

Andre Nies, “Logic Blog 2012”, arXiv:1302.3686 (2013).

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.