Probabilistic Turing machine

In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turing machine can—unlike a deterministic Turing Machine—have stochastic results; that is, on a given input and instruction state machine, it may have different run times, or it may not halt at all; furthermore, it may accept an input in one execution and reject the same input in another execution.

In the case of equal probabilities for the transitions, probabilistic Turing machines can be defined as deterministic Turing machines 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.

A quantum computer is another model of computation that is inherently probabilistic.

Description

A probabilistic Turing machine is a type of nondeterministic Turing machine in which each nondeterministic step is a coin-flip—that is, there are two possible next moves and the computation probabilistically selects which move to take.^[1]

Formal definition

A probabilistic Turing machine can be formally defined as a 7-tuple $M=(Q,\Sigma ,\Gamma ,\iota ,A,\delta _{1},\delta _{2})$ , where

$Q$ is a finite set of states
$\Sigma$ is the input alphabet
$\Gamma$ is a tape alphabet, which includes the blank symbol $\sqcup$
$\iota \in Q$ is the initial state
$A\subseteq Q$ is the set of accepting (final) states
$\delta _{1}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ is the first probabilistic transition function. $L$ is the movement to the left and $R$ is the movement to the right.
$\delta _{2}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ is the second probabilistic transition function.

At each step, the Turing machine probabilistically applies either the transition function $\delta _{1}$ or the transition function $\delta _{2}$ .^[2] This choice is made independently of all prior choices. In this way, the selection of transition function for the computation to follow resembles a coin flip.

Complexity classes

Unsolved problem in computer science

Is P = BPP ?

More unsolved problems in computer science

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 the machine is restricted to logarithmic space instead of polynomial time, the analogous RL, co-RL, BPL, and ZPL complexity classes are obtained. By enforcing both restrictions, RLP, co-RLP, BPLP, and ZPLP are yielded.

Probabilistic computation is also critical for the definition of most classes of interactive proof systems, 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 that 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^[who?] 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, as well as the simple algorithms it creates for difficult problems such as polynomial-time primality testing and log-space graph connectedness testing, suggests that randomness may add power.

Notes

^ Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. p. 368. ISBN 978-0-534-95097-2.
^ Arora, Sanjeev; Barak, Boaz (2016). Computational Complexity: A Modern Approach. Cambridge University Press. p. 125. ISBN 978-0-521-42426-4.

References

Arora, Sanjeev; Barak, Boaz (2016). Computational Complexity: A Modern Approach. Cambridge University Press. pp. 123–142. ISBN 978-0-521-42426-4.
Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. pp. 368–380. ISBN 978-0-534-95097-2.

External links

NIST website on probabilistic Turing machines

[1] Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. p. 368. ISBN 978-0-534-95097-2.

[2] Arora, Sanjeev; Barak, Boaz (2016). Computational Complexity: A Modern Approach. Cambridge University Press. p. 125. ISBN 978-0-521-42426-4.

[1]

[2]