Computational complexity of probabilistic Turing machines

Abstract

Probabilistic Turing machines are Turing machines with the ability to flip coins in order to make random decisions. We allow probabilistic Turing machines small but nonzero error probability in computing number-theoretic functions. An example is given of a function computable more quickly by probabilistic Turing machines than by deterministic Turing machines. It is shown how probabilistic linear-bounded automata can simulate nondeterministic linear-bounded automata.