4
$\begingroup$

Let $\Omega$ be the halting probability (see (http://en.wikipedia.org/wiki/Chaitin's_constant) and R. Downey, and D. Hirschfeldt (2010), Algorithmic Randomness and Complexity for reference). If A is Martin-Löf random with respect to $\Omega$ (so A is 2-random), does A compute an infinite set $G\subseteq \Omega$ or $G\subseteq 2^\omega-{\Omega}$ ? This was motivated by the idea of constructing models using random sets to avoid $SRT_2^2$ in the reverse mathematics context.

$\endgroup$
1
  • $\begingroup$ Your link got cut off I believe. $\endgroup$
    – Jason Rute
    Commented Jun 12, 2013 at 18:04

1 Answer 1

6
$\begingroup$

No. Since $A$ is ML-random relative to $\Omega$, by van Lambalgen's theorem it follows that $\Omega$ is ML-random relative to $A$. If $A$ could compute such a set $G = \{g_0 < g_1 < g_2 < \dots \}$, then $A$ could form the ML-test $(V_n)_{n \in \omega}$, where $V_n = \{ X : (\forall i < n )[X(g_i) = 1]\}$. Note that $\mu(V_n) = 2^{-n}$. This would capture $\Omega$, a contradiction.

Replace $X(g_i) = 1$ with $X(g_i) = 0$ for the case $G \subseteq 2^{\omega} - \Omega$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .