Description

A probabilistic Turing machine is a type of nondeterministic Turing machine in which each nondeterministic step is a "coin-flip", that is, at each step there are two possible next moves and the Turing machine probabilistically selects which move to take.

Formal definition

A probabilistic Turing machine can be formally defined as the 7-tuple , where
* is a finite set of states
* is the input alphabet
* is a tape alphabet, which includes

1.Previous
3.Next