2. Probabilistic Turing Machines

Probabilistic Turing Machines are defined like any other Turing Machine but we instead substitute a different transition function:

$$\delta (\text{current state},\text{read symbol})\to \text{prob. distribution on possible instructions}$$

The sample space therefore becomes:

$$S=\mathcal{P}(Q\times \Sigma \cup \{\bigsqcup \}\times \{\leftarrow ,\to \})$$

Each branching transition now has an associated probability, and much like non-deterministic machines, we branch out when evaluating it. We can find the probability of a terminating accepting / rejecting state by multiplying all probabilities down the branch.

Acceptance Criteria: we can compute the possibility that a PTM $M$ accepts an input word $w$ by multiplying the probabilities along all the paths that lead to the accept state and adding them together.

Any numerical property we associate with a computation can be considered a random variable and hence we could also find its variance and S.D.:

• Termination time, $T(n)$
• Amount of space / time used, $S(n)$
• And so on.