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
Digital Rights Management

... protection" systems: Serial copy management system[?] (SCMS) Macrovision iTunes Windows media player[?] DRM and document restriction technology Opponents ...

This page was created in 33 ms