Probabilistic Turing machine: Difference between revisions

Revision as of 08:21, 2 April 2020

Revision as of 08:22, 2 April 2020

Line 1:

{{no sources|date=February 2018}}

{{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; on a given input and instruction state machine, it may have different run times, or it may not halt at all; further, it may accept an input in one execution and reject the same input in another execution.