Rule 30

Elementary Automaton

...my dear Watson

We start with an infinite one-dimensional cellular automaton (CA). At each time step all cells change their state based on the current state of their "neighborhood". For this CA we only consider the current state of the cell and the state of the cells on its immediate left and right. We will label the cells (p,q,r) where q is the cell in question. The next state of the cell is determined by a rule.
Each cell may be either "alive" or "dead". Here is a table showing every possibility:

As we can see there are 8 possible situations. If we represent the states with 1's and 0s you might notice that we form the binary representation for the numbers 0-7.

That's convenient! This means that we can store these 8 situations as numbers 0-7 and the binary will actually encode the states of the cell, or we can read the cells, interpret it as binary, and easily look up the "case" to find out what we are supposed to do. So what are we supposed to do?

The Rules

8 cases to rule them all

We have an infinite array of cells and we need to evaluate them all simultaneously in sets of 3. We know that there are only 8 unique situations, but we do not yet know what to do in each situation. We need rules for each situation that tell us if the cell in question (q) will become alive or dead. Lets lay out the 8 situations and determine our rules. Click the cells to change the rule:

Conveniently, we can again use binary to store our set of "cases" and outcomes. Each case results in a cell being alive or dead. We can think about it as true/false, on/off, but using 1/0 gives us a way store the whole story as a number between 0 and 255.

Rule 30 is one of the 256 rules. There are some open questions about rule 30 that have cash rewards if you can find (and prove) the answer.

To Infinity

...and beyond!

We have a rule and we are looking for a board to play on. The CA is supposed to be an "infinite" array and that is going to be a problem. Lets start small and work our way up to infinity.

What is the minimum input we need to play the game?

Our rule must consider the current state of the cell in question (q), the cell on it's left(p), and the cell on its right (r). So the minimum number of cells we need to start with is 3. Instead of replacing a cell with the result, lets place it below so we can see cause and effect.

(You can change the rule and initial state)

Not a very exciting game yet. Our game currently evaluates 3 cells, and outputs 1 cell. If we wanted to take another step in time we would need to evaluate more cells. Also you may notice that the initial state determines which case of our rule is used. Changing the rule does not change the case, it only determines the output.

It would be more fun if we output at least 3 cells, that way we could generate another generation from our output, but we have a problem. Every step in time is going to require the evaluation of 2 more cells, one on each end. 3->5->7->9

What is outside of the initial state?

A simple solution is to assume that all new cells from outside the current evaluation window are "dead" cells by default. As we increase the window by 2 cell every generation we simply add dead cells to the outside.

If we have to add 2 cells for each row, it is going to quickly become too big to display. After some number of steps our computer may even have a hard time computing the result.

Looking at Everything

...everywhere, all at once.

It seems as though, if we want to know what a given cell's state is after some number (N) steps, we must compute all prior steps. If we tried to look at a window that is smaller than the full output we can't assume that the cells outside our window are dead. They might be living or dead and the only way to know for sure would be to run the whole simulation. The only thing we know for sure is that those cells are either alive or dead. At each step there are 4 possible paths.

Lets look at a 5 cell slice of rule 30 and compare it to the output if we assume that the unknown cells are always dead or always alive, or randomly chosen.

OK, that's not going to work. We don't have enough information. As we move forward in time our simulation drifts further away from the truth. Is there any other information we can use?
At the moment all we know is that a cell is either on or off. If we want more information we will have to compute it. If we keep computing more info the rows will get keep getting wider, maybe we can find an alternative way of displaying it.

Over the Rainbow

...or how i learned to stop worrying and love computational irreducibility

Lets store the case in the lower three bits and the state in the fourth bit. This will also give us an opportunity to make better looking diagrams. We can choose 8 colors, one for each case, and then modify the brightness to signify if a cell is "on" or "off" like an LED.

Lets see how this looks:

That's pretty.

We can now see some pattern emerging that give us a little more information about what is happening. Previously we only had 2 kind of cells but now we have more.
How many do we have?

Impassible Combinations

...nothing is impossible.

We know that we have 8 colors x 2 states, so 16 possible cells. The color of a cell is determined by the case (the state of 3 cells above it). The state is determined by the current rule. Each rule states that a specific color is either on or off. We can't have both so we actually have half of 16 (thats 8). You can see that by looking at the color legend above.

Can all colors be neighbors?
The answer to this question is the same no matter which rule you are using. If we take the lower 2 bits of each case, we can check if they are the same as the higher 2 bits of each case.

This means that there are 16 different combinations of 2 cell. What about 3 cells?
We could make a giant table of all (512) possible combinations, or we can use the following formula

((x & 3) === (y >> 1)) && ((y & 3) === (z >> 1))

to determine that only 32 of them are possible. Each cell has two neighbors, so in this situation the middle cell must match 2 bits of the cell on the left and 2 bits of the cell on the right.

A side note here, looking at valid states, as we increased the window we saw 8,16,32... it looks like a pattern.

Number of cells	Possible configurations	Count
1 cell	`0`, `1`	`2`
2 cells	`00`, `01`, `10`, `11`	`4`
3 cells	`000...111`	`8`
4 cells	`0000...1111`	`16`
k cells	`2^k` possible bit strings	`2^k`

So what are we doing here? Adding color to 3 cells is really just the same as evaluating 5 bits right?

Connect the dots

...---...

Having a full set of 3 cell neighborhoods is a cool place to be because we need 3 cells to spawn a cell in the next generation. It would be nice to see what relation these sets have to each other. In order to do that we will need to add some cells to the outside of each set...again.

Any 5 cell row will produce one of the other three cell rows. For each of our 3 cell sets, which other sets can they spawn and which ones can spawn them? Gathering this info will let us build a directed graph. Thankfully we already have the data we need saved in our colors. The colors are essentially a record of the previous generation. All we have to do is shave off the outer bits and to see who the parents could be. This will also identify nodes that are orphans, meaning that they cannot naturally spawn from this rule, but you COULD start from there initially.

What can we do with a graph? We can walk it. Lets do a random walk and see the results.

OK thats all for now. I don't think we covered any new ground about rule 30. It certainly seems random unlike some of the other rules. It should be clear, if you played with the demos, that most of the other rules are less connected, and they have orphan nodes. Maybe it would be interesting to see what happens when we use more than 8 colors (3 bits).

If you want to generate some CA images with colors like we did here then check out this tool.

Good luck!