Random infinite sequence : Can machines generate truly random sequences. [closed]

Question

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.

Answer 1

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.

Answer 2

http://search.dilbert.com/comic/Random%20Number%20Generator

Answer 3

(I'm really not sure this is appropriate for MO - mathstackexchange might be better - but this does lead into some quite interesting subjects, so I'll give a go at answering.)

So first, let me make a few obvious comments. Certainly a truly random source cannot be distinguished from a nonrandom source in a finite amount of time: if I have an agent who correctly identifies a sequence $S$ as random after the first $n$ bits, then that same agent will guess that a sequence $T$ agreeing with $S$ on the first $n$ bits is random; but there are many such computable $T$.

So the "right" way to ask this question might be: given a binary sequence $S$, is there some sort of effective test which at each moment $n$ makes a guess "random/nonrandom" (really: "noncomputable/computable," but I think this is what the OP means by "random?") and $S$ is in fact random iff there are infinitely many $n$ at which the test guesses "random"? In particular, the test cannot refuse to guess (although at a given $n$, it may take an arbitrarily long time). (There are other ways we could modify the question, but let's take this one to start with.)

Now the answer is "no," there is no such test. For suppose $\mathfrak{t}$ were such a test. Then we could build a computable sequence $S$, a finite initial segment at a time, by always searching for some way to extend $S$ so that $\mathfrak{t}$ says "random" at least once more than it already has. Either this process becomes impossible at some point - in which case $\mathfrak{t}$ is terrible, since it won't recognize as random any random sequence which begins with the finite initial segment of $S$ built so far - or this process defines a computable sequence $S$ which $\mathfrak{t}$ infinitely often thinks is random. So every specific effective randomness test fails, somehow.

On the other hand, there is no "pseudorandom" computable real: if $S$ is a computable sequence, there is a test for randomness that guesses "nonrandom" iff the string it's presented with agrees with $S$. This test is absolutely terrible, but it does successfully identify all random strings as random, and $S$ as nonrandom. Another way of phrasing it: in your words, there will always be the possibility of a "judge" who happens to know just the index for the computable sequence, and bases his decisions entirely on that.

You might object that this treats "computable sequences" in a broad way. An interesting question we can ask is the following: let's say I'm presented, one bit at a time, with a sequence I am told is computable. Can I find an index for it? This is the beginning of computability-theoretic learning theory; Jain and Stephan's paper "A tour of robust learning" might be interesting to you. (I'll add a couple other sources, which I vaguely remember but can't find right now, as I track them down.)