Encyclopedia > Probabilistic Turing Machine

  Article Content

Probabilistic Turing Machine

A probabililstic Turing machine, in computability theory, is equivalent to a Turing machine except that it has an additional instruction that allows it to randomly choose an execution path. An example of such an instruction would be a "write" instruction where the value of the write is random and equally distributed between the characters in the Turing Machine's alphabet (generally, an equal likelihood of writing a '1' or a '0' to the Turing Machine's tape.)

As a consequence, a probabalistic Turing machine can (unlike a Turing Machine) have stochastic results; on a given input and instruction state machine, it may have different run times, or it may not halt at all.

A non-deterministic Turing machine is like a probablistic one, except it guesses the correct answer (if that applies) every time. It has been proposed that a quantum computer is an example of this.

External Link NIST website on probabilistic Turing machines (http://www.nist.gov/dads/HTML/probablturng)

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Springs, New York

... town. The population density is 225.9/km² (584.8/mi²). There are 3,878 housing units at an average density of 177.0/km² (458.2/mi²). The racial ...

This page was created in 32.5 ms