# 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?

• 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. May 7 '17 at 17:55
• 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. Jan 9 '20 at 8:09