6
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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$? $\endgroup$
    – Joel David Hamkins
    Apr 29, 2012 at 11:13
  • $\begingroup$ @Joel: good point, fixed. $\endgroup$
    – Noah Schweber
    Apr 29, 2012 at 17:49
  • $\begingroup$ 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. $\endgroup$
    – Joel David Hamkins
    May 2, 2012 at 13:06
  • $\begingroup$ 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.). $\endgroup$
    – Noah Schweber
    May 2, 2012 at 15:13
  • $\begingroup$ 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$. $\endgroup$
    – Noah Schweber
    May 2, 2012 at 15:15

1 Answer 1

Reset to default
3
$\begingroup$

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.

\begin{proof}

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.

\end{proof}

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ I know the definition of $n$-randomness, but I don't see where your results come from. Could you elaborate a bit? $\endgroup$
    – Noah Schweber
    Apr 29, 2012 at 3:56
  • $\begingroup$ 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. $\endgroup$
    – Noah Schweber
    Apr 29, 2012 at 3:57
  • $\begingroup$ I just added some more details. But actually these remarks do not give any information about $N_e$. You might want better answer. $\endgroup$
    – 喻 良
    Apr 29, 2012 at 4:06
  • $\begingroup$ 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. $\endgroup$
    – Noah Schweber
    Apr 29, 2012 at 4:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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