Computer science Models of computation Concept
Probabilistic Turing machine
Summary
A probabilistic Turing machine is a Turing machine that may flip fair coins and choose its next move by the outcome. Its output on an input is then a random variable, and one asks for the probability of acceptance. It is the standard model of randomised algorithms. Classes such as BPP, the problems decided in polynomial time with error probability at most , are defined with it.
Where this leads
14 pages build on this one.
Further reading
About this page
| Tag | K99S0Q0814 |
|---|---|
| URI | m2://K99S0Q0814 |
| Kind | concept |
| Writing | W0 stub |
| MSC | 68Q10, 68Q87, 68Q04 |
| Specializes | Model of computation |
| Same as | |
| Changed | 3 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
Used by
- Randomized algorithm
- Luby–Rackoff theorem
- Ciphertext indistinguishability
- RP
- BPP
- Digital signature
- Interactive proof system
- Homomorphic encryption
- One-way function
- Zero-knowledge proof
- Semantic security
- Cryptographic hash function
- PCP theorem
- ZPP