Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Probabilistic_Turing_machine> ?p ?o }
Showing triples 1 to 71 of
71
with 100 triples per page.
- Probabilistic_Turing_machine abstract "In computability theory, a probabilistic Turing machine is a non-deterministic 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 polynomial-time randomized complexity classes that result from different definitions of acceptance include RP, Co-RP, BPP and ZPP. If the machine is restricted to logarithmic space instead of polynomial time, the analogous RL, Co-RL, BPL, and ZPL complexity classes are obtained. By enforcing both restrictions, RLP, Co-RLP, BPLP, and ZPLP are yielded.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 all-powerful 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 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, as well as the simple algorithms it creates for difficult problems such as polynomial-time primality testing and log-space graph connectedness testing, suggest that randomness may add power.A quantum computer is another model of computation that is inherently probabilistic.".
- Probabilistic_Turing_machine wikiPageExternalLink probablturng.html.
- Probabilistic_Turing_machine wikiPageID "197812".
- Probabilistic_Turing_machine wikiPageLength "3617".
- Probabilistic_Turing_machine wikiPageOutDegree "26".
- Probabilistic_Turing_machine wikiPageRevisionID "705414432".
- Probabilistic_Turing_machine wikiPageWikiLink BPL_(complexity).
- Probabilistic_Turing_machine wikiPageWikiLink BPP_(complexity).
- Probabilistic_Turing_machine wikiPageWikiLink Category:Models_of_computation.
- Probabilistic_Turing_machine wikiPageWikiLink Category:Probabilistic_complexity_theory.
- Probabilistic_Turing_machine wikiPageWikiLink Category:Turing_machine.
- Probabilistic_Turing_machine wikiPageWikiLink Computability_theory.
- Probabilistic_Turing_machine wikiPageWikiLink Computational_complexity_theory.
- Probabilistic_Turing_machine wikiPageWikiLink IP_(complexity).
- Probabilistic_Turing_machine wikiPageWikiLink Interactive_proof_system.
- Probabilistic_Turing_machine wikiPageWikiLink NL_(complexity).
- Probabilistic_Turing_machine wikiPageWikiLink NP_(complexity).
- Probabilistic_Turing_machine wikiPageWikiLink Non-deterministic_Turing_machine.
- Probabilistic_Turing_machine wikiPageWikiLink PSPACE.
- Probabilistic_Turing_machine wikiPageWikiLink Probability_distribution.
- Probabilistic_Turing_machine wikiPageWikiLink Quantum_computing.
- Probabilistic_Turing_machine wikiPageWikiLink RL_(complexity).
- Probabilistic_Turing_machine wikiPageWikiLink RP_(complexity).
- Probabilistic_Turing_machine wikiPageWikiLink Randomized_algorithm.
- Probabilistic_Turing_machine wikiPageWikiLink Stochastic.
- Probabilistic_Turing_machine wikiPageWikiLink Turing_machine.
- Probabilistic_Turing_machine wikiPageWikiLink Uniform_distribution_(discrete).
- Probabilistic_Turing_machine wikiPageWikiLink ZPLP.
- Probabilistic_Turing_machine wikiPageWikiLink ZPP_(complexity).
- Probabilistic_Turing_machine wikiPageWikiLinkText "Probabilistic Machines".
- Probabilistic_Turing_machine wikiPageWikiLinkText "Probabilistic Turing Machine".
- Probabilistic_Turing_machine wikiPageWikiLinkText "Probabilistic Turing machine".
- Probabilistic_Turing_machine wikiPageWikiLinkText "probabilistic Turing machine".
- Probabilistic_Turing_machine wikiPageWikiLinkText "probabilistic model of computation".
- Probabilistic_Turing_machine wikiPageWikiLinkText "probabilistic".
- Probabilistic_Turing_machine wikiPageWikiLinkText "randomized algorithm".
- Probabilistic_Turing_machine wikiPageUsesTemplate Template:=.
- Probabilistic_Turing_machine wikiPageUsesTemplate Template:Turing.
- Probabilistic_Turing_machine wikiPageUsesTemplate Template:Unsolved.
- Probabilistic_Turing_machine wikiPageUsesTemplate Template:Who.
- Probabilistic_Turing_machine subject Category:Models_of_computation.
- Probabilistic_Turing_machine subject Category:Probabilistic_complexity_theory.
- Probabilistic_Turing_machine subject Category:Turing_machine.
- Probabilistic_Turing_machine hypernym Machine.
- Probabilistic_Turing_machine type Model.
- Probabilistic_Turing_machine type Software.
- Probabilistic_Turing_machine type Machine.
- Probabilistic_Turing_machine type Method.
- Probabilistic_Turing_machine type Model.
- Probabilistic_Turing_machine type Redirect.
- Probabilistic_Turing_machine comment "In computability theory, a probabilistic Turing machine is a non-deterministic 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. ".
- Probabilistic_Turing_machine label "Probabilistic Turing machine".
- Probabilistic_Turing_machine sameAs Q1191836.
- Probabilistic_Turing_machine sameAs Màquina_de_Turing_probabilística.
- Probabilistic_Turing_machine sameAs Probabilistische_Turingmaschine.
- Probabilistic_Turing_machine sameAs Probableca_maŝino_de_Turing.
- Probabilistic_Turing_machine sameAs Máquina_de_Turing_probabilística.
- Probabilistic_Turing_machine sameAs ماشین_تورینگ_احتمالی.
- Probabilistic_Turing_machine sameAs Machine_de_Turing_probabiliste.
- Probabilistic_Turing_machine sameAs מכונת_טיורינג_הסתברותית.
- Probabilistic_Turing_machine sameAs Probabilistički_Turingov_stroj.
- Probabilistic_Turing_machine sameAs Macchina_di_Turing_probabilistica.
- Probabilistic_Turing_machine sameAs 確率的チューリング機械.
- Probabilistic_Turing_machine sameAs 확률적_튜링_기계.
- Probabilistic_Turing_machine sameAs Máquina_de_Turing_probabilística.
- Probabilistic_Turing_machine sameAs m.01c353.
- Probabilistic_Turing_machine sameAs Вероятностная_машина_Тьюринга.
- Probabilistic_Turing_machine sameAs Q1191836.
- Probabilistic_Turing_machine sameAs 機率圖靈機.
- Probabilistic_Turing_machine wasDerivedFrom Probabilistic_Turing_machine?oldid=705414432.
- Probabilistic_Turing_machine isPrimaryTopicOf Probabilistic_Turing_machine.