4 ms·
If I understand correctly, the key difference is that the rand() function in a Turing machine cannot generate true random numbers (I think it's something like M
by deepnotderp 7y ago
If I understand correctly, the key difference is that the rand() function in a Turing machine cannot generate true random numbers (I think it's something like Martin-Lof?).
- bo1024 7y agoPseudorandomness is related, but doesn't affect this issue. We can hook up a physically random process to a computer for a source of "true" random bits, then go from there.
- sokrates85 7y agox = rand() % 2 always gives a random number. You can't correlate them that way. Needs to be a tunable random number and technically needs to be "true" as mentioned. But I don't think that the authors would disagree with your larger point - their point is to provide polynomial speed-up over digital computers for a certain class of problems. That this can be done with classical computers isn't exactly a deep insight, it's rather obvious.