<p>This answer is not a reference but rather to make some of the notions precise in your question. First, semicomputable does stand for what you say but I think there is a big difference between upper and lower semicomputable - in case of the former I have no clue how you would sample.</p>

<p>Second, do you have a measure or a semimeasure? In a semimeasure the sum of the probabilities is at most 1, so I again do not know how you would sample, as there is no full distribution (of course you can say that you normalize by dividing the sum of the probabilities but that might not be computable, you could never know when to give up a computational path).</p>

<p>Finally, if you have a lower semicomputable measure, then it is in fact equivalent to have a PTM that can sample with this distribution (although we must allow the sampling to run for arbitrarily long, as long as it stops eventually).</p>

<p>I think the best reference on the topic is Ming Li and Paul Vitányi: An Introduction to Kolmogorov Complexity and Its Applications. For another available online see chapter 6.2 of László Lovász: Complexity of Algorithms at <a href="http://www.cs.elte.hu/~dom/complexitynew.pdf" rel="nofollow">http://www.cs.elte.hu/~dom/complexitynew.pdf</a></p>

CC BY-SA 3.0
2013-05-28T12:00:01.177Z
You're absolutely right (I guess this is the problem with rough proofs). The proof only works on lower semicomputable semimeasures. The way to deal with semimeasures that the 'left-over' probability mass is taken up by non-halting programs. It may not be sampling as you'd like in an experimental setting, but you have to account for the halting problem somewhere. I didn't find any reference to the sampling perspective in Li & Vitanyi (I'll have another look though). I'll see if the Lovasz book contains anything useful.
Peter
CC BY-SA 3.0
2013-05-28T15:00:44.667Z
I don't think there is any reference to sampling in any of these books, I've only suggested them as a reference for semicomputable semimeasures.
domotorp
CC BY-SA 3.0
2013-05-28T07:46:24.937Z
2013-05-28T07:46:24.937Z
domotorp
<p>I'm working with computable probability distributions over all finite strings. These are usually formalized as the space of all semicomputable semimeasures. Informally: a probability distribution is semicomputable if the probability it assigns to a given string can be computed to arbitratry precision from above or below by a Turing machine. If it can be computed from above and below, it's computable. (formal description <a href="http://en.wikipedia.org/wiki/Semicomputable_function" rel="nofollow">here</a>)</p>

<p>Now, I prefer to think of the space of distributions that can be sampled by a <a href="http://en.wikipedia.org/wiki/Probabilistic_Turing_Machine" rel="nofollow">probabilistic Turing machine</a> (PTM). That is the distributions $p$ for which a PTM with no input outputs the string $x$ with probability $p(x)$.</p>

<p>I have a (rough) proof that <s>the two classes of distributions</s> the class of lower semicomputable semimeasures and the class of semimeasures samplable by PTM are equivalent: every lower semicomputable semimeasure can be sampled by a PTM and vice versa. However, this seems like the sort of thing that has been worked out ages ago, and is well known to everybody. Can anybody help me with a reference that asserts and proves this equivalence?</p>

<p><strong>edited after @domothorp's comments</strong></p>

CC BY-SA 3.0
2017-05-07T17:55:43.433Z
I could not find a convincing reference, so I ended up writing a proof myself.  I doubt it's the first, but for what it's worth, it can be found in the appendix of  [this paper](https://scholar.google.nl/citations?view_op=view_citation&hl=en&citation_for_view=zVntAfQAAAAJ:Y0pCki6q_DkC).
Peter
CC BY-SA 4.0
2020-01-09T08:09:56.350Z
I wrote a more or less isomorphic question about computable probability measures on Cantor space, and was suggested this. Thanks for writing up this (surely classical?) fact, so I don't have to have an appendix.
Ville Salo
<pr.probability>
Looking for a reference: equivalence of (semi)computable (semi)measures and PTMs
Peter
# Looking for a reference: equivalence of (semi)computable (semi)measures and PTMs

(Asked by: username_0 on 2013-05-21)

I'm working with computable probability distributions over all finite strings. These are usually formalized as the space of all semicomputable semimeasures. Informally: a probability distribution is semicomputable if the probability it assigns to a given string can be computed to arbitratry precision from above or below by a Turing machine. If it can be computed from above and below, it's computable. (formal description [here](http://en.wikipedia.org/wiki/Semicomputable_function))

Now, I prefer to think of the space of distributions that can be sampled by a [probabilistic Turing machine](http://en.wikipedia.org/wiki/Probabilistic_Turing_Machine) (PTM). That is the distributions $p$ for which a PTM with no input outputs the string $x$ with probability $p(x)$.

I have a (rough) proof that ~~the two classes of distributions~~ the class of lower semicomputable semimeasures and the class of semimeasures samplable by PTM are equivalent: every lower semicomputable semimeasure can be sampled by a PTM and vice versa. However, this seems like the sort of thing that has been worked out ages ago, and is well known to everybody. Can anybody help me with a reference that asserts and proves this equivalence?

**edited after @domothorp's comments**

**Tags:** pr.probability
> **Comments:**
> **username_0**: I could not find a convincing reference, so I ended up writing a proof myself.  I doubt it's the first, but for what it's worth, it can be found in the appendix of  [this paper](https://scholar.google.nl/citations?view_op=view_citation&hl=en&citation_for_view=zVntAfQAAAAJ:Y0pCki6q_DkC).  
> **username_1**: I wrote a more or less isomorphic question about computable probability measures on Cantor space, and was suggested this. Thanks for writing up this (surely classical?) fact, so I don't have to have an appendix.  

---

## 1 answers

### Answer by username_2 on 2013-05-28. Score: 3

This answer is not a reference but rather to make some of the notions precise in your question. First, semicomputable does stand for what you say but I think there is a big difference between upper and lower semicomputable - in case of the former I have no clue how you would sample.

Second, do you have a measure or a semimeasure? In a semimeasure the sum of the probabilities is at most 1, so I again do not know how you would sample, as there is no full distribution (of course you can say that you normalize by dividing the sum of the probabilities but that might not be computable, you could never know when to give up a computational path).

Finally, if you have a lower semicomputable measure, then it is in fact equivalent to have a PTM that can sample with this distribution (although we must allow the sampling to run for arbitrarily long, as long as it stops eventually).

I think the best reference on the topic is Ming Li and Paul Vitányi: An Introduction to Kolmogorov Complexity and Its Applications. For another available online see chapter 6.2 of László Lovász: Complexity of Algorithms at <http://www.cs.elte.hu/~dom/complexitynew.pdf>

> **Comments:**
> **username_0**: You're absolutely right (I guess this is the problem with rough proofs). The proof only works on lower semicomputable semimeasures. The way to deal with semimeasures that the 'left-over' probability mass is taken up by non-halting programs. It may not be sampling as you'd like in an experimental setting, but you have to account for the halting problem somewhere. I didn't find any reference to the sampling perspective in Li & Vitanyi (I'll have another look though). I'll see if the Lovasz book contains anything useful.  
> **username_2**: I don't think there is any reference to sampling in any of these books, I've only suggested them as a reference for semicomputable semimeasures.  

---

