Content deleted Content added
Nick Number (talk | contribs) m sp accommodate WP:TYPO; dmy dates |
→Formal definition: wording clarification |
||
Line 20:
*<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
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:
| |||