Probabilistic Turing Machine
A probabilistic 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 probabilistic 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 probabilistic 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
Referenced By
Computability Theory | Computation Theory | List of computability and complexity topics | List of mathematical topics (P-R)
|
