Science and Math
Rule 30 - Cellular Automaton
The Rule of Rule 30
Below is the rule that defines RULE 30. It will make sense shortly...
Rule 30 Logic Table

Imagine an empty grid...
Empty Grid

With one of the squares colored in at the top...
One square filled in

Using the rule at the top of this page, can you figure out what the first line of the grid turns into? You may notice that the red square is surrounded by two whites, corresponding to one of the blocks from the rule diagram. The part of interest is illustrated below.
Pattern match in rule 30

If you look at the top of this page at the Rule 30 rule, you will find a block that matches this particular pattern. The block below is what you should find.

Notice that the top three squares on the, somewhat triangular, block match the original pattern. The bottom square tells us to place that color below on the original pattern on the main grid. Since this is probably confusing, here is what we should have...
Step 1 on row 2
The question marks indicate that the value (whether its colored or not) of the square has yet to be determined. We can use the same procedure as before to calculate the color of these squares.

First, we will focus on the left side question mark. Centered directly above the left question mark there is a "three group" of squares.
Pattern match in rule 30

Now, as before, look at the rule of Rule 30 and find the corresponding block. The following is the correct block.

Since the bottom square is colored in, we will color in the square centered directly below on the main grid. In other words, replacing the left question mark with a filled in square.

Now, one more time, let's try to do the right question mark. We find the three group above it...

This corresponds to...

So since the bottom square is filled in, we replace the right question mark with a filled in square.

That's all there is to it.

The finished second line looks like this...
First two rows completed

You may be wondering why we didn't calculate the two remaining squares on row 2, the one on the far left and the one on the far right. On a larger grid, these squares would evaluate as empty since, in Rule 30, three empties in a row creates an empty directly centered below it. On this grid, the edge is cut off, so we don't really know what's out there. Assuming that its empty is one popular choice. Or you use a wrap around technique, in essense connecting the far left with the far right. This would be similar to a 2 dimensional map of a 3 dimensional planet. The best method is to use an infinite grid and allow the pattern to grow continuously. Of course this isn't possible, but it can be approximated using a sufficiently large grid.

Up to this point, you havn't seen anything particularly fasinating about the use of the Rule 30 cellular automaton, but watch what happens when the same rule that was described before is reapplied line after line on a larger grid.

First 10 lines of the Rule 30 cellular automaton 
This is the first 10 lines of the Rule 30 cellular automaton, starting from an initital single filled square. The reapplication of rule continuously creates new lines. The amazing thing about this is that the lines never repeat. From a simple rule emerges apparently infinite complexity. In fact, if you wanted to calculate what the center square's color would be on the ten millionth line, you would have to actually calculate each line up to the ten millionth line.

First 100 lines of Rule 30
The first 100 lines of Rule 30

Do you want to see more?

Click here to see the first 500 lines

Customized Integrated Circuits

Can't find the chip you need? We can build one for you! Click on the "Custom Design" button on the left menu.
Get started NOW and receive your free quote by tomorrow!