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 with equal probability.
Equivalently, 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.)
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-RPL, BPLP, and ZPLP.
A quantum computer is another model of computation that is inherently probabilistic.
See also: randomized algorithm
External link
- NIST website on probabilistic Turing machines (http://www.nist.gov/dads/HTML/probablturng.html)es:Máquina de Turing probabilística