Content deleted Content added
m →Formal definition: wording adjustment |
→Formal definition: added criteria for a language to be recognized |
||
Line 20:
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 for the computation to follow 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. Thus, 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>
==Complexity classes==
| |||