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.
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.