math - Quantifying the non-randomness of a specialized random generator? -

i read this interesting question random number generator never generates same value 3 consecutive times. makes random number generator different standard uniform random number generator, i'm not sure how quantitatively describe how generator differs generator didn't have property.

suppose handed me 2 random number generators, r , s, r true random number generator , s true random number generator has been modified never produce same value 3 consecutive times. if didn't tell me 1 r or s, way can think of detect run generators until 1 of them produced same value 3 consecutive times.

my question - there better algorithm telling 2 generators apart? restriction of not producing same number 3 times somehow affect observable behavior of generator in way other preventing 3 of same value coming in row?

as consequence of rice's theorem, there no way tell which.

proof: let l output of normal rng. let l' l, sequences of length >= 3 removed. tms recognize l', not. therefore, rice's theorem, determining if tm accepts l' not decidable.

as others have noted, may able make assertion "it has run n steps without repeating 3 times", can never make leap "it never repeat digit 3 times." more appropriately, there exists @ least 1 machine can't determine whether or not meets criterion.

caveat: if had random generator (e.g. nuclear decay), possible rice's theorem not apply. intuition theorem still holds these machines, i've never heard discussed.

edit: secondary proof. suppose p(x) determines high probability whether or not x accepts l'. can construct (infinite number of) programs f like:

f(x): if x(f), don't accept l'       else, accept l' 

p cannot determine behavior of f(p). moreover, p correctly predicts behavior of g. can construct:

f'(x): if x(f'), don't accept l'        else, run g(x) 

so every case, there must exist @ least 1 bad case.