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
    Commented Apr 29, 2012 at 11:13
  • $\begingroup$ @Joel: good point, fixed. $\endgroup$
    – Noah Schweber
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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$
    – 喻 良
    Commented 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
    Commented Apr 29, 2012 at 4:14

You must log in to answer this question.

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