8
$\begingroup$

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?
$\endgroup$
8
  • $\begingroup$ Is it true that if $x\equiv_T0″$ is random and $z$ is low for $x$, then $z\oplus 0′\not\geq_T0‴$? $\endgroup$ – 喻 良 Apr 3 '14 at 10:36
  • $\begingroup$ I do not know how to prove - or disprove - this either. $\endgroup$ – Laurent Bienvenu Apr 3 '14 at 14:12
  • $\begingroup$ 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. $\endgroup$ – Denis Hirschfeldt Apr 3 '14 at 17:57
  • $\begingroup$ Sorry, in my comment, what I should have said is that the degrees of jumps of $2$-randoms include all degrees $\geq \mathbf{0''}$. $\endgroup$ – Denis Hirschfeldt Apr 3 '14 at 22:23
  • $\begingroup$ Hi Denis. No, I had not noticed this, nice! Maybe there is some hope that the answer is positive then (?) $\endgroup$ – Laurent Bienvenu Apr 4 '14 at 15:38
5
$\begingroup$

Frank came up a quite short negative answer:

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$.

$\endgroup$
2
  • $\begingroup$ do you need that $\emptyset' \oplus z \equiv_T z'$? I guess "$z$ is low for $x$" means "$x$ is random in $z$". $\endgroup$ – Wei Wang Jun 30 '14 at 23:36
  • $\begingroup$ If $x$ is random and $\geq_T \emptyset'$, then any low for $x$ real is $GL_1$. $\endgroup$ – 喻 良 Jul 1 '14 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.