Mike O'Kane

A cellular automaton is a simple model that manifests a very simple rule-based universe of 1, 2 or n dimensions, that progresses according to a clock. Each location in the universe is termed a cell and each cell has a certain state. At each tick of the clock, each of the cells that make up the universe progresses to its next state, which is a result of the application of the rules of the universe to it’s current state.  That might sound quite complicated but it can be very simple, since usually there are very few rules and very few states for each cell. In fact simple is of special interest since mathematicians, physicists and biologists have all been intrigued by the interesting behavior that can emerge under the simplest of conditions.   What makes CA fun for the rest of us is that they are easy to program, and provide a wonderful experience of an evolutionary, bottom-world: you set the rules and the initial conditions (initial states of each cell), then run the program and observe the results as the universe evolves.

In the case of a one-dimensional CA the universe consists of a line of cells, and that’s it. Let’s say the universe contains 20 cells. Now let’s give each cell only two possible states, 0 or 1. So you have 20 cells and each one might be a 0 or a 1.  For example, here are three possible states of this universe at any given moment (tick of the clock):

00010010011101001111
00000000011111011101
01010101010101010101

Each cell in the universe has a left and right neighbor, except the first and last cell. Since that seems intuitively wrong and implies that the universe has an edge with different characteristics than other locations) we will define this universe as unbounded, so the first cell is actually the  neighbor of the last cell (visualize the universe as a circular string). So we have  a universe of only 20 cells where each cell has a left and right neighbor and each cell can be in a state of 0 or 1. That looks like a very simple universe! But consider how many states this universe can have as a whole. The answer is 2^20, or 1,048,576. In other words this little universe can exist in any of 1,048,576 different states. Now consider a similar universe of just 200 such cells, which can exist in any of 1.606938e+60 different states! So even a very small and simple universe can have many different states.

However the number of states that most universes can inhabit is restricted by the rules of the universe and the initial state (initial conditions). The rules will determine the next state, based on the current state. These rules are applied at the cellular level so the state of an individual cell will be based on rules that determine this state based on its current state and the current state of its two neighbors. This is founded on the notion that all actions are local. even though the effects may be passed on in subsequent ticks of the clock. For an example of this working in our own world, in a row of people, if one person leans on another on the next, eventually a person at the end will fall over, but this is a result of local effects, that then pass along the line over time, as each person leans on the  next. In the case of our one-dimensional universe of 2-state cells, the rules can be very simple and simply specify what happens to a cell based on its current state and the current state of its two neighbors. So for example the rules of universe might be:

If a cell is currently in state 0, then  it will stay in state 0 if both of the neighboring cells are also currently in state 0 otherwise the cell will switch to state 1.

If a cell is currently in state 1, then it will stay in state 1 if either of the neighboring cells are currently in state state 1. otherwise it will switch to state 0.

We can see this in state chart where the left neighbor of the cell is listed first, the cell is listed next, the right neighbor is listed next, then after the dash, the new state of the cell is listed:

000 – 0
100 -1
001 -1
101 -1
010 -0
011 -1
110 -1
111 -1

You might consider this as an energy sharing model since basically it means that anytime a cell has at least one neighbor in state 1 it will be “energized” and go to state 1 itself, whereas anytime a cell has two neighbors that are both in state 0, it will be “energy depleted” and go to state 0. .

So let’s look at how the universe will change based these rules given the following current state:

00010010011101001111

Let’s apply the rules of this universe. The first cell is in state 0. Its left neighbor is the last cell which is in state 1, and its right neighbor is the 2nd cell which is in state 0. So under the rules, this means the rule for 100 will apply so the next state of the first cell will be 1. The 2nd cell is in state 0 and it;s left and right neighbors are also in state 0, so rule for 000 will apply and the next state of the 2nd cell will be 0. The third cell is in state 0 and its left and right neighbors are in states 0 and 1 respectively, so the rule for 001 will apply and the next state will be state 1. Note that we are applying the rules for every cell based on the current state of the universe (the current moment or tick of the clock), and the new state of each cell will not come into effect until the next tick of the clock, after the rules have been applied to all the cells in their current state.

So here again is  the current state, this time followed by the next state of this universe at the next moment, after the rules have been applied to all cells based on their current state and the current state of their neighbors:

00010010011101001111
10101101111110111111

You might consider this as energy sharing. And if a cell is currently in state 1, then if the neighboring cells are both in state 0 then the cell will go to state 0, otherwise, if either neighbor is state 1. it will state in state 1.

So far so good ,but what happens if we “run” this universe for awhile to see how it evolves based on these rules. To make it easier to observe the evolution of the universe as a pattern, we will substitute green (if the cell state is 1) and black (if the cell state is 0) pixels for each cell, and we will construct a universe of 400 cells (since pixels are small and we want to see the patterns more easily). My program above allows you to choose between initially assigning the cells random values of either 0 or 1 (of equal probability), or making all the cells 0 except 1 which has the value 1. You can also choose the number of iterations it will run, and you can change the rules at any point, restart whenever you want, and play and pause. Many rules generate relatively uninteresting universes, but many others are intriguing. For example rule 195 (the default) shows quite complex behavior, and rule 30 famously appears to generate random consecutive sequences. In the image, each row of green (state 1) and black (state 0) pixels indicates the state of the universe at the next state tick of the clock, following the application of the rules to the previous row.