Rule 30

[rokicki]

So because of the Rule 30 prizes that were announced https://blog.wolfram.com/2019/10/01/ann ... 30-prizes/ I've been spending too much time playing with rule 30.

The left side of Rule 30 shows some patterns, so I was wondering what those looked like. The period of the leftward diagonal columns apparently always becomes periodic (this can be proved). So far, through column 457 million, the highest period I've seen is just 32. This is a bit surprising to me, since the periods went through 2, 4, 8, and 16 pretty quickly. Anyone want to make a guess on when (or if!) the period of the left columns will double again, to 64?

By comparison period doubling on the *right* side happens remarkably quickly.

[Freywa]

I can interpret the Rule 30 Prizes as kinds of vanity prizes, somewhat like the old Eternity Puzzle. They are vanity prizes because Stephen Wolfram defined Rule 30 (and the rest of the elementary cellular automata) first. It's like saying "here's my puzzle, solve this and you win some money".

The difference between these prizes and, say, the Clay Millennium Prizes, both awarding sums of money to unsolved mathematical problems, is that the latter features well-known open problems while the former focuses on a domain only a handful of enthuisasts dabble in (like us). It is somewhat of a joke that Mathematica has too many features, too many special commands for just about anything "computational" you can imagine. Better to build your own programs from open-source parts.

The lure of money also matters to mathematicians less than ever. Unlike (most branches of) physics or chemistry, the bare essentials really are pen, paper and a decent computer. Everyone can do it. That lots of Mathematica code and graphics are included in the blog post announcing the prizes makes said post feel less like a sincere challenge and more of an indirect advertisement for Wolfram products.

In short, while the solution of the Rule 30 Prizes would indeed contribute to mathematical knowledge, the solutions would not be terribly useful because the problem domain is not of general interest.

[rokicki]

Well, Rule30 is pretty fundamental, as it's the simplest CA exhibiting the type of behavior that it does.

And while I don't disagree with you, the only reason I do any of this is because it's fun, not because it has any fundamental importance. For instance, in this particular case, I was able to use this problem to further my knowledge of OpenCL and GPU programming, something I've always had some interest in.

I was able to validate all one billion bits of the center column data that Wolfram has in their data repository (yes, they are correct).

If I had the chops I'd probably try some of the Clay prizes, but we all do what we can.

[Freywa]

I see potential in Polymath Project-like collaborations to solve things like these. We work on such problems primarily for fun, we do what we can, yes. What I'm saying is that monetary prizes "perpetuate the myth of the lone genius", as I recall one criticism of the Fundamental Physics Prize (US$3 million). The public media, tending to single things out, seems to be contributing to that myth as well.

Remember that Perelman declined the Clay prize and Fields Medal that were sent his way.

[praosylen]

So here's an actual observation I have on Rule 30:

Code: Select all

x = 10984, y = 1, rule = W30
o6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo!

Observe the rightmost side of the agar as the pattern evolves over time. Note that, surprisingly, it does not decay at all, even as chaos spreads to the right of the agar's edge. Eight columns to the right of the final "on" cell appear to eventually become periodic, but there is no clear indication that any further ones do. Nevertheless, these columns are clearly not random: for example, the first seemingly aperiodic columns never appears to be "on" in successive generations (and at least the next few columns have clear, visually-apparent patterns). In fact, I would conjecture (of the pattern defined by the boundary between of an infinite repeating segment of this agar on the left and vacuum on the rights) 1) that no column eventually becomes random (for some as-yet-to-be-determined definition of random) and 2) that successive columns to the right approach this definition of randomness in the limit. No idea how to prove this, though, and I don't necessarily see how these observations could translate to the problem of vacuum on both sides.

(Note that under different initial conditions, this agar is able to decay a small amount before appearing to stabilize):

Code: Select all

x = 218, y = 1, rule = W30
o6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo6bo
6bo6bo6bo6bo6bo6b2o4b2o3b4o!

Many other agars appear to produce intermediate effects between vacuum and this one, decaying at typically subluminal (but occasionally luminal) speeds to the left and exhibiting periodicity along leftward paths of equal speed to the decay, increasing faster in period for slower decay speeds.

Also observe that this agar:

Code: Select all

x = 560, y = 1, rule = W30
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo2bo
!

