Content deleted Content added
No edit summary Tags: Mobile edit Mobile web edit |
CAPTAIN RAJU (talk | contribs) m Reverted 1 edit by 171.76.211.8 identified as test/vandalism using STiki |
||
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]].
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''.
| |||