JACK IN DAVAO
Other Places, Other Perspectives
Wolfram-style One Dimensional Cellular Automaton In Java Applet

In its simplest form, a cellular automaton ('CA') consists of a grid of squares. Each square can be black or white. At intervals, the grid is recomputed and some of the squares change color, causing the geometric pattern made by the squares to change. At each iteration, when the grid is recomputed, the color of each square changes or stays the same depending on the color of the squares in some small 'neighborhood' surrounding it. A CA uses 'transition rules' to determine the color of a cell at the next iteration from the current colors of the neighboring cells.

The 'game of life' is an 'oldie but a goodie' in the world of cellular automata. It consists of a two-dimensional grid of squares. Each square is either white (dead) or black (alive). If a square is alive, it stays alive in the next iteration if exactly two or three of the eight squares surrounding it are alive, otherwise it dies. If a square is dead, it comes to life in the next iteration if and only if exactly two of the eight neighboring squares are alive, otherwise it remains dead. The 'life' CA was invented in the 1950's by Conway, who, according to legend, worked it out by placing dinner plates on the tiled floor of his kitchen, since a suitable computer was not available at the time. From a reasonable starting state (random works pretty well) the 'Life' grid evolves into shifting patterns of repeated shapes that move, rotate, shoot off other shapes, etc. To see 'Life' in action (on someone else's web site, I didn't write this one), click here.

One of the interesting things about CA's is that they appear to display 'emergent behavior' under some circumstances. This means that a large number of simple components, obeying simple rules based on entirely local information, seem to engage in coordinated behavior. It is also possible to construct CA's that can do computation -- the input is the initial pattern on the grid, the output is the grid pattern at some later time, and the 'computation' consists of the changes in the pattern due to applying the transition rules at each time step.

Stephen Wolfram -- Cal Tech PhD (in one year, at age 20), inventor of Mathematica (in my opinion, perhaps the best piece of software ever written) and recipient of a MacArthur Foundation 'genius' award -- is convinced that cellular automata offer a way of describing physical processes that may allow insights that conventional mathematics cannot provide. He spent nine years researching and writing a book on the subject, A New Kind Of Science. (Stephen Wolfram's web site, including full text of many of his journal papers, is here. The web site for Mathematica (student version is only $149, a real bargain) is here.)

Wolfram wrote a series of journal papers in the 80's about one-dimensional CA's. In its simplest form, a one-dimensional CA can be thought of as a single row of cells each of which can be either white or black. The state of each cell at time t + 1 depends on the state of the same cell and its neighbors at time t. For a neighborhood of radius 1, this means that the state (color) of each cell at time t + 1 depends on the state of the cell and it's two adjacent cells at time t. Since the state is therefore determined by three cells, each able to have a value of either 0 or 1 (white or black), there are eight possible combinations of values for the three cells. We can construct a transition rule for the cell's state at the next iteration by assigning a 0 or a 1 to each of the eight possible combinations. Therefore, there are 256 possible transition rules, since there are eight combinations and each can have a value of 0 or 1. It is convenient to write the transition rule as an eight bit binary number, with each bit corresponding to one of the eight possible combinations of 3-cell states, and to designate the rules by the value of the binary number. For example, Rule 90 would be:


111

110

101

100

011

010

001

000

0

1

0

1

1

0

1

0


(The binary number 01011010 -- the bottom row of the table -- has a value of 90 in decimal, hence, 'Rule 90'.) Under this rule, if a cell is currently white (0) and both of its immediate neighbors are black (1), the cell would remain white (0) in the next iteration (101 -> 0 under the rule).

To visualize the operation of a one-dimensional CA, it is useful to draw the row for each iteration below the row for the previous iteration, so that a pattern emerges as each new row is added. Of the 256 possible rules, some produce no interesting patterns, but some produce quite extraordinary fractal patterns, such as Sierpinski Sieves, when begun from a row with a single black cell.

The applet on this page displays any radius-1 one-dimensional CA; the rule number can be specified, or the applet can be set to cycle through all the rules in sequence. The initial state can be a single black cell, or random (check the 'Random IC' check box for random initial conditions). The 'skip static rules' checkbox causes the applet to skip most of the 'boring' rules where little or nothing changes from one iteration to the next. Source code for the Applet is here.






HOME
PATENT LAW PRACTICE
SITE CONTENTS
ABOUT
CONTACT



Copyright 2011-12 Jack S. Emery. License is freely given to reproduce site content provided authorship is acknowledged and URL or link to the source page are prominently displayed.