Looking for a reference: equivalence of (semi)computable (semi)measures and PTMs 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)

Now, I prefer to think of the space of distributions that can be sampled by a 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
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