The Probabilistic Turing machine reference article from the English Wikipedia on 24-Apr-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

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

External Link

• NIST website on probabilistic Turing machines

This is the "Probabilistic Turing machine" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.