🚀 go-pugleaf

Nick Maclaren (nmm1@cus.cam.ac.uk) wrote:

: 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?

If I understand your questions, the answers to (2) and (4) are both
trivially "no".  To say that a probabilistic machine's output and
termination depend solely on the input tape means that its behavior is
the same on all sequences of bits that might result from the random
bit generator.  In particular, its output and termination will be the
same on the sequence of all 0's.  By fixing each random bit to 0, it
is easy to convert the probabilistic Turing machine into an equivalent
deterministic one.

==================================================
| Michael Fischer <fischer-michael@cs.yale.edu>  |
==================================================