Editing Probabilistic Turing machine (section)

==Formal definition==
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.

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