Probabilistic Turing machine: Difference between revisions

Revision as of 02:38, 6 April 2020

Revision as of 10:01, 14 April 2020

Line 21:

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. ThusTo accomodate 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>