3
$\begingroup$

Is there any computable infinite pseudorandom sequence of 0's and 1's which have been proven to be normal?

  • 0
    What do you mean by "pseudorandom"?2011-11-22

2 Answers 2

0

Yes, the Champernowne number, which you get by concatenating the numbers 1, 2, 3, etc: in binary, 1101110010111011111000....

EDIT: There is some unease here about what exactly is meant by the word, pseudorandom. When in doubt, consult Wikipedia:

"Pseudorandom sequences typically exhibit statistical randomness while being generated by an entirely deterministic causal process."

Well, any sequence that is normal certainly exhibits a large amount of statistical randomness, and the Champernowne number is certainly generated by an entirely deterministic causal process, so I reckon we pass the Wikipedia test.

  • 0
    *If* one has a generator of "pseudorandom" bits, is there a way to use it to pseudorandomly modify the above sequence in a way that guarantees both base-2 normality and pseudorandomness of the resulting sequence (for some given definition of "pseudorandom")?2011-11-22
1

Possibly yes; viz., the binary expansions of various computable absolutely normal real numbers said to be "constructed" via algorithms in Becher & Figueira.

However, as far as I can see, the paper claims to prove the existence of certain algorithms without describing how to actually implement them. That is, it does not describe how to actually compute the digits (no digits are given explicitly) -- so it might be difficult to determine whether they are "pseudorandom".