I'm wondering whether a Turing Machine with access to a random number generator is equivalent in power to an ordinary Turing Machine. The RNG is implemented here as a privileged instruction that reads a $0$ or $1$ from an otherwise inaccessible entropy source and then moves the head to a new state as if it had read an actual $0$ or $1$ from the tape.

I've heard the result stated before that a "deterministic turing machine can simulate a non-deterministic turing machine", but I'm not sure how to set up the definitions so that this statement is provable.

The thing I'm struggling with is how to define "equivalent in power" in this context.

If all levels of computation are defined in such a way that they mandate determinism, then the combination of a Turing Machine and an entropy source is not, itself, a computer at any level in the hierarchy. This seems like a reasonable thing to do. A halting oracle is deterministic, so some exotic forms of computation are captured here.

Now suppose computation is defined in such a way that a deterministic program is just a degenerate case of a non-deterministic one. In this setting a program produces a distribution over pure results. A deterministic program is just one that always produces a distribution with all the mass under one pure result. In this setting, a TM without access to an entropy source cannot return all the distributions, therefore it's less powerful.

These frameworks for posing the question seem ad hoc to me. Non-determinism is either prohibited or baked in. What's the most natural way to state the question formally?

  • $\begingroup$ The concept of “powerful” in computation is basically wether or not something is equivalent to a Turing machine. This depends on whether it can simulate or be simulated by a Turing Machine. A Turing Machine with access to a random oracle is obviously equivalent to one without it iff a random oracle can be obtained from a deterministic algorithm. Now there seems to be some sort of contradiction arising from the definition of a random oracle... $\endgroup$ – Μάρκος Καραμέρης Oct 22 '18 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.