What Turing degree is this function?

Question

Over at http://www.scottaaronson.com/blog/?p=2725#comment-1089004 we had a discussion of intermediate Turing degrees.

The following function came up:

Take Chaitin’s constant, and rearrange its binary digits as follows: for each of the sets {1st digit} {2-3rd digits} {4-7th digits} {2^n-(2^n+1)-1}, order the digits within in ascending order, i.e. zeros then ones.

(This is a number, the function is just {n->nth digit of the number} for natural numbers n)

A later comment says it's non-computable:

because it has unbounded information about omega.

We know that K(Omega_n) >= n + O(1), but knowing how many 0s and 1s are in the second half of n/2 bits would allow you to save about (log n)/2 bits. This gives a contradiction for large enough n of the form n=2^i

It's clearly either of degree 0′ or lower. Which is it? In other words, does an oracle for this function let you solve the halting problem?

Answer 1

I think it's strictly below $0'$. Namely let's call your number $\Gamma(\Omega)$ where $\Gamma$ is a Turing functional. Let $\Phi$ be any other Turing functional. Then show that the set $$ S = \{X: X = \Phi(\Gamma(X))\} $$ has measure 0 (which is easy since $\Gamma$ erases a lot of information about $X$) and moreover show that it is a Martin-Löf null set (this requires a bit more care). Then, since $\Omega$ is Martin-Löf random, it follows that $\Omega$ does not belong to $S$. Hence $\Omega$ is not Turing reducible to $\Gamma(\Omega)$.

On the other hand, $\Gamma(\Omega)$ is above another ML-random number in Turing degree, namely

$N(\Omega) := \{n: \Omega$ has at least as many 1s as 0s in the $n$th interval in the definition of $\Gamma(\Omega) \}$.

We should then have $$ \mathbf 0 < \mathrm{deg}_T(N(\Omega)) <\textrm{deg}_T(\Gamma(\Omega)) <\mathbf 0' $$ Note however that the Turing degrees $\mathrm{deg}_T(N(\Omega))$ and $\textrm{deg}_T(\Gamma(\Omega))$ presumably depend on the chosen Gödel numbering of the Turing functionals, so part of the answer to the question "what Turing degree does $\Gamma(\Omega)$ have" is "it depends on your Gödel numbering of the Turing functionals".