Probabilistic Turing machine: Difference between revisions

Revision as of 19:04, 25 February 2018

Latest revision as of 08:48, 3 February 2025

(46 intermediate revisions by 13 users not shown)

Line 1:

{{Short description|Mathematical model of computation}}

{{no sources}}

{{Use dmy dates|date=May 2020}}

{{unsolved|computer science|Is '''P''' {{=}} '''BPP''' ?}}

{{turing}}

In [[computabilitytheoretical theorycomputer science]], a '''probabilistic Turing machine''' is a [[non-deterministic Turing machine]] whichthat chooses between the available [[State-transition table|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, itprobabilistic Turing machines can be defined as a deterministic [[Turing machine]]s having an additional "write" instruction where the value of the write is [[uniform distribution (discrete)|uniformly distributed]] in the Turing Machinemachine'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]] (or [[quantum Turing machine]]) is another [[model of computation]] that is inherently [[probabilistic]].

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.

==Description==

Therefore, the notion of acceptance of a string by a probabilistic Turing machine can be defined in different ways. Various polynomial-time randomized [[computational complexity theory|complexity classes]] that result from different definitions of acceptance include [[RP (complexity)|RP]], co-RP, [[Bounded-error probabilistic polynomial|BPP]] and [[ZPP (complexity)|ZPP]]. If the machine is restricted to logarithmic space instead of polynomial time, the analogous [[RL (complexity)|RL]], co-RL, [[BPL (complexity)|BPL]], and [[ZPL (complexity)|ZPL]] complexity classes are obtained. By enforcing both restrictions, [[Randomized Logarithmic-space Polynomial-time|RLP]], co-RLP, [[BPLP]], and [[ZPLP]] are yielded.

A probabilistic Turing machine is a type of [[nondeterministic Turing machine]] in which each nondeterministic step is a "coin-flip", that is, at each step there are two possible next moves and the Turing machine probabilistically selects which move to take.<ref>{{cite book|last=Sipser|first=Michael|authorlink=Michael Sipser|title=Introduction to the Theory of Computation|edition=2nd|year=2006|publisher=Thomson Course Technology|___location=USA|page=368|isbn=978-0-534-95097-2|title-link=Introduction to the Theory of Computation}}</ref>

==Formal definition==

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 (complexity)|IP]]''' equals '''[[PSPACE]]''', but if randomness is removed from the verifier, we are left with only '''[[NP (complexity)|NP]]''', which is not known but widely believed to be a considerably smaller class.

A probabilistic Turing machine can be formally defined as the 7-tuple <math>M=(Q, \Sigma, \Gamma, q_0, A, \delta_1, \delta_2)</math>, where

* <math>Q</math> is a finite set of states

* <math>\Sigma</math> is the input alphabet

* <math>\Gamma</math> is a tape alphabet, which includes the blank symbol '''#'''

* <math>q_0 \in Q</math> is the initial state

* <math>A \subseteq Q</math> is the set of accepting (final) states

* <math>\delta_1: Q \times \Gamma \to Q \times \Gamma \times \{L,R\} </math> is the first probabilistic transition function. <math>L</math> is a movement one cell to the left on the Turing machine's tape and <math>R</math> is a movement one cell to the right.

* <math>\delta_2: Q \times \Gamma \to Q \times \Gamma \times \{L,R\} </math> is the second probabilistic transition function.

At each step, the Turing machine probabilistically applies either the transition function <math>\delta_1</math> or the transition function <math>\delta_2</math>.<ref>{{cite book |last1=Arora |first1=Sanjeev|author1-link=Sanjeev Arora |last2=Barak |first2=Boaz|author2-link=Boaz Barak |title=Computational Complexity: A Modern Approach |date=2016 |publisher=Cambridge University Press |isbn=978-0-521-42426-4 |page=125}}</ref> This choice is made independently of all prior choices. In this way, the process of selecting a transition function at each step of the computation resembles a coin flip.

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{{Who|date=November 2010}} 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.

