Probabilistic Turing machine

A Probabililstic Turing Machine is equivalent to a <a href=http://www.wikipedia.org/wiki/Turing_machine">Turing Machine</a> 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.