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?