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 $&gt; 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!
If you just consider consecutive samples then, for most kinds of PRNGs the answer is that you can't distinguish them from true RNGs.

If you consider large input samples, then, in principle (if you don't take complexity issues into account), you can always distinguish a PRNG from true randomness:

For each PRNG $r$, seed length $L$ and starting point $x$ there exist a sample sequence length $k$ such that $f([r(seed, x),\ r(seed, x+1),\ \dots,\  r(seed, x+k-1)])\ =\ 1$ with certainty, and $f(\dots)\ =\ 0$ for any other sequence,
where $r(seed, n)$ is the n-th sample generated by the PRNG initialized with $seed$.

If the PRNG has finitely many states, as it is the case with all the PRNGs commonly in use, then the sample sequence length $k$ is independent of the seed length and starting point.

The distinguishing algorithm $f(\cdot,\ \cdot)$ can be just a brute-force search that tries in order all possible initial states to check whether they produce the sample sequence. Of course, for large state spaces, this is unpractical.
Moreover, the output sequence of a finite-state PRNG is periodic or eventually becomes periodic, although the period can be very large.

The design goal of cryptographically-secure PRNGs is to ensure that no method substantially faster than brute-force search can be used to distinguish them from true RNGs. Currently, various PRNGs are believed to be cryptographically-secure, though no mathematical proof exists.

Cryptographically-insecure PRNGs like the Mersenne Twister can be easily distinguished from true RNGs by observing a relatively short sample sequence.