Probabilistic Turing machine

In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turing machine can—unlike a deterministic Turing Machine—have stochastic results; that is, on a given input and instruction state machine, it may have different run times, or it may not halt at all; furthermore, it may accept an input in one execution and reject the same input in another execution.

In the case of equal probabilities for the transitions, probabilistic Turing machines can be defined as deterministic Turing machines having an additional “write” instruction where the value of the write is uniformly distributed in the Turing Machine’s alphabet (generally, an equal likelihood of writing a “1” or a “0” on to the tape). Another common reformulation is simply a deterministic Turing machine with an added tape full of random bits called the “random tape”.

A quantum computer is another model of computation that is inherently probabilistic.

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.[1]{\displaystyle {\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon }

References

  • Arora, Sanjeev; Barak, Boaz (2016). Computational Complexity: A Modern Approach. Cambridge University Press. pp. 123–142. ISBN 978-0-521-42426-4.
  • Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. pp. 368–380. ISBN 978-0-534-95097-2.

Ofer Abarbanel – Executive Profile

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library