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)?
Some preliminary comments:
- 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?