Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For a fixed Turing machine $\Phi_e$, what is the probability that it will reduce a given real to some less complex, yet still non-computable real?

More precisely: It is known that the set of reals with minimal Turing degree has measure zero. Since $N_e:=\lbrace X: \Phi_e^X\text{ is total and }X>_T\Phi_e^X>_T\emptyset\rbrace$ is Borel, it is Lebesgue measurable. But each non-minimal $X$ is in some $N_e$, and hence by the result quoted above not every $N_e$ has measure zero (since the set of non-minimal reals, with measure 1, is the union of the countably many measurable $N_e$). My question is: what is known about the possible values of $m(N_e)$ for $e\in\omega$? (I am also interested in a characterization of the set of $e$ such that $N_e$ has measure zero (or one).)

One thing that is easy to show: just by examining the definition, it is clear that $m(N_e)$ is $\Sigma^1_2$ (I think) for each $e\in\omega$. I presume much more can be said (perhaps $\forall e, m(N_e)\in\lbrace 0, 1\rbrace$?), yet I cannot seem to prove anything nontrivial.

share|improve this question
Very interesting question! (despite your several self-deprecating remarks, which in my opinion could be omitted) But wouldn't it be clearer to write your condition positively as: $0\lt_T \phi_e^X\lt_T X$? –  Joel David Hamkins Apr 29 '12 at 11:13
@Joel: good point, fixed. –  Noah S Apr 29 '12 at 17:49
So we seem to get any computable real in the unit interval as the measure $m(N_e)$ for some $e$. But is there any reason to think that $m(N_e)$ is always a computable real? If so, this answers the question. But it does seem that $m(N_e)$ could be more complex than computable. –  Joel David Hamkins May 2 '12 at 13:06
Off the top of my head: it seems like we can get not just the computable reals, but the c.e. reals, as follows. Fix a c.e. set $C$, and consider the Turing machine $\Phi_e$ which operates as follows. Given oracle $X$, with an initial sequence of $n$ 1s (possibly $n=0$), $\Phi_e^X(k)=0$ for $n\not\in C_k$, and $\Phi_e^X(k)=X(2k)$ for $n\in C_k$. It seems to me that the binary representation of $N_e$ is precisely the characteristic function of $C$ (maybe shifted one digit over? It's early in the morning.). –  Noah S May 2 '12 at 15:13
Actually, I think this lets us get all $\Delta^0_2$ reals: let $f(x, s)$ be a computable function of two variables so that $\lim f(x, s)$ exists for all $x$. Let $C=\lbrace x: \lim f(x, s)=1\rbrace$. Let $n$ be as before, and let $\Phi_e^X(k)=0$ if $f(n, k)=0$, and $\Phi_e^X(k)=X(2k)$ if $f(n, k)=1$. –  Noah S May 2 '12 at 15:15
show 1 more comment

1 Answer

Not sure whether the following answers your question, but they might be helpful.

Fix any number $n\geq 2012$.

1 For any $e_0$ so that $\Phi_{e_0}^X=X_0$ where $X_0$ is the unique real so that $X=X_0\oplus X_1$. Then for such $e_0$, $m(N_{e_0})=1$.

2 For any $e_1$ so that $\Phi_{e_1}^X=0$ if $X(0)=0$ and $\Phi_{e_1}^X=X_0$ if $X(0)=1$. Then for such $e_1$, $m(N_{e_1})=\frac{1}{2}$.

3 $m(N_e)$ must be $\Delta^0_n$. Just note that $N_e$ is a $\Delta^0_{n-1}$ set.

4 $m(N_e)>0$ if and only if $N_e$ contains an $n$-random real.


If $m(N_e)>0$, then obviously $N_e$ contains an $n$-random real.

$N_e$ is a $\Delta^0_{n-1}$ set. So if it is null, then it does not contain any $n$-random real.


5 $m(N_e)=1$ if and only if $N_e$ contains all $n$-random reals.

The proof is similar to 4.

The lower bound $2012$ can be certainly significantly smaller.

For randomness notions, you may refer Downey and Hirschfeldt (2010) or Nies (2009).

share|improve this answer
I know the definition of $n$-randomness, but I don't see where your results come from. Could you elaborate a bit? –  Noah S Apr 29 '12 at 3:56
Specifically, I understand 1 and 2 (and it seems that 2 could be generalized to get $m(N_e)$ to be any computable real), but not 3 through 5. –  Noah S Apr 29 '12 at 3:57
I just added some more details. But actually these remarks do not give any information about $N_e$. You might want better answer. –  Liang Yu Apr 29 '12 at 4:06
Thanks - this makes sense now. The upper (it makes more sense to me to think of it as an upper bound) bound 2012 seems to be about 6, just based on a quick glance at the quantifier complexity of the sentences asserting $X\in N_e$, $N_e$ has measure $<r$, etc. –  Noah S Apr 29 '12 at 4:14
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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