🚀 go-pugleaf

Consider standard deterministic Turing machines with a fixed, finite program
and an arbitrary input tape (i.e. the input is deemed separate from the
program.  Consider probabilistic versions with the program extended to
allow the generation of a true random bit.

Clearly the second model is strictly more powerful than the first, but I
am interested (for now) only in deterministic problems - that is ones
where the output and termination (if any) depend solely on the input tape.

1) Is it known whether there are any deterministic problems that can be
solved by probabilistic Turing machines but not by deterministic ones?

2) Is it known that there are no such algorithms?

3) Assuming (2), are there any deterministic problems that have a lower
complexity for probabilistic Turing machines than deterministic ones?

4) Is is known that there are no such problems?

Does anyone know of any good results/references on these questions?
Please note that I am NOT working in the automata area, but am interested
because they affect the theoretical justification for pseudorandom
numbers.  I know that there are zillions of probabilistic algorithms,
many of which predate Turing, but that isn't much help!


Nick Maclaren
University of Cambridge Computer Laboratory,
New Museums Site, Pembroke Street,
Cambridge CB2 3QG, England.
Email:  nmm1@cus.cam.ac.uk
Tel.:   +44 223 334761
Fax:    +44 223 334679