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!