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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What is this "certain sense"? Do you mean to shuffle? $\endgroup$
    – Raphael ♦
    Mar 13, 2015 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, 2015 at 14:10
  • 1
    $\begingroup$ There is no such thing as "more random", per se. $\endgroup$
    – Raphael ♦
    Mar 13, 2015 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, 2015 at 20:21

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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, 2015 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, 2015 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, 2015 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, 2015 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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