14
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I heard that Feynman also had no intuition for it... which is not exactly hopeful. =) $\endgroup$
    – Mensen
    Commented Oct 26, 2009 at 22:49
  • $\begingroup$ 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 $\endgroup$
    – Kim Morrison
    Commented Oct 27, 2009 at 1:23
  • $\begingroup$ Ought there be an "intuition" tag? I see there's already "geometric-intuition". $\endgroup$
    – Alex Fink
    Commented Oct 27, 2009 at 1:45
  • $\begingroup$ 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. $\endgroup$
    – Mensen
    Commented Oct 27, 2009 at 10:23
  • $\begingroup$ Now (October 2019) there are also cash prizes to win (3x 10.000$), see rule30prize.org $\endgroup$
    – Marcus
    Commented Oct 11, 2019 at 12:40

3 Answers 3

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Mensen
    Commented Oct 27, 2009 at 12:09
  • $\begingroup$ I'd say more, but I really don't know much about cellular automata. All I have is the intuition I already gave. $\endgroup$
    – Michael Lugo
    Commented Oct 27, 2009 at 15:33
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ 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? $\endgroup$
    – Alex Fink
    Commented Oct 27, 2009 at 1:48
  • $\begingroup$ 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) $\endgroup$
    – Ilya Nikokoshev
    Commented Oct 28, 2009 at 19:46
  • $\begingroup$ A nice and simple argument. $\endgroup$
    – Jose Brox
    Commented Nov 11, 2009 at 10:04
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .