1
$\begingroup$

S. Wolfram has in has book "A New Kind of Science" listed 256 simple rules of cellular automata. Which of these rules could via iteration essentially contribute to render an input sequence more random in a certain sense?

Rule 170, for examples, simply produces a left shift and evidently is not of use in this, if I don't err. My limited computations with inputs that are more or less random seem to indicate that the majority of the 256 rules are even contraproductive in this context. How could one best proceed to clarify this issue or are there already relevant published results available?

$\endgroup$
  • 1
    $\begingroup$ What is this "certain sense"? Do you mean to shuffle? $\endgroup$ – Raphael Mar 13 '15 at 12:24
  • $\begingroup$ @Raphael: I meant one could accept a statistical test as a criteria to judge that the result of application of a rule to a given sequence is more (or less) random than the original. $\endgroup$ – Mok-Kong Shen Mar 13 '15 at 14:10
  • 1
    $\begingroup$ There is no such thing as "more random", per se. $\endgroup$ – Raphael Mar 13 '15 at 17:57
  • $\begingroup$ @Raphael: You are right, since "random" is hard to exactly define practically IMHO. What I personally comonnly choose to employ as a measure is Maurer's Universal Test. If a sequence passes it, I consider it to be sufficiently random. (But this is of course merely my personal approach, other people might well disagree with me.) I am certainly interested to learn much better possibilities of comparison of sequences. $\endgroup$ – Mok-Kong Shen Mar 13 '15 at 20:21
1
$\begingroup$

Rule 30 is probably the "most random" of all 256 rules. It has been used as random number generator, but there are some issues:

  • Some initial states will result in repetitive output, which is not what we want from a random number generator. However, given that the automaton is large enough, and that the initial state is itself somewhat random, this shouldn't a problem.

  • There are better ways to generate random numbers.

$\endgroup$
  • $\begingroup$ As mentioned in my OP, I found -- by applying the rules to bit sequences obtained from bytes of chracters of books -- the majority of the 256 rules don't improve the randomness of the sequences (I use Maurer's Universal Test as a measure of that) and most of them (including rule 30) are even counter-productive. $\endgroup$ – Mok-Kong Shen Mar 20 '15 at 22:00
  • $\begingroup$ My point was, that rule 30 seems to give the best randomness, comparing to other (inequivalent) rules - not to other randomness generators. That Maurer's test looks interesting, thanks for mentioning it. $\endgroup$ – Vilius Normantas Mar 23 '15 at 18:16
  • $\begingroup$ I must beg your pardon for my error in the comment above due to a bug (found in the meantime in a code review because of your hints) in my program that attempts to rank the usefulness of the rules for my special application. The correct result is: 105, 150, 120, 135, 75, 180, 90, 165, 106, 149, 180, 90, 165, 106, 149, 89, 166, 86, 169, 45, 210, 30, 225, 101, 154, 60, 195, 102, 153, 15, 240. So rule 30 can indeed positively contribute in my application, though 105 and 150 seem to be more preferable. $\endgroup$ – Mok-Kong Shen Mar 25 '15 at 0:09
  • $\begingroup$ Both 105 and 150 are somewhat prone to periodic behaviour, if your initial state is not nearly-random. Rule 30 does not have such periodicity at all - most initial states degrade to absolute chaos in predictable (and short) time. So, rule 30 still remains my favourite when it comes to randomness. If you are interested, I can share some results from the research on entropy of these guys. $\endgroup$ – Vilius Normantas Apr 19 '15 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.