Probabilistic Turing machine: Difference between revisions

Revision as of 10:01, 14 April 2020

Revision as of 03:58, 2 May 2020

Line 1:

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

{{turing}}

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 machine]]s having an additional "write" instruction where the value of the write is [[uniform distribution (discrete)|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.<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==

Line 21 ⟶ 22:

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 selection of transition function at each step of the computation resembles a coin flip.

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 accomodateaccommodate 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 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>

Line 47 ⟶ 48:

==External links==

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

{{DEFAULTSORT:Probabilistic Turing Machine}}