Probabilistic Turing machine: Difference between revisions

Revision as of 08:02, 2 April 2020

Revision as of 08:04, 2 April 2020

Line 2:

{{unsolved|computer science|Is '''P''' {{=}} '''BPP''' ?}}

{{turing}}

In [[computabilitytheoretical theorycomputer science]], 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''.