Probabilistic Turing machine
Encyclopedia
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.
Probabilistic computation is also critical for the definition of most classes of interactive proof system
s, in which the verifier machine depends on randomness to avoid being predicted and tricked by the all-powerful prover machine. For example, the class IP
equals PSPACE
, but if randomness is removed from the verifier, we are left with only NP
, which is not known but widely believed to be a considerably smaller class.
One of the central questions of complexity theory is whether randomness adds power; that is, is there a problem which can be solved in polynomial time by a probabilistic Turing machine but not a deterministic Turing machine? Or can deterministic Turing machines efficiently simulate all probabilistic Turing machines with at most a polynomial slowdown? It is currently widely believed by researchers that the latter is the case, which would imply P = BPP. The same question for log space instead of polynomial time (does L = BPLP?) is even more widely believed to be true. On the other hand, the power randomness gives to interactive proof systems and the simple algorithms it creates for difficult problems such as polynomial-time primality testing and log-space graph connectedness testing suggest that randomness may add power.
A quantum computer
is another model of computation that is inherently probabilistic.
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, a probabilistic Turing machine is a non-deterministic Turing machine
Non-deterministic Turing machine
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers....
which randomly chooses between the available transitions at each point according to some probability distribution
Probability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....
.
In the case of equal probabilities for the transitions, it can be defined as a deterministic Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
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
Stochastic
Stochastic refers to systems whose behaviour is intrinsically non-deterministic. A stochastic process is one whose behavior is non-deterministic, in that a system's subsequent state is determined both by the process's predictable actions and by a random element. However, according to M. Kac and E...
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
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
that result from different definitions of acceptance include RP
RP (complexity)
In complexity theory, RP is the complexity class of problems for which a probabilistic Turing machine exists with these properties:* It always runs in polynomial time in the input size...
, 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
BPL (complexity)
In computational complexity theory, BPL , sometimes called BPLP , is the complexity class of problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with two-sided error...
, and ZPL. If we enforce both restrictions, we get RLP
RLP
In computational complexity theory, RL , sometimes called RLP , is the complexity class of problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with one-sided error...
, Co-RLP, BPLP, and ZPLP.
Probabilistic computation is also critical for the definition of most classes of interactive proof system
Interactive proof system
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a...
s, in which the verifier machine depends on randomness to avoid being predicted and tricked by the all-powerful prover machine. For example, the class IP
IP (complexity)
In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. The concept of an interactive proof system was first introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985...
equals PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
, but if randomness is removed from the verifier, we are left with only NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
, which is not known but widely believed to be a considerably smaller class.
One of the central questions of complexity theory is whether randomness adds power; that is, is there a problem which can be solved in polynomial time by a probabilistic Turing machine but not a deterministic Turing machine? Or can deterministic Turing machines efficiently simulate all probabilistic Turing machines with at most a polynomial slowdown? It is currently widely believed by researchers that the latter is the case, which would imply P = BPP. The same question for log space instead of polynomial time (does L = BPLP?) is even more widely believed to be true. On the other hand, the power randomness gives to interactive proof systems and the simple algorithms it creates for difficult problems such as polynomial-time primality testing and log-space graph connectedness testing suggest that randomness may add power.
A quantum computer
Quantum computer
A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
is another model of computation that is inherently probabilistic.