… keep in mind that deterministic Turing machines can trivially simulate nondeterministic Turing machines.
The problem here seems to be one of notation. You are using nondeterministic Turing machine in the formal sense of the term, where Mitchell seems to be using nondeterministic closer to “has a source of random bits.”
Trivially? I was under the impression that it involved up to a polynomial slowdown, while probabilistic Turing machines can simulate deterministic Turing machines by merely having only a single probability of 1 for each component of its transition function.
Well, wouldn’t that be because it’s all theorizing about computational complexity?
I see the point. Pseudorandom number generators would be what you mean by simulation of nondeterminism in a DTM? Would a deterministic UTM with an RNG be sufficient for AIXI to hypothesize randomness? I still don’t see how SI would be able to hypothesize Turing machines that produce bitstrings that are probabilistically similar to the bitstring it is “supposed” to replicate.
… keep in mind that deterministic Turing machines can trivially simulate nondeterministic Turing machines.
The problem here seems to be one of notation. You are using nondeterministic Turing machine in the formal sense of the term, where Mitchell seems to be using nondeterministic closer to “has a source of random bits.”
Trivially? I was under the impression that it involved up to a polynomial slowdown, while probabilistic Turing machines can simulate deterministic Turing machines by merely having only a single probability of 1 for each component of its transition function.
Algorithmically trivially, I didn’t see anyone concerned about running times.
Well, wouldn’t that be because it’s all theorizing about computational complexity?
I see the point. Pseudorandom number generators would be what you mean by simulation of nondeterminism in a DTM? Would a deterministic UTM with an RNG be sufficient for AIXI to hypothesize randomness? I still don’t see how SI would be able to hypothesize Turing machines that produce bitstrings that are probabilistically similar to the bitstring it is “supposed” to replicate.