Rule 110

Rule 110 is a type of 1d cellular automation. It can be generalized into any numbered rule you like, and some numbers can lead to very complex patterns.

The rule number specifies how to fill in each row of a grid. The first row has to be set by a user (or, in our case, filled in at random), and for the next row, each cell gets set according to the value of the cell above it and the two cells diagonally to the left and right. So every bit takes as input the 3 bits above it.

The rule number is actually a binary code which tells you which patterns of 3 bits turn into a 1, and which turn into a 0.

The cool thing about it is that each cell only knows the 3 cells above it, so the complex patterns that get generated are not the result of a program looking at the entire grid and filling in cool patterns, its an extremly simple program, where cells only have information about their immediate neighbors. This is reminiscent of how cells grow into complex patterns, despite not being concious themselves, or how ant and termite colonies create incredible structures, despite each insect only being able to follow a few basic rules. It’s proof that complex, interesting behaviors can result from very simple rules, with no top-down control or design.

The reason rule 110 in particular is special is it is capable of universal computation. Assuming you are allowed to pre-set the grid in a very specific pattern, you can set it up to run “programs” that can, technically, emulate any computer code (though for anything but the most basic of programs, this would be very inefficient and slow). That’s the magic of turning complete systems, they can run any other turning complete system inside them. You could program a bit pattern in rule 110 to simulate minecraft, and inside that minecraft world create a computer that runs an excel spreadsheet, and inside that spreadsheet simulate a website that runs rule 110!

To try this out yourself with any arbitrary rule number, enter in any number (the max possible value is 256, anything larger and it will just use the remainder after dividing by 256), then hit go. It will randomly fill in the first row, then fill in the rest according to the rule you set.

In particular, 30, 183 and 110 both look interesting.

getting meta

But what if we get a little meta with this? Each rule requires 8 bits of information, but we have more than 8 bits here! Each row is 100 bits long! So what if a cells rule was dependant on the actual values of the cells around it? Surely being more meta means more interesting.

And what if instead of simply using the 4 bits above and to the left, and the 4 above and to the right, we instead used a multiplier?

For example, a multiplier of 3 would mean the rule is defined by the bit up 1 and left 12, up 1 and left 8 … up 1 and right 12.

Technically, this is the same as a non-meta cellular automation script with longer rules, and some might say this is missing the point of the original rule 110 (that simple rules can lead to complex outcomes).

But what if we ignore the point and a it even more complicated?

In this next version, there are 3 layers.

layer 1: the same as normal cellular automation, except it uses rules defined by layer 2

layer 2: defines the rules for layer 1, and it’s rules are defined by layer 3

layer 3: defines the rules for layer 2, it’s rules are defined by the user, the same way the first grid worked

Since there are 3 layers, I figure may as well add 3 colors, layer 1 is red, layer 2 is green, and layer 3 is blue.

There is no self-reflection here, each layer can only impact the layer beneath it. So far the most interesting pattern I have found for this one is 22. It seems to create triangle shaped blotches of black in a sea of random colors.