|
|
|
|
|
Probabilistic Turing MachineIn 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
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|