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)