**Test** : "*A True Random Sequence Source and a computer producing a certain sequence of numbers are kept in separate rooms and judges try to tell them apart by conducting a series of tests on the digits being sent to them from each room.*"


" If the judges cannot reliably tell the computer from the Random sequence Source, the Computer is said to have passed the random generation test" 




---


With apologies to the Turing test....my question is


Q **Is the above test valid** for determining the randomness of an infinite sequence? 



> 
> 
> 


Motivation : Turing test like mechanism for random sequences.



> 
> 
> 



Random infinite sequence : Can machines generate truly random sequences.
I don't think the question is appropriate for MO either (try cs.stackexchange.com) but I'd say the question has to involve the computational capabilities of the judges.


If the judges just have ordinary computers, they have to be able to distinguish random from nonrandom sequences in polynomial time. A cryptographer would say that a sequence that passes all polynomial-time randomness tests is "pseudorandom". They like to think that encryption functions such as AES (parametrized by key size) are pseudorandom in this sense. Of course, such pseudorandomness would imply P != NP, the biggest open problem in computer science. That is, it is still (in some sense) an unsolved theoretical mystery whether cryptography can work at all.


If you assume the judges have unlimited power (normal-style computers with unlimited time and memory, i.e. they can compute anything that's Turing-computable) then instead of pseudorandomness, the property they think is randomness is "Kolmogorov randomness" which we can also call 1-randomness (we'll see why in a minute). As Noah explains, by diagonalization, even someone with a Turing machine can't actually pick out the 1-random sequences. The basic definition of a 1-random string of length N is that (relative to some fixed universal Turing machine U) there is no program smaller than N which produces it as output. Checking this property is equivalent to the famous Halting Problem for Turing machines.


Suppose though that you had a so-called oracle for the halting problem, something that given a description of a Turing machine could immediately tell you whether that machine halts. In technical jargon, this can be called a $\Pi^0\_1$-oracle machine, or a "1-machine" for short. This machine can detect 1-randomness of an N-letter string by enumerating all Turing machines of size less than N, using the 1-oracle to find and throw out the non-halting machines, then simulating all the halting ones to see if any produce the original string. The 1-machine can also run a simple program to *generate* 1-random strings of arbitrary size, by generating *all* the strings of that size and then filtering out the 1-random ones as described above.


Naturally there is the notion of a string of size N that can't be produced by a program shorter than N, even if the program runs on a 1-machine. That sort of string is called 2-random. You can detect or produce them on a machine with a halting oracle for 1-machines, i.e. a $\Pi^0\_2$-oracle machine or 2-machine. And this continues through 3-machines, 4-machines, etc. MO regular Joel David Hamkins developed the idea even further, into "infinite time Turing machines" that include $\omega$-machines, $(\omega+1)$-machines, $\omega^2, \omega^3\ldots \omega^\omega\ldots$ up through some quite high countable ordinals. I'm not sure how far into the ordinals that theory goes though, or whether the notion of $\alpha$-randomness is developed for transfinite $\alpha$. 


Anyway yeah, there is quite a body of theory around your question.


For the "feasible"-computing (i.e. polynomial time) version, you could look at Bellare and Rogaway's lecture notes on cryptography, or the more theoretical "Foundations of Cryptography" by Oded Goldreich.


For the versions with oracles, try the wikipedia article


* <http://en.wikipedia.org/wiki/Algorithmically_random_sequence>


which has some references.


