Content deleted Content added
m Dating maintenance tags: {{No sources}} |
No edit summary Tags: Mobile edit Mobile web edit |
||
Line 3:
{{turing}}
In [[computability theory]], a '''probabilistic Turing machine''' is a [[non-deterministic Turing machine]] which chooses between the available transitions at each point according to some [[probability distribution]].
kip
In the case of equal probabilities for the transitions, it can be defined as a deterministic [[Turing machine]] having an additional "write" instruction where the value of the write is [[uniform distribution (discrete)|uniformly distributed]] in the Turing Machine's alphabet (generally, an equal likelihood of writing a '1' or a '0' on to the tape.) Another common reformulation is simply a [[deterministic Turing machine]] with an added tape full of random bits called the ''random tape''.
| |||