Interesting examples of cellular automata.

On Habré many articles on cellular automata ( http://habrahabr.ru/post/168291/ , http://habrahabr.ru/post/227003/ ), especially on the game "Life" ( http://habrahabr.ru/ post / 67790 / , http://habrahabr.ru/post/154509/ , http://habrahabr.ru/post/237629/ ). I want to tell something new - about other cellular automata, to give unexpected and interesting, in my opinion, examples. We look at the structure, which gradually copies its original configuration ; and on the structure that draws a circle .

Caution, big gifs
')

This also applies to definitions, but it will definitely come in handy:
- the state of the structure.
- cell, then - her condition. Something like: "according to the coordinates of the cell - its state".
- new cell state
- new state of the structure, where each cell has its own new state. (Applied to all cells)

Note that the new state of the structure does not depend on the “order of application” as it may seem at first glance: in fact, we do not change the state, we make a new field and fill it with new states.

Configuration - the state of the structure with a finite number of non-zero cells.

Copy structure

We have some directions - surroundings. We want to - XOR'ila all values ​​from the neighborhood (including the value of the cell, the result of which is calculated). Why did we take that way? It's just clear to us that if we have only one single cell on the field, then in one move it will “copy out” into the entire neighborhood (inverted).

Obviously, the operation is linear (in the sense of XOR), that is, we can subtract the new configurations for each cell separately, and then element-wisely proximize the result, and not honestly read the new configuration. In other words (hereinafter under understood XOR): if then . Well, accordingly .
Denote - configuration with one unit in a cell element.


Well, consider them separately. It is easy to see that the following configuration will have in cells (including, 1 will remain in place), that is:


Let's see how the configuration will bring itself further (and then it will behave cool!):


It turns out that all members at they are reduced, for they include an even number of times in the sum (and we use the characteristic field two).

Well, the proof base is ready to copy, try to make the transition. All the same, only instead of two - .
If application time looks like:


that


What I wanted to get.
Now we have
Cool, cool, our structure is really copied along the vectors that define the neighborhood.

Let's dig the sun:


On the example of a square, how it extends further:

Circle

A remarkable example of the incredible: with a discrete structure, with a finite memory of each cell (which means it cannot even remember its coordinates!), We will interpolate a continuous object — a circle — as much as you like.

I will not formally describe this system, since it will not become clearer from its formal description: there are a dozen states in the cell and the same number of elements in the surroundings.

Let's start. Almost obvious what a running signal is.




And it is clear that he can "push apart" the cells holding him.




This is almost all we need: let's launch a horizontal signal that will push the carrier cells, and with each pushing we will create two vertical latches and a vertical signal. It is clear that the signals can be arranged so that the horizontal does not conflict with the vertical ones: if they are superimposed, you need to make a new state that will “remember” in which directions the signals should be launched in the next step.

Why do fixing points tend to circle?
Denote:
, - the distance "to the beginning" from the points fixing the horizontal signal;
, - distance from the horizontal axis to the points fixing the vertical signal in the column with the index ;

Then start time vertical signal: (for each of the amount we need to move away from the center right, return, left, return), which is asymptotically . Likewise, the time from the launch of a vertical signal to its height : . Define circle radius like that is, we have . As we already understood, the time of formation of a point on distance column : . This point lies on the circle of radius (Pythagorean theorem), that is but so we got that . And this means that all such (vertical fixing) points will be located approximately at the same distance from the center as the horizontal fixing points. Therefore, they will form a shape close to the circle.

Beautiful picture, clarifying the situation:



Thanks to Arsen for the prototype sun!