My last two blogs were about the Conway's Game of Life [1][2]. Actually this game belongs to a broader set of models, that are called Cellular Automata. All of them follow the same idea of applying simple rules according to the current state of the cell and its neighbours.  A simple modification as changing any of the 4 rules of the game of live or taking into account second order (Figure 1) neighbours will produce very distinct patterns in the game.

Figure 1.
Figure 1. Second order neighbours of a cell in the Game of Life. There are 24 neighbours instead of 8.


However, the Game of Life is a quite sophisticated cellular automaton compared with the simplest version of them. The Game of Life is actually a 2-dimensional and, yes, there are 3-dimensional version of it. But I am looking for more simplicity and there are 1-dimensional automata (Figure 2). Again, we have "live" and "death" individuals and a few rules to decide the next state.

Figure 2. An 1-dimensional cellular automaton. The blacks cell represent alive individuals. The whites represents dead individuals.

The way we are going to define rules in this scenario is slightly different. We are just going to use two neighbours and the current state of the cell itself to stablish the state in the next iteration. We can represent this with 3 values indicating the actual state of the neighbours and the current cell: left neighbour - current cell - right neighbour. We are going to use symbol 0 for death and symbol 1 for alive. For example, 111 means that both neighbours and the current cell are alive. When 111 happens, we have to decide whether the next state would be 0 or 1 (Figure 3.).

Figure 3. Example of a rule (Rule 30). The 1 represent "alive", the 0 "dead". For instance, "101" means that the current cell is dead but the left and the right cells are alive and, then, the state in the next iteration would also be dead.

There exactly 8 possible combinations of 0s and 1s with three values. If we define 111,110,101,100,011,010,001,000 as a universal order for this kind of cellular automaton, then we just have to define 8 values that indicate the next state of the center cell. For example, in the Figure 3. the values would be 00011110. Yes, that is a binary number that could be represented in decimal system as 30. So the rule of Figure 3. is Rule 00011110 or Rule 30. Just remember we accept the universal order of 111,110,101,100,011,010,001,000.

Take a few seconds to re read the previous two paragraph. It may seem very complicated but it isn't. You just have to remember that the state of each cell in the next iteration is going to be the result of the two nearest neighbours and the cell itself. Just to be sure, Figure 4. gives and example. First row is the current iteration and second row the next iteration. Use the Figure 3. to check everything is fine. You can practice calculating the next "next generation". When you are on the leftest cell you can use as the left neighbour the rightest cell (like a ring).

Figure 4. Calculating the next generation for Figure 3. with the Rule 30.

Ok, so what? Let's say you continue doing this with a bigger 1-dimensional array (instead of just 10 cells per iteration, use 1000 or more). At the end you are going to have something like the Figure 5. You may see a pattern but actually there is no way of complete generalization, welcome to chaos! It is true, there are parts that have order and even cycles (I like to think the live on Earth as one of that ordered universal instants) but in general is unpredictable. Actually Wolfram proposed a computer random generator (more properly say  pseudorandom number generator) with it.

Figure 5. Rule 30 applied to many iteration in a big array.

Going back to Figure 3., all we need is 8 1s and 0s  to define a rule. There are exactly 256 different rules (actually just 128 because the other 128 are a negative mirror of the first 128, black would be white and white black). Not all of them produces this kind of crazy patterns (another good example is Rule 90 in Figure 6.).

Figure 6. Example of Rule 90 with initial setting.

Some of them produce no patterns at all. Think about Rule 0 (Rule 00000000), everything is going to die in one iteration. Others produces some kind of cycles or more order structures like Rule 184 (Figure 7.) used to model traffic flow in a single line of a road.

Figure 7. Example of rule 184.

Well, you may say. This very artificial, simplistic and unrealistic. Take a look the Figure 8 and compare it to Rule 30 in Figure 5.

Figure 8.  A shell similar in appearance to Rule 30

You may said it is a coincidence and it just looks like. Maybe, but the probabilities of Rule 30 appear in nature is very high so the coincidence is the rule appearing and not the whole pattern out of the blue. Just think how the growth of a shell is done.  The conclusions are the same of my previous post:

  1. Initial setting is very important
  2. Complexity can emerge from simplicity
  3. Chaos is not randomness
Thanks Wikipedia to for the pictures.

[2] Yet another “yet another blog about the “Conway’s Game of Life”