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 defined in different ways. Various randomized complexity classes that result from different definitions of acceptance include RP, Co-RP, BPP and ZPP.
A quantum computer is another model of computation that is inherently probabilistic.
See also: randomized algorithm
