# An intuitive reason why the “Rule 30” CA is random/pseudorandom?

I'm a little bit hesitant to ask this here, so please notice the tag. My hope is that someone will have a more satisfying answer than what I've heard before...

A long time ago I read (perhaps 'browsed' is a better word) Wolfram's "A New Kind of Science". There are many many references to the "Rule 30" CA - http://mathworld.wolfram.com/Rule30.html. However, no intuitive reasoning for it's random/pseudorandom behavior is provided prior to a digression to the importance of the discovery. I was recently reminded of this when I heard that Mathematica (a program I use quite frequently) uses certain outputs from this CA as its random number generator.

So my question is - beyond 'numerical phenomenology' is there an intuitive understanding why Rule 30 should behave in this random/pseudorandom manner?

-
I heard that Feynman also had no intuition for it... which is not exactly hopeful. =) –  Mensen Oct 26 '09 at 22:49
I don't think this needs or deserves the "soft-question" tag you gave it. I'll add the tags NKS (oh dear ..., but I think we'll survive) and cellular-automata, but leave you to remove the soft-question tag. +1 –  Scott Morrison Oct 27 '09 at 1:23
Ought there be an "intuition" tag? I see there's already "geometric-intuition". –  Alex Fink Oct 27 '09 at 1:45
Scott has provoked me to hesitantly remove the 'soft-question' tag I have assigned this question. Also, I love the idea of the intuition tag. –  Mensen Oct 27 '09 at 10:23

If you look at the results of elementary cellular automata from mathworld, most of them seem to have some kind of symmetry. (I don't want to make "symmetry" formal here; what I mean is that you get nice patterns of some sort.)

But I suspect that in general, the results of cellular automata are psuedorandom. (I haven't looked at this too closely.)

So if I had to guess, I would say that the answer is just that most CAs on small neighborhoods are "nice", and most CAs on large neighborhoods aren't. Rule 30 is not sporadic, but it's the first example of a family that eventually predominates.

-
Dear Michael, "But I suspect that in general, the results of cellular automata are psuedorandom..." Thank you for sharing your intuition - based on the published images on the elementary CAs, I agree with you. However, I'm having a difficult time coming up with a convincing argument for why this would be true... beyond appealing to results from some kind of statistical 'tour de force' through all the elementary CAs using random initial conditions of varying length. –  Mensen Oct 27 '09 at 12:09
I'd say more, but I really don't know much about cellular automata. All I have is the intuition I already gave. –  Michael Lugo Oct 27 '09 at 15:33
Michael, Thank you nevertheless. –  Mensen Oct 27 '09 at 19:38

Well, here are some thoughts of mine.

You want triangular shape, so you fix 000 -> 0 ; 100 -> 1 ; 001 -> 1. Now you don't want symmetry, so the only way for you is to assign different values to 011 and 110, say 011 -> 1 and 110 -> 0.

Now we kind of want lots of 111s to disappear fast, which is kind of required for random generators, so 111 -> 0.

We're left with choices for 101 and 010, of which there are 4: 26, 30, 58, 62. Chances are at least one of the choices will be interesting. Indeed, 30 looks pseudorandom, while others do not.

-
I don't see why we care about triangular shape a priori: it could well be that evolution from generic conditions is pseudorandom enough but evolution from (say) a single cell 1 is not. Nor why the observation about 111 is necessary: don't you do the opposite for 000? –  Alex Fink Oct 27 '09 at 1:48
Sure, that's another possibility, but I thought for this question we consider specifically evolution from 1 (other automata may indeed be better for other initial values) –  Ilya Nikokoshev Oct 28 '09 at 19:46
A nice and simple argument. –  Jose Brox Nov 11 '09 at 10:04

As I understand it Mathematica in fact uses rule 30 to generate pseudorandom numbers by just reading down a single column: so what it's exploiting is not just that rule 30 behaves pseudorandomly but that columns look more or less like strings of independent uniform random bits. If we label the four cells on which the rule is defined

 a b c   d 

it seems a lot easier to achieve this if (b,d) takes on all its possible values equally often, as rule 30 does.

In fact, the stronger property is true that rule 30 can be run leftwards. a is a (total) function of (b,c,d), therefore any two columns of cells can be completed uniquely to a halfplane extending leftwards satisfying rule 30. This is suggestive at the very least -- if more things could appear to the left of some columns than others, the columns probably wouldn't be nice and uniform and all that.

-