The probabilistic selection of the transition function at each step introduces error into the Turing machine; that is, strings which the Turing machine is meant to accept may on some occasions be rejected and strings which the Turing machine is meant to reject may on some occasions be accepted. To accommodate this, a language <math>L</math> is said to be recognized ''with error probability <math>\epsilon</math>'' by a probabilistic Turing machine <math>M</math> if:

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

# a string <math>w</math> in <math>L</math> implies that <math>\text{Pr}[M \text{ accepts } w] \geq 1 - \epsilon</math>

# a string <math>w</math> not in <math>L</math> implies that <math>\text{Pr}[M \text{ rejects } w] \geq 1 - \epsilon</math>

==Complexity classes==

{{unsolved|computer science|Is {{noitalic|'''P''' {{=}} '''BPP'''}} ?}}

As a result of the error introduced by utilizing probabilistic coin tosses, the notion of acceptance of a string by a probabilistic Turing machine can be defined in different ways. One such notion that includes several important complexity classes is allowing for an error probability of 1/3. For instance, the complexity class '''[[Bounded-error probabilistic polynomial|BPP]]''' is defined as the class of languages recognized by a probabilistic Turing machine in [[polynomial time]] with an error probability of 1/3. Another class defined using this notion of acceptance is '''[[BPL (complexity)|BPL]]''', which is the same as '''BPP''' but places the additional restriction that languages must be solvable in [[Logarithmic growth|logarithmic]] [[space complexity|space]].

Therefore, the notion of acceptance of a string by a probabilistic Turing machine can be defined in different ways. Various polynomial-time randomized [[computationalComplexity complexity theory|complexity classesclass]]es that resultarising from differentother definitions of acceptance include '''[[RP (complexity)|RP]]''', '''co-RP''', [[Bounded-error probabilistic polynomial|BPP]] and '''[[ZPP (complexity)|ZPP]]'''. If the machine is restricted to logarithmic space instead of polynomial time, the analogous '''[[RL (complexity)|RL]]''', '''co-RL, [[BPL (complexity)|BPL]]''', and '''[[ZPL (complexity)|ZPL]]''' complexity classes are obtained. By enforcing both restrictions, '''[[Randomized Logarithmic-space Polynomial-time|RLP]]''', '''co-RLP''', '''[[BPLP]]''', and [['''ZPLP]]''' are yielded.

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 (complexity)|IP]]''' equals '''[[PSPACE]]''', but if randomness is removed from the verifier, we are left with only '''[[NP (complexity)|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 whichthat 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 currentlyknown widelythat believed'''P''' by&sube; researchers{{Who|date=November'''BPP''', 2010}}since thata thedeterministic latterTuring machine is thejust a special case of a probabilistic Turing machine. However, whichit wouldis implyuncertain whether (but widely suspected that) '''BPP''' &sube; '''P''', =implying that '''BPP''' = '''P'''. 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.

==See also==

* [[Randomized algorithm]]

==Notes==

{{reflist}}

==References==

* {{cite book |last1=Arora |first1=Sanjeev|author1-link=Sanjeev Arora |last2=Barak |first2=Boaz|author2-link=Boaz Barak |title=Computational Complexity: A Modern Approach |date=2016 |publisher=Cambridge University Press |isbn=978-0-521-42426-4 |pages=123–142}}

* {{cite book|last=Sipser|first=Michael|authorlink=Michael Sipser|title=Introduction to the Theory of Computation|edition=2nd|year=2006|publisher=Thomson Course Technology|___location=USA|isbn=978-0-534-95097-2|title-link=Introduction to the Theory of Computation|pages=368–380}}

==External links==

* [https://xlinux.nist.gov/dads/HTML/probablturng.html NIST website on probabilistic Turing machines]

{{DEFAULTSORT:Probabilistic Turing Machine}}