# Martin-Löf randomness relative to a $\Delta^0_2$-representation of a real

I have a question which I already asked on a more specialized site (http://logicblogfrontend.hoelzl.fr/), but perhaps M.O. will allow me to reach a wider range of experts.

Suppose that $X$ is Martin-Löf random, and $Y$ is some real. Must there be a sequence $R$ of rationals converging to $Y$ such that $X$ is random relative to $R$ (coded as a single real)?

• Of course the question is only interesting when $X$ is not random relative to $Y$, otherwise take $R$ to be a fast Cauchy sequence for $Y$.
• One cannot require the sequence $R$ to be non-decreasing. For example, if $X=\Omega$ (Chaitin's constant) and $Y=1-\Omega$, then any non-decreasing sequence of rational converging to $Y$ in fact computes $Y$ and thus derandomizes $X$.
• If the answer to the question is `yes', a weak consequence would be that for every random $X$, there is a high set $R$ such that $X$ is $R$-random (indeed, taking $Y=\emptyset''$, any approximation $R$ of $Y$ is such that $R' \geq_T Y = \emptyset''$, hence is high). Is it even known whether this simpler fact is true?
• Is it true that if $x\equiv_T0″$ is random and $z$ is low for $x$, then $z\oplus 0′\not\geq_T0‴$? – 喻 良 Apr 3 '14 at 10:36
• I do not know how to prove - or disprove - this either. – Laurent Bienvenu Apr 3 '14 at 14:12
• You may already know this, but the answer is yes if $X$ is $\Delta^0_2$, because the degrees of jumps of $2$-randoms are closed upwards. But I don't think that helps much which the general question. – Denis Hirschfeldt Apr 3 '14 at 17:57
• Sorry, in my comment, what I should have said is that the degrees of jumps of $2$-randoms include all degrees $\geq \mathbf{0''}$. – Denis Hirschfeldt Apr 3 '14 at 22:23
• Hi Denis. No, I had not noticed this, nice! Maybe there is some hope that the answer is positive then (?) – Laurent Bienvenu Apr 4 '14 at 15:38

Let $x=\Omega\oplus \Omega^{\Omega}$ and $z$ is low for $x$. Then by van-Lambalgen's theorem relativized to $z$, $\Omega^{\Omega}$ is $\Omega\oplus z$-random. So $0''\equiv_T x\not\leq_T \Omega\oplus z\equiv_T 0'\oplus z$.
• do you need that $\emptyset' \oplus z \equiv_T z'$? I guess "$z$ is low for $x$" means "$x$ is random in $z$". – Wei Wang Jun 30 '14 at 23:36
• If $x$ is random and $\geq_T \emptyset'$, then any low for $x$ real is $GL_1$. – 喻 良 Jul 1 '14 at 0:04