WWW.
MakeYourOwnChip
.COM

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...
Imagine an empty grid...
With one of the squares colored in at the top...
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.
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...
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.
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...
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.
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.
The first 100 lines of
Rule 30
Do you want to see more?
Click here
to see the first
500 lines

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!