grows instead of decaying, but does so at a rate that appears completely irregular, even as a few patterns are visually apparent to suggest it, too, is nonrandom.

[praosylen]

I just made a rule to simulate running W30 "sideways":

Code: Select all

@RULE sideways-W30

@TABLE

n_states:9
neighborhood:Moore
symmetries:none

#C state 0: undetermined
#C state 1: untested off
#C state 2: untested on
#C state 3: off with off to the right
#C state 4: on with off to the right
#C state 5: off with on to the right
#C state 6: on with on to the right
#C state 7: history off
#C state 8: history on

var aa = {0,1,2,3,4,5,6,7,8]
var ab = aa
var ac = aa
var ad = aa
var ae = aa
var af = aa
var ag = aa
var ah = aa
var fx = {1,3,5,7}
var nx = {2,4,6,8}
var fy = {3,5}
var ny = {4,6}

1,aa,ab,fx,ac,ad,ae,af,ag,3
2,aa,ab,fx,ac,ad,ae,af,ag,4
1,aa,ab,nx,ac,ad,ae,af,ag,5
2,aa,ab,nx,ac,ad,ae,af,ag,6
0,aa,ab,3,fx,ac,ad,ae,af,1
0,aa,ab,3,nx,ac,ad,ae,af,2
0,aa,ab,4,fx,ac,ad,ae,af,2
0,aa,ab,4,nx,ac,ad,ae,af,1
0,aa,ab,5,fx,ac,ad,ae,af,2
0,aa,ab,5,nx,ac,ad,ae,af,1
0,aa,ab,6,fx,ac,ad,ae,af,2
0,aa,ab,6,nx,ac,ad,ae,af,1
fy,aa,ab,ac,ad,ae,af,ag,ah,7
ny,aa,ab,ac,ad,ae,af,ag,ah,8

@COLORS
1 60  60  128
2 128 128 255
3 60  128  60
4 128 255 128
5 128  60  60
6 255 128 128
7 60  60  60
8 255 255 255

Example, using 100 generations worth of the center column and the column immediately to the right of a single cell's evolution:

Code: Select all

x = 1, y = 1, rule = W30
o!

Code: Select all

x = 2, y = 100, rule = sideways-W30
BA$2B$2A$2B$BA$2B$2A$2A$2B$BA$AB$AB$AB$2B$2A$BA$BA$2A$AB$2B$2A$AB$2B$
BA$2B$2A$BA$AB$2B$BA$BA$2A$AB$2B$BA$2B$2A$BA$AB$2B$2A$BA$BA$2A$AB$AB$
AB$2B$BA$AB$AB$2B$2A$BA$AB$2B$BA$2A$2B$2A$BA$AB$2B$BA$BA$BA$BA$BA$2A$
AB$AB$AB$2B$BA$BA$BA$2A$AB$AB$2B$2A$BA$2A$2B$BA$2B$2A$2A$AB$AB$AB$2B$
2A$2A$2B$2A$BA$BA$2A$AB!

EDIT: I just noticed that it seems to support up-and-to-the-left diagonal deduction, too.
EDIT 2: Example:

Code: Select all

x = 17, y = 16, rule = sideways-W30:T1024+16,16
15.AB$14.2A$13.2A$12.2A$11.2A$10.2A$9.AB$8.AB$7.2A$6.AB$5.AB$4.AB$3.A
B$2.AB$.2A$2A!

EDIT 3: Also, a rule which will only run W30 in the particular cells you want it to:

Code: Select all

@RULE local-W30
@TABLE
n_states:3
neighborhood:Moore
symmetries:none
var aa = {0,1,2}
var ab = aa
var ac = aa
var ad = aa
var ae = aa
2,0,0,aa,ab,ac,ad,ae,0,0
2,0,1,aa,ab,ac,ad,ae,0,1
2,1,0,aa,ab,ac,ad,ae,0,1
2,1,1,aa,ab,ac,ad,ae,0,1
2,0,0,aa,ab,ac,ad,ae,1,1
2,0,1,aa,ab,ac,ad,ae,1,0
2,1,0,aa,ab,ac,ad,ae,1,0
2,1,1,aa,ab,ac,ad,ae,1,0
@COLORS
1 255 255 255
2 192 128 255