A probabilistic Turing machine (PTM) is informally described as a non-deterministic Turing machine such that ''the next movement'' is chosen with a certain probability. Suppose that the input of a PTM $M$ is a string $x$, then the probability that $M(x)=y$ (where $y$ is another string) is simply the number of computational branches of the computational tree that halts with $y$, divided by the number of all computational branches of the PTM.
The above argument is clear for me, but I have many troubles when books say that a PTM is a random variable. Formally a random variable is a measurable function $X$ from a probability space to a measurable space, the pushforward probability induced by $X$ on the codomain is the distribution of $X$.
Now a PTM is not a function from the space of strings to itself since for a fixed string $x$ it may have different outputs, so I have problems to formalize the concept of a PTM in the context of the measure theory. To be more precise I have the following questions:
- In which way a PTM is a random variable?
- Which is the sample space?
- Which is the probability measure defined on the sample space?
- Which is the distribution of this random variable?