# Turing degree of Solomonoff semi-measure

We define the Solomonoff semi-measure $m$ on finite strings $x$ by

$$m(x) = \sum_{p: U(p) = x} 2^{-l(p)},$$

where $U$ is a universal prefix Turing machine, $U(p) = x$ means $U$ outputs $x$ on input $p$, and $l(p)$ is the length of $p$. What is the Turing degree of (computing the first $n$ digits of) $m(x)$?

• Is "computing the first $n$ digits of" $m(x)$ (with $n$ as an input) known to $\hspace{1.89 in}$ be equivalent to computing $m(x)$? $\;$
– user6973
May 7 '15 at 4:16
• We can certainly only ever compute a finite sequence of digits of $m(x)$, so the two mean the same thing May 7 '15 at 13:02
• How does that follow? $\:$ (Consider the sequence of real numbers whose $m$-th entry is the limit of the sequence whose $n$-th term is 0.499999...[$t$ of them]...99999, where $t$ is the maximum of $n$ and the number of steps that $U(m)$ runs for.) $\;\;\;\;$
– user6973
May 7 '15 at 13:46
• @RickyDemer Ah, sorry, I misunderstood. Are you referring to this issue: en.wikipedia.org/wiki/… ? It looks like I should have used the "modern definition" rather than Minsky's. May 7 '15 at 15:23
• Yes. ${}{}{}\;$
– user6973
May 7 '15 at 16:01

Note that from $m (0)$ you can compute a version of Chaitin's $\Omega$. Moreover $m (x)$ is left-c.e. uniformly in $x$. So $m$ has Turing degree $0'$.