Probabilistic Turing Machine

See: Non-Deterministic Turing Machine, Probability Function.

---

---

References

• (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Probabilistic_Turing_machine
  • In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which randomly chooses between the available transitions at each point according to some probability distribution.
  • In the case of equal probabilities for the transitions, it can be defined as a deterministic Turing machine having an additional "write" instruction where the value of the write is uniformly distributed in the Turing Machine's alphabet (generally, an equal likelihood of writing a '1' or a '0' on to the tape.) Another common reformulation is simply a deterministic Turing machine with an added tape full of random bits called the random tape.
  • As a consequence, a probabilistic Turing machine can (unlike a deterministic Turing Machine) have stochastic results; on a given input and instruction state machine, it may have different run times, or it may not halt at all; further, it may accept an input in one execution and reject the same input in another execution.
  • Therefore the notion of acceptance of a string by a probabilistic Turing machine can be defined in different ways. Various polynomial-time randomized complexity classes that result from different definitions of acceptance include RP, Co-RP, BPP and ZPP. If we restrict the machine to logarithmic space instead of polynomial time, we obtain the analogous RL, Co-RL, BPL, and ZPL. If we enforce both restrictions, we get RLP, Co-RLP, BPLP, and ZPLP.

---