Probabilistic Turing machine: Difference between revisions

Revision as of 08:22, 2 April 2020

Revision as of 08:23, 2 April 2020

Line 1:

{{turing}}

In [[theoretical computer 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]]. As a consequence, a probabilistic Turing machine can (unlike a deterministic Turing Machine) have [[stochastic]] results; that is, on a given input and instruction state machine, it may have different run times, or it may not halt at all; furtherfurthermore, it may accept an input in one execution and reject the same input in another execution.

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''.