<p>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'$.</p>

CC BY-SA 3.0
2015-05-06T03:55:54.453Z
2015-05-06T03:55:54.453Z
Bjørn Kjos-Hanssen
<p>We define the <a href="http://www.scholarpedia.org/article/Algorithmic_probability#Discrete_Universal_A_Priori_Probability" rel="nofollow">Solomonoff semi-measure</a> $m$ on finite strings $x$ by</p>

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

<p>where $U$ is a universal <a href="http://www.scholarpedia.org/article/Algorithmic_complexity#Prefix_Turing_machine" rel="nofollow">prefix Turing machine</a>, $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)$?</p>

CC BY-SA 3.0
2015-05-07T13:02:04.830Z
We can certainly only ever compute a finite sequence of digits of $m(x)$, so the two mean the same thing
Andrew
CC BY-SA 3.0
2015-05-07T15:23:33.023Z
@RickyDemer Ah, sorry, I misunderstood. Are you referring to this issue: http://en.wikipedia.org/wiki/Computable_number#Informal_definition_using_a_Turing_machine_as_example ? It looks like I should have used the "modern definition" rather than Minsky's.
Andrew
<computability><pr.probability><universal-turing-machines>
Turing degree of Solomonoff semi-measure
Andrew
# Turing degree of Solomonoff semi-measure

(Asked by: username_0 on 2015-05-05)

We define the [Solomonoff semi-measure](http://www.scholarpedia.org/article/Algorithmic_probability#Discrete_Universal_A_Priori_Probability) $m$ on finite strings $x$ by

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

where $U$ is a universal [prefix Turing machine](http://www.scholarpedia.org/article/Algorithmic_complexity#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)$?

**Tags:** computability, pr.probability, universal-turing-machines
> **Comments:**
> **username_0**: We can certainly only ever compute a finite sequence of digits of $m(x)$, so the two mean the same thing  
> **username_0**: @RickyDemer Ah, sorry, I misunderstood. Are you referring to this issue: http://en.wikipedia.org/wiki/Computable_number#Informal_definition_using_a_Turing_machine_as_example ? It looks like I should have used the "modern definition" rather than Minsky's.  

---

## 1 answers

### Answer by username_1 on 2015-05-06. Score: 3 | Accepted answer

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


---

