January 30, 2016 at 18:28The simplest cellular automata and their practical application
This world is just fucking so complicated, I am amazed every day.
In order to somehow get to know him and at the same time not get off the coils, we humans with our miserable brains have to look thoughtfully at what is happening, analyze what we have seen and build models - abstractions, with the help of which we can sometimes predict something with some accuracy and it’s even naive to believe that we understand what is really happening.
And you know what is amazing? This approach works great. Well, almost always. At least we haven’t come up with anything better.
But actually I'm not talking about that. I want to talk about one extremely interesting category, both aesthetically and mathematically, of the categories of these same models.
Yes, I’m talking about cellular automata, namely, about their subset, the simplest cellular automata (Elementary cellular automaton). In this article, I will tell you what it is, what they are, what properties they have, and I will answer the main, in my opinion, absolutely correct question, which is often unfairly ignored in such articles. It sounds like this: And why is this all?
Looking ahead, I will say that the simplest cellular automata are used in cryptography, modeling of physical processes, human behavior, in biology, and in a whole bunch of other important and interesting things. And in general: firstly, it is beautiful .
I sincerely hope that after reading the article you yourself will want to play with them, and in this case I have a generator assembled from JS and sticks.
There are only 256 simple cellular automata, and the behavior of some of them duplicates others. But, despite this, Stephen Wolfram , widely known in narrow circles, devoted years of his life to studying them, before him dozens of mathematicians were also engaged in this, and to this day, scientists write dissertations and scientific works on this topic.
First, let's define the terminology. Since there are only 256 variants of such machines, the same Wolfram (I will often refer to it) did not bother much and suggested calling them numbers from 0 to 255. This naming, due to its brevity and convenience, has taken root well, and since then it has been called You Won't Believe, " Tungsten Code ".
I understand you, I’m too lazy to follow the links, so I’ll briefly talk about how to understand these codes. And if you already know this perfectly well without me, you can not deploy a spoiler, but just read on.
Wolfram also proposed dividing cellular automata into four classes according to the type of behavior:
class 1: all cells quickly assume the same state, which becomes stable.
For example, Rule 40:
2 class: the state of all cells stabilizes quickly, or periodic fluctuations occur.
For example, Rules 3 and 33:
3 class: an automaton generates chaotic, non-periodic structures. Small changes in the initial state entail significant changes in the result.
For example, rule 22:
4 class: the machine generates complex, interacting structures that can survive for a long time, but it does not achieve stability.
For example, rule 193:
Sometimes elementary cellular automata are found in completely unexpected places.
For example, look what a cutie.
Just do not flatter yourself. He does not love you. This is a Textile cone , the most dangerous mollusk from the Cones family for humans. There is no antidote for its poison yet.
The drawing on its shell is nothing more than a pattern generated by Rule 30. At least that's what they think at the University of Nottingham.
This is how the development of “Rule 30” looks from one point.
The same Rule 30 has until recently been usedin Mathematica package for generating pseudo random numbers. This became possible due to its important property: the results generated by it are chaotic, that is, a slight change in the initial conditions has a significant impact on the generated results.
However, there are a huge number of initial conditions under which a rule generates repeating patterns. For example, if in the initial conditions every 14th cell is “alive”, the result is such a Scandinavian sweater.
One of the most interesting rules. Tungsten classifies it as class 4, but depending on the initial conditions, it can behave as a representative of class 1, 2, 3 or 4.
For comparison, evolution from one point:
There are periodic structures at the left boundary of the triangle, a stable homogeneous state in the right half , and chaotic structures interspersed with unstable periodic ones in the central and right parts of the triangle.
And here is the evolution from a random initial state, 50% full of living cells.
Here you can also see periodic (interestingly, with different periods) and chaotic.
I won’t pull for long, in 2000 Matthew Cook provedthat this cellular automaton is Turing-complete, that is, on its basis any computable function can be realized.
There are a number of cellular automata (rules 18, 22, 126, 161, 182, 218, etc.) that, developing from one point, generate fractal images. For example, the rule 22 pattern is a Pascal triangle modulo 2 (a kind of discrete analogue of “Sierpinski Napkins”). The connection between the Sierpinski napkin and the Pascal triangle was already adequately covered on Habré three years ago.
And all this happiness looks like this:
Rule 161 generates an inverted version of the same fractal.
By the way, I forgot to mention one important point regarding the implementation of automata.
Otherwise, instead of the fully anticipated completely filled rectangle (evolution of rule 161 with the initial state entirely consisting of living cells), something unexpected can be seen:
Rule 184 has several interesting features, due to which it is widely used in mathematical modeling:
With its help, traffic flows are rather effectively modeled .
Each individual car moves forward, while a wave of traffic moves backward.
(Wikipedia picture)
It is also applicable to modeling the deposition of aerosols to the surface and to modeling particle annihilation. And it seems to be even (I can’t assert, since I didn’t understand anything from the article ) on its basis, we can build a majority element .
Mathematics, whatever one may say, is the queen of sciences (although it is unlikely that it can be considered science itself), and work in it is no end. There are many unsolved physical problems , many of which have not been solved just because the mathematical apparatus for solving them has not yet been invented.
And it happens, and vice versa - there seems to be no one needs the mathematical apparatus, and here a problem arises for which it suddenly turns out to be suitable (as, for example, with rule 184 and traffic flows).
And, after all, it's beautiful.
Atlas of the simplest cellular automata from Stephen Wolfram ;
Tungsten Book New Kind of Science ;
The generator of the simplest cellular automata for the authorship of yournon- humble servant ( source );
Another great generator from a friend named Nico Disseldorp.
In order to somehow get to know him and at the same time not get off the coils, we humans with our miserable brains have to look thoughtfully at what is happening, analyze what we have seen and build models - abstractions, with the help of which we can sometimes predict something with some accuracy and it’s even naive to believe that we understand what is really happening.
And you know what is amazing? This approach works great. Well, almost always. At least we haven’t come up with anything better.
But actually I'm not talking about that. I want to talk about one extremely interesting category, both aesthetically and mathematically, of the categories of these same models.
Yes, I’m talking about cellular automata, namely, about their subset, the simplest cellular automata (Elementary cellular automaton). In this article, I will tell you what it is, what they are, what properties they have, and I will answer the main, in my opinion, absolutely correct question, which is often unfairly ignored in such articles. It sounds like this: And why is this all?
Looking ahead, I will say that the simplest cellular automata are used in cryptography, modeling of physical processes, human behavior, in biology, and in a whole bunch of other important and interesting things. And in general: firstly, it is beautiful .
I sincerely hope that after reading the article you yourself will want to play with them, and in this case I have a generator assembled from JS and sticks.
Dull theory
What is a cellular automaton?
A discrete model, which is a grid of arbitrary dimension, each cell of which at any time can take one of a finite set of states, and a rule is defined for the transition of cells from one state to another.
Examples: Conway's Life , Von Neumann Automation , Wireworld , Schelling Segregation Model .
Examples: Conway's Life , Von Neumann Automation , Wireworld , Schelling Segregation Model .
What are they like?
Depending on the dimension of the lattice:
one-, two-, three-dimensional, etc.
For example, Rule 110 and others highlighted in this article are one-dimensional, “Life” is two-dimensional.
Depending on the number of possible states:
binary, ternary, etc.
In different cellular automata, the cell neighborhood can be determined in different ways , that is, a lot of cells, on which the state will depend at the next moment in time. This may be, for example, a neighborhood of Von Neumann of various ranks or a neighborhood of Moore .
SCs are synchronous and asynchronous . In synchronous all cells of the system are updated at the same time, in asynchronous - each does it independently.
One of the most important classifications is by type of behavior . I will talk about this separately below.
one-, two-, three-dimensional, etc.
For example, Rule 110 and others highlighted in this article are one-dimensional, “Life” is two-dimensional.
Depending on the number of possible states:
binary, ternary, etc.
In different cellular automata, the cell neighborhood can be determined in different ways , that is, a lot of cells, on which the state will depend at the next moment in time. This may be, for example, a neighborhood of Von Neumann of various ranks or a neighborhood of Moore .
SCs are synchronous and asynchronous . In synchronous all cells of the system are updated at the same time, in asynchronous - each does it independently.
One of the most important classifications is by type of behavior . I will talk about this separately below.
And then what is the simplest cellular automaton?
A one-dimensional binary (with two possible states) cellular automaton, where the state of a cell at each moment of time depends only on its own state and the states of adjacent cells at the previous moment in time.
There are only 256 simple cellular automata, and the behavior of some of them duplicates others. But, despite this, Stephen Wolfram , widely known in narrow circles, devoted years of his life to studying them, before him dozens of mathematicians were also engaged in this, and to this day, scientists write dissertations and scientific works on this topic.
First, let's define the terminology. Since there are only 256 variants of such machines, the same Wolfram (I will often refer to it) did not bother much and suggested calling them numbers from 0 to 255. This naming, due to its brevity and convenience, has taken root well, and since then it has been called You Won't Believe, " Tungsten Code ".
I understand you, I’m too lazy to follow the links, so I’ll briefly talk about how to understand these codes. And if you already know this perfectly well without me, you can not deploy a spoiler, but just read on.
What do tungsten codes mean
Let's look at an example right away.
Take the rule number, for example, 110.
1. 110 10 = 01101110 2 .
2. Enter the numbers of the binary representation of the number in the table:
Depending on the states of the neighbor on the left, the cell itself and the neighbor on the right (first row of the table), at the next step, the cell will accept one of the states indicated in the second row.
This can be visualized even more like this:
Take the rule number, for example, 110.
1. 110 10 = 01101110 2 .
2. Enter the numbers of the binary representation of the number in the table:
| 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
Depending on the states of the neighbor on the left, the cell itself and the neighbor on the right (first row of the table), at the next step, the cell will accept one of the states indicated in the second row.
This can be visualized even more like this:
Wolfram also proposed dividing cellular automata into four classes according to the type of behavior:
class 1: all cells quickly assume the same state, which becomes stable.
For example, Rule 40:
2 class: the state of all cells stabilizes quickly, or periodic fluctuations occur.
For example, Rules 3 and 33:
3 class: an automaton generates chaotic, non-periodic structures. Small changes in the initial state entail significant changes in the result.
For example, rule 22:
4 class: the machine generates complex, interacting structures that can survive for a long time, but it does not achieve stability.
For example, rule 193:
PKA in life
Rule 30
Sometimes elementary cellular automata are found in completely unexpected places.
For example, look what a cutie.
Just do not flatter yourself. He does not love you. This is a Textile cone , the most dangerous mollusk from the Cones family for humans. There is no antidote for its poison yet.
The drawing on its shell is nothing more than a pattern generated by Rule 30. At least that's what they think at the University of Nottingham.
This is how the development of “Rule 30” looks from one point.
The same Rule 30 has until recently been usedin Mathematica package for generating pseudo random numbers. This became possible due to its important property: the results generated by it are chaotic, that is, a slight change in the initial conditions has a significant impact on the generated results.
However, there are a huge number of initial conditions under which a rule generates repeating patterns. For example, if in the initial conditions every 14th cell is “alive”, the result is such a Scandinavian sweater.
Rule 110
One of the most interesting rules. Tungsten classifies it as class 4, but depending on the initial conditions, it can behave as a representative of class 1, 2, 3 or 4.
For comparison, evolution from one point:
There are periodic structures at the left boundary of the triangle, a stable homogeneous state in the right half , and chaotic structures interspersed with unstable periodic ones in the central and right parts of the triangle.
And here is the evolution from a random initial state, 50% full of living cells.
Here you can also see periodic (interestingly, with different periods) and chaotic.
I won’t pull for long, in 2000 Matthew Cook provedthat this cellular automaton is Turing-complete, that is, on its basis any computable function can be realized.
Fractals
There are a number of cellular automata (rules 18, 22, 126, 161, 182, 218, etc.) that, developing from one point, generate fractal images. For example, the rule 22 pattern is a Pascal triangle modulo 2 (a kind of discrete analogue of “Sierpinski Napkins”). The connection between the Sierpinski napkin and the Pascal triangle was already adequately covered on Habré three years ago.
And all this happiness looks like this:
Rule 161 generates an inverted version of the same fractal.
By the way, I forgot to mention one important point regarding the implementation of automata.
In order to avoid the “edge effect”, that is, the effect of borders on the border cells, you need to close the automaton into a ring, i.e. make the leftmost cell the right neighbor of the far right, and vice versa.
Otherwise, instead of the fully anticipated completely filled rectangle (evolution of rule 161 with the initial state entirely consisting of living cells), something unexpected can be seen:
Rule 184
Rule 184 has several interesting features, due to which it is widely used in mathematical modeling:
- After each step, the number of “living” cells remains unchanged.
- A rule, depending on the initial state, can behave as a rule of class 2 or 4.
- The fewer “living” cells in the initial state, the faster the machine stabilizes
With its help, traffic flows are rather effectively modeled .
Each individual car moves forward, while a wave of traffic moves backward.
(Wikipedia picture) It is also applicable to modeling the deposition of aerosols to the surface and to modeling particle annihilation. And it seems to be even (I can’t assert, since I didn’t understand anything from the article ) on its basis, we can build a majority element .
Conclusion
Mathematics, whatever one may say, is the queen of sciences (although it is unlikely that it can be considered science itself), and work in it is no end. There are many unsolved physical problems , many of which have not been solved just because the mathematical apparatus for solving them has not yet been invented.
And it happens, and vice versa - there seems to be no one needs the mathematical apparatus, and here a problem arises for which it suddenly turns out to be suitable (as, for example, with rule 184 and traffic flows).
And, after all, it's beautiful.
Related links:
Atlas of the simplest cellular automata from Stephen Wolfram ;
Tungsten Book New Kind of Science ;
The generator of the simplest cellular automata for the authorship of your
Another great generator from a friend named Nico Disseldorp.