Content deleted Content added
m minor wording adjustments |
added Formal definition section |
||
Line 8:
==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==
A probabilistic Turing machine can be formally defined as a 7-tuple <math>M=(Q, \Sigma, \Gamma, \iota, 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>\sqcup</math>
*<math>\iota \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 the movement to the left and <math>R</math> is the movement 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.
==Complexity classes==
| |||