Live briefing
Everything about Probabilistic Turing machine
Mathematical model of computation
In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turing machine can 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; furthermore, it may accept an input in one execution and reject the same input in another execution. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Probabilistic Turing machineA 5-minute orientation
- Pick up a classic book: Language and Automata Theory and ApplicationsThe most-reprinted book on the subject
- Read the landmark paper: Computational Complexity of Probabilistic Turing MachinesCited 486 times
- Go sideways: Complexity classA closely related topic
- Go sideways: BPP (complexity)A closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Computational Complexity of Probabilistic Turing Machines
Probabilistic Turing machines and computability
Computability by probabilistic Turing machines
On tape-bounded probabilistic Turing machine acceptors
Deterministic simulation of tape-bounded probabilistic turing machine transducers
Fast probabilistic RAM simulation of single tape turing machine computations
A note on two-dimensional probabilistic Turing machines
Computability by Probabilistic Turing Machines
📚 Books worth reading
Language and Automata Theory and ApplicationsAdrian-Horia Dediu · 2012
Introduction to the theory of computationMichael Sipser · 1996
Developments in Language TheoryMarie-Pierre Béal · 2013- 📕Causality in the sciencesPhyllis McKay Illari, Russo, Federica Dr · 2011
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Complexity class In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly…
- BPP (complexity) In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable…
- L (complexity) In computational complexity theory, L (also known as LSPACE, LOGSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved…
- ZPP (complexity) In complexity theory, ZPP (zero-error probabilistic polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists…
- PP (complexity) In complexity theory, PP, or PPT is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability…
- Arthur–Merlin protocol In computational complexity theory, an Arthur–Merlin protocol, introduced by Babai (1985), is an interactive proof system in which the verifier's coin…
- RP (complexity) In computational complexity theory, randomized polynomial time (RP) is the complexity class of decision problems for which a probabilistic Turing machine…
- Alternating Turing machine In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations…