 Probabilistic Turing machine

Turing machine(s) Machina  Universal Turing machine
 Alternating Turing machine
 Quantum Turing machine
 Readonly Turing machine
 Readonly right moving Turing Machines
 Probabilistic Turing machine
 Multitrack Turing machine
 Turing machine equivalents
 Turing machine examples
 Wolfram's 2state 3symbol..
Science This box: view · computability theory, a probabilistic Turing machine is a nondeterministic Turing machine which randomly 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 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.
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.
Therefore the notion of acceptance of a string by a probabilistic Turing machine can be defined in different ways. Various polynomialtime randomized complexity classes that result from different definitions of acceptance include RP, CoRP, BPP and ZPP. If we restrict the machine to logarithmic space instead of polynomial time, we obtain the analogous RL, CoRL, BPL, and ZPL. If we enforce both restrictions, we get RLP, CoRLP, BPLP, and ZPLP.
Probabilistic computation is also critical for the definition of most classes of interactive proof systems, in which the verifier machine depends on randomness to avoid being predicted and tricked by the allpowerful prover machine. For example, the class IP equals PSPACE, but if randomness is removed from the verifier, we are left with only NP, which is not known but widely believed to be a considerably smaller class.
One of the central questions of complexity theory is whether randomness adds power; that is, is there a problem which can be solved in polynomial time by a probabilistic Turing machine but not a deterministic Turing machine? Or can deterministic Turing machines efficiently simulate all probabilistic Turing machines with at most a polynomial slowdown? It is currently widely believed by researchers^{[who?]} that the latter is the case, which would imply P = BPP. The same question for log space instead of polynomial time (does L = BPLP?) is even more widely believed to be true. On the other hand, the power randomness gives to interactive proof systems and the simple algorithms it creates for difficult problems such as polynomialtime primality testing and logspace graph connectedness testing suggest that randomness may add power.
A quantum computer is another model of computation that is inherently probabilistic.
See also
External links
Categories: Models of computation
 Probabilistic complexity theory
 Turing machine
Wikimedia Foundation. 2010.
Look at other dictionaries:
Turing machine equivalents — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… … Wikipedia
Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… … Wikipedia
Nondeterministic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… … Wikipedia
Multitrack Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… … Wikipedia
Quantum Turing machine — A Quantum Turing machine (QTM) is an abstract machine used to model the effect of a quantum computer. It provides a very simple model which captures all of the power of quantum computation. Any quantum algorithm can be expressed formally as a… … Wikipedia
Readonly Turing machine — A read only Turing machine or Two way deterministic finite state automaton (2DFA) is class of models of computability that behave like a standard Turing machine and can move in both directions across input, except cannot write to its input tape.… … Wikipedia
Church–Turing thesis — Church s thesis redirects here. For the constructive mathematics assertion, see Church s thesis (constructive mathematics). In computability theory, the Church–Turing thesis (also known as the Church–Turing conjecture, Church s thesis, Church s… … Wikipedia
Pointer machine — In theoretical computer science a pointer machine is an atomistic abstract computational machine model akin to the Random access machine.Depending on the type, a pointer machine may be called a linking automaton, a KU machine, an SMM, an… … Wikipedia
Nondeterministic finitestate machine — In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. This distinguishes … Wikipedia
Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… … Wikipedia
18+© Academic, 20002024 Contact us: Technical Support, Advertising
Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx.Share the article and excerpts
Probabilistic Turing machine
 Probabilistic Turing machine

Turing machine(s) Machina  Universal Turing machine
 Alternating Turing machine
 Quantum Turing machine
 Readonly Turing machine
 Readonly right moving Turing Machines
 Probabilistic Turing machine
 Multitrack Turing machine
 Turing machine equivalents
 Turing machine examples
 Wolfram's 2state 3symbol..
Science