A little bit about cellular automata

On Habré already many - many - many times they wrote about the game "Life". Most recently there was an amazing article Life on the Lobachevsky plane . But the game "Life" is a special case of the so-called. cellular automata . There are many other cellular automata quite different from the game "Life", but nevertheless very interesting. I want to tell about some of them here.

To begin with, we consider a series of cells in which, except for one, there are zeros:

  ... 0 1 0 0 0 0 0 0 ... 

Consider the following rule; replace the number in the cell with the sum of this number and the neighbor on the left. We get the following series of states:
')

 ... 0 1 0 0 0 0 0 0 ...
 ... 0 1 1 0 0 0 0 0 ...
 ... 0 1 2 1 0 0 0 0 ...
 ... 0 1 3 3 1 0 0 0 ...
 ... 0 1 4 6 4 1 0 0 ...
 ... 0 1 5 10 10 5 1 0 ...
 ... 0 1 6 15 20 15 6 1 ...

It is not difficult to see that this is Pascal's triangle. And now instead of the usual addition we will use the addition modulo two. It is known (and even recently it was told in habrastatiya the Sierpinski Triangle and Pascal's triangle ) that we get the discrete analog of the Sierpinski triangle:

 ... 0 1 0 0 0 0 0 0 ...
 ... 0 1 1 0 0 0 0 0 ...
 ... 0 1 0 1 0 0 0 0 ...
 ... 0 1 1 1 1 0 0 0 ...
 ... 0 1 0 0 0 1 0 0 ...
 ... 0 1 1 0 0 1 1 0 ...
 ... 0 1 0 1 0 1 0 1 ...

Interesting? Read on!


It makes no sense to give a precise definition of a cellular automaton here, but it is useful to note the following properties of cellular automata: parallelism , locality , uniformity . Parallelism means that updates of all cells occur independently of each other. By locality it is meant that the new state of the cell depends only on the old state of the cell and its neighborhood. And finally, homogeneity means that all cells are updated according to the same rules.

In order not to get involved in infinite grids, we will consider cellular automata on a finite quadrangular grid, and to avoid problems with borders, we wrap the grid in a torus. The two neighborhoods of the cell have named names: this is Moore 's neighborhood — all eight surrounding cells are neighbors, and von Neumann 's neighborhood — only the nearest cells to the left, right, top, and bottom are neighbors. To avoid ambiguities, besides the verbal description of the cell state transformation rule, the implementation of the function will also be given.

int transformCell( int northWestCell, int northCell, int northEastCell, int westCell, int centerCell, int eastCell, int southWestCell, int southCell, int southEastCell); 

Limited and unlimited growth

So, let the cells be in two states, 0 is dead and 1 is live.
Consider the following rule: a cell becomes alive, if at least one of its neighbors is alive; a cell, once becoming alive, remains alive forever. In the case of Moore’s neighborhood, the body of the transformCell() function will be:

 int sum = northWestCell + northCell + northEastCell + westCell + eastCell + southWestCell + southCell + southEastCell; if (sum > 0) { return 1; } else { return centerCell; } 

If the field is initially filled with zeros, then living cells will not appear, but if one of the cells is made alive, then a growing square of living cells will arise from this “embryo”, which will eventually fill the field. At the same time, the area of ​​living cells increases as fast as possible - the speed of light.


Let's slightly change the rule above: instead of the condition “at least one of the neighbors is alive”, consider the condition “exactly one of the neighbors is alive”.

 int sum = northWestCell + northCell + northEastCell + westCell + eastCell + southWestCell + southCell + southEastCell; if (sum == 1) { return 1; } else { return centerCell; } 

The structure obtained from a single cell will be, firstly, much more rarefied, and, secondly, it will have a clear fractal character.


You can consider von Neumann's neighborhood instead of Moore’s neighborhood:

 int sum = northCell + westCell + eastCell + southCell; if (sum == 1) { return 1; } else { return centerCell; } 

Cyclic cellular automata

Cyclic cellular automata were invented by David Griffith. A cell can be in n states, which will be numbered 0, 1, ..., n - 1. We say that the state m is next to the state k if m + 1 = k (mod n ). A cell from state m enters the next state k , only if one of the neighboring cells has state k . For example, in the case of a von Neumann neighborhood, the transformation is written as follows:

 int nextState = (centerCell + 1) % statesNumber; if (northCell == nextState || westCell == nextState || eastCell == nextState || southCell == nextState) { return nextState; } else { return centerCell; } 

However, if you start with a randomly filled field, there can be three different stages. The first stage is a random field. Then colored areas begin to appear, which will absorb randomly filled areas. These blocks will “wave” change their color. Further spirals arise, also called demons . Finally, in the third stage, the field will be absorbed by the demons.





You can also consider a one-dimensional cyclic cellular automaton:

 int transformCell(int leftCell, int centerCell, int rightCell) { int nextState = (centerCell + 1) % statesNumber; if (nextState == leftCell || nextState == rightCell) { return nextState; } else { return centerCell; } } 

If you are interested to know more details, I recommend starting with Wikipedia Cyclic cellular automaton .

Hashman

Let the cell again be in the states 0, 1, ..., n - 1.
Consider the rule consisting of three parts.

Health . If a cell is in a state of 0 (that is, it is healthy), then it becomes ill if several of its neighbors are ill (that is, they are in a non-zero state).

Recovery . If the cell is in the state n - 1, then it self-cures and goes into state 0.

Disease . Otherwise, the state of the cell is calculated as the average of the states of neighboring cells, plus some constant. (If the resulting number is greater than n - 1, then the new state will be n - 1.)

 int sum = northWestCell + northCell + northEastCell + westCell + eastCell + southWestCell + southCell + southEastCell; if (centerCell == 0) { if (sum < 5) { return 0; } else if (sum < 100) { return 2; } else { return 3; } } else if (centerCell == statesNumber - 1) { return 0; } else { return Math.min(sum / 8 + 5, statesNumber - 1); } 

It is noted that the wave-like processes obtained in this way resemble the reaction of Belousov-Zhabotinsky .

Surface of venus

This rule (as well as the previous one) I found in the Cellab Manual . Each cell is in a state of 0, 1, 2, or 4. The rule is:

 if (centerCell == 0) { return 2 * ((northWestCell % 2) ^ (northEastCell % 2)) + northCell % 2; } else if (centerCell == 1) { return 2 * ((northWestCell % 2) ^ (southWestCell % 2)) + westCell % 2; } else if (centerCell == 2) { return 2 * ((southWestCell % 2) ^ (southEastCell % 2)) + southCell % 2; } else { return 2 * ((southEastCell % 2) ^ (northEastCell % 2)) + eastCell % 2; } 

If you start with a randomly filled field, then two "streams" crashing into each other are formed: vertical and horizontal. After some time, one of the "streams" begins to prevail. And in the end, there is only one.





This is a small part of cellular automata, about which I wanted to tell, but I have to stop so that the article does not become too large. For those interested in giving a few links:

(1) T. Toffoli, N. Margolus, Machines of cellular automata , M., Mir, 1991.

(2) M. Schroeder, Fractals, chaos, power laws. Miniatures from infinite paradise , Izhevsk, RHD, 2001, pp. 469--490.

(3) R. Rucker, J. Walker Cellab Manual .