SIAM Journal on Computing · 1977 · 694 citations · 17 references
ComputingComputer ScienceMathematicsAlgorithmsProbability TheoryTheory Of ComputationComputability TheoryComputational ComplexityComputational Complexity ClassesFinite-state MachinesRecursion TheoryTuring MachinesComputational Complexity Of LanguagesDeterministic Turing MachinesNondeterministic Turing MachinesPartial Recursive FunctionsPolynomial Time ComplexityProbabilistic ComputationProbabilistic Turing MachinesRecursive Functions
A probabilistic Turing machine is a Turing machine with the ability to make decisions based on the outcomes of unbiased coin tosses. The partial function computed by a probabilistic machine is defined by assigning to each input the output which occurs with probability greater than $\frac{1}{2}$. With this definition, only partial recursive functions are probabilistically computable. The run time and tape of probabilistic machines are defined. A palindrome-like language is described that can be recognized faster by one-tape probabilistic Turing machines than by one-tape deterministic Turing machines. It is shown that every nondeterministic machine can be simulated in the same space by a probabilistic machine with small error probability. Several classes of languages recognized probabilistically in polynomial time are defined and compared with $NP$.
17
Information Theory and Reliable Communication
David A. Bell · Electronics and Power · 1969 · 4K citations
Computation: Finite and Infinite Machines.
D. A. Clarke, Marvin Minsky · American Mathematical Monthly · 1968 · 2.6K citations
Theory of Recursive Functions and Effective Computability
D. C. Cooper · The Computer Journal · 1969 · 2.6K citations · Full text
J. J. Stiffler · 1971 · 1.4K citations