What class of probability distributions do probabilistic turing machines induce? [closed]

Question

What class of probability distributions is induced by the class of probabilistic turing machines? Is there a precise characterization?

Answer 1

There are different meanings to induced probability measure of a probabilistic Turing machine. First, lets consider the finitary case since that is easier. A Turning machine with oracle input and natural number output is just a partial computable function, $f\colon 2^\mathbb{N} \rightarrow \mathbb{N}$. Assuming the oracles are given the uniform probability measure (a.k.a. the fair-coin measure or the Lebesgue measure) then the probability $p(n)$ is the probability that $n$ is outputted with some random oracle input. For total computable functions, by compactness you will notice that $p(n)$ must be zero for sufficiently large $n$ and a dyadic rational for all other $n$. It is easy to see all such $p(n)$ can be realized. Now assume that $f$ is partial computable, but its domain is measure one. Then $p(n)$ is a computable sequence of reals summing to 1. It is computable since one can estimate $p(n)$ by searching through all possible oracles until we know where all but $\varepsilon$-measure of the oracles map to. Such a $p$ is called a computable measure on $\mathbb{N}$. Again, all such $p$ can be realized. (Associate $2^\mathbb{N}$ with the unit interval. Then construct a partial computable maps which maps all reals strictly between $\sum_{n<m} p(n)$ and $\sum_{n<m+1} p(n)$ to $m$.) Last, if $f$ is merely partial computable, then first notice that $p(n)$ is no longer a measure since it doesn't sum to one. Instead, the sum is at most one. Also, $p(n)$ is lower semi-computable (a.k.a. left-c.e., computable from below, among many other terms). Such a measure is called a discrete semi-measure in the literature. Again, one can see that every discrete semi-measure can be realized this way.

Now, consider the case of partial computable functions of type $f\colon 2^\mathbb{N} \rightarrow 2^\mathbb{N}$. (I am assuming the OP is familiar with this concept.) First, we will consider the case where the domain of $f$ is measure one. The measure $P$ on the output can be measured by the probability $P(\sigma)$ that the finite bit-string $\sigma$ is an initial segment of some output of $f$. Notice in the case where the domain of $f$ is measure one, then $P()=1$ and $P(\sigma 0) + P(\sigma 1) = P(\sigma)$. (By Caratheodory extension theorem, this describes a Borel probability measure on $2^\mathbb{N}$. Conversely, all Borel probability measures can be given this way.) Moreover, by the same argument as in the $\mathbb{N}$ case above, $P(\sigma)$ must be computable uniformly in $\sigma$. Such a measure is called a computable probability measure. It is well-known (using an argument similar to the case of $\mathbb{N}$) that all such computable probability measures can be realized this way. (If we require that $f$ is total, then by compactness, $P(\sigma)$ must be additionally a dyadic rational uniformly in $\sigma$. Again, such measures can all be obtained this way.)

Now, if $f$ is partial then there is not a probability measure on the outputs (since there is an output with probability less than one). Then we have two ways of thinking about this problem. One way is to just consider the values $P(\sigma)$ mentioned above. In that case, we need to be clear about the machine that computes $f$. There are many models of computation from $2^\mathbb{N}$ to $2^\mathbb{N}$. One is called a monotone machine. That is a partial computable function $M:2^* \rightarrow 2^*$ (finite strings to finite strings) such that if $\tau \succeq \sigma$ then $M(\tau) \succeq M(\sigma)$ assuming $M(\tau)$ halts. Then $P(\sigma)$ now makes sense. It satisfies the properties $P() \leq 1$, $P(\sigma 0) + P(\sigma 1) \leq P(\sigma)$, and $P$ is lower semicomputable. This is called a continuous semimeasure. Levin (in his thesis?) showed that all continuous semimeasures can be produced this way.

Finally, we could alternately calculate the measure $Q$ on $2^\mathbb{N}$ such that $Q(\sigma)$ is Prob($f$ has an infinite output sequence starting with $\sigma$ given a random input). If $P$ is the continuous semi measure from before, then $Q(\sigma)=\inf_n \sum_{\tau:|\tau|=n} P(\sigma\, \tau)$. I don't know a better characterization of such measures $Q$.