Skip to main content
more info
Source Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

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

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

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

Source Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

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