Skip to main content
edited tags
Link
Kaveh
  • 21.8k
  • 8
  • 84
  • 185
Tweeted twitter.com/#!/StackCSTheory/status/46712966086795265
Source Link
quanta
  • 221
  • 1
  • 4

Algorithmic distinctions between random and pseudorandom.

Given a specific pseudo random number generator (e.g. Mersenne twister) $r()$ and a true random number generator $q()$ is there an algorithm $f(x,y)$ such that:

  • $f(r(),r()) = 1$ almost always.
  • $f(q(),q()) = 0$ almost always.

It should be noted that $f()$ stores no state, it only takes the return values of two consecutive calls as its parameter: we can also consider the case of a vector of $n$ calls as input.

"almost always" may be interpreted quite liberally, it could return this result with $> 2/3$ probability or the long term average could tend towards this limit.

I would also appreciate any insight on the same question for an unknown pseudo-random number generator (i.e. an arbitrary Turing machine) as $r()$. Thanks very much!