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](http://www.scottaaronson.com/blog/?p=2725#comment-1089344) 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?



What Turing degree is this function?
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".


