Cellular Automata, continued November 5, 2008Posted by eric22222 in General, Math.
(You may want to refresh yourself on the basics of cellular automata before reading this post by reading my previous one)
So, now that we’ve got the idea of a binary cellular automaton down, that is, one with only two states for each cell, let’s up the ante a bit. Now consider a cellular automaton with five states. Instead of being “on” or “off,” they will have a value from zero to four. Our previous example was very similar, with the values ranging from zero to one, in a sense.
You may recall from our simpler CA, if the sum of a cell and its two neighbors was zero or three, we would set the new value to zero. Otherwise, it became one. We express that ruleset in the following form:
[0 1 1 0]
The outputs are ordered from left to right based on the input sum. Get it? In order, left to right, that’s “a sum of 0 yields 0,” “a sum of 1 yields 1,” “a sum of 2 yields 1,” and “a sum of 3 yields 0.” It’s a simple rule table of sorts, with the inputs not expressly written out, but simply counted up.
For our new CA, we have five states, zero to four. If a cell and its neighbors were all fours, the sum would be 12. So, our new ruletable will have thirteen rules, rather than four, as earlier.
One last thing to point out before we get rolling: our rules will be quiescent; that is, is a cell and its neighbors add to zero, the result will always be zero.
Ok, that was just obligatory definition of style for later. For now, let’s get to some more subjective matters about cellular automata.
(For the following images, instead of using “#” and “_” for 1 and 0, we’re using colors. Just a heads up.)
Given a random initial starting condition and a random rule string, let’s see what we get:
Well, that’s kind of boring. This is class I behavior. The whole string settles into the same state. Generally this is state 0; that is, everything adds to zero, and those zeroes add up to zero again.
Hmm, still not much to look at. This is class II behavior. Instead of settling to one state, it settles into some sort of oscillation. Now, you have to consider that this is a finite-state system. That is, there are only a set number of possible patterns. Technically, every pattern will eventually oscillate, but this refers to more manageable periods of repetition. Above, we have a period of 2. (Also consider that class I is a sort of oscillation with a period of 1)
Well, there’s more visual interest, but this is basically a colorful variety of white noise. This is class III, but no, there’s really not much information here in this CA.
Now this is what makes this complex kind of cellular automaton interesting. This is called class IV behavior, and exhibits forms of computation. Now, the one seen above settles into class II, but the transient period beforehand is a prime example of class IV. Here we see patterns that continue through several iterations, interacting with others producing new results by either annihilating each other or forming one oscillating string.Persistent storage, terminating cyclic activity, and a global transfer of activity. Okay, I just copied those from my notes, but it’s still valid, yeah?
Now, of course you’re dying to try this out for yourself now, right? Of course you are; no one can resist the allure of uncovering the elegant secrets hidden beneath simple mathematical rules, just waiting to be explored.
You can check out the online applet I used above right here.
Using it is pretty simple:
- Hit “random rule” to generate the rule table automatically. Alternatively, you can hit enter rule to input whatever ruleset you’d like.
- Hit “setup random.” This creates the random initial conditions.
- Hit “go.” Simple as that.
And here are a few experiments to try:
Sierpinski’s Triangle: Change the “states” slider to 2. Instead of “setup random,” use “setup single.” This is the pattern I showed last time.
Class IV: Leave “states” at 5. Instead of “random rule,” enter the following ruleset as shown:
[0 4 1 3 1 1 2 4 2 4 3 1 2]
Well, I suppose that I’ve finally gone beyond scratching the surface of cellular automata. Believe it or not, there’s even more I could cover, and just might do sometime.Further reading:
- Langton, Christopher G. “Computation at the Edge of Chaos: Phase Transitions and Emergent Computation,” in Emergent Computation, ed. Stephanie Forrest. North-Holland, 1990.
- Langton, Christopher G. “Life at the Edge of Chaos,” in Artificial Life II, ed. Langton et al. Addison-Wesley, 1992.
Emmeche, Claus. The Garden in the Machine: The Emerging Science of Artificial Life. Princeton, 1994
- Wolfram, Stephen. A New Kind of Science. Wolfram Media, 2002.