The simplest cellular automata and their practical application
This world just ohrenet how difficult, every day amazed.
In order to somehow get to know him and not to leave the coils at the same time, we humans, with our pitiful brains, have to thoughtfully look 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 is even naive to believe that we understand what is actually happening.
And you know what's amazing? This approach works great. Well, almost always. At least, we still haven't come up with anything better.
')
But actually, I'm not talking about that. I want to tell about one extremely interesting both from an aesthetic and mathematical point of view categories of these same models.
Yes, I'm talking about cellular automata, namely about their subset, the simplest cellular automaton (Elementary cellular automaton). In this article I will tell you what it is, what they are, what properties they have, and also answer the main, in my opinion, and absolutely correct question, which is often unfairly ignored in such articles. It sounds like this: And this is all why?
Looking ahead, I will say that the simplest cellular automata are used in cryptography, modeling of physical processes, behavior of people, 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.
The simplest cellular automata are only 256, 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, and dozens of mathematicians were doing it before him, and to this day scientists write dissertations and scientific works on this topic.
To begin with we will be defined with terminology. Since there are only 256 variants of such automata, the same Wolfram (I will often refer to it) did not bother much and offered to call them numbers from 0 to 255. This naming convention, because of its brevity and convenience, has perfectly taken root, and since then it is called , you will not believe the " Wolfram Code ".
I understand you, I am too lazy to follow the links, so I will briefly tell you how to understand these codes. And if you know it perfectly well without me, you can not deploy the spoiler, but just read further.
Wolfram also proposed to divide cellular automata into four classes according to the type of behavior:
Grade 1: all cells quickly take on the same state, which becomes stable.
For example, Rule 40:
Grade 2: the state of all cells quickly stabilizes, or periodic oscillations occur.
For example, Rules 3 and 33:
Class 3: the automaton generates chaotic, non-periodic structures. Small changes in the initial state entail significant changes in the result.
For example, rule 22:
Grade 4: the automaton generates complex, interconnected structures that can survive for a long time, but does not achieve stability.
For example, rule 193:
Sometimes elementary cellular automata are found in completely unexpected places.
Here, for example, look, what a cutie.
Just make no mistake. He doesn't love you. This is the Textile cone , the most dangerous mollusk of the Cones family for humans. Antidote to his poison yet.
The pattern on his shell is nothing more than a pattern produced by “Rule 30”. At least that's what they think at the University of Nottingham.
This is how the development of “Rule 30” from one point looks like.
The same Rule 30 until recently was used in the Mathematica package to generate 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 gives rise to repeated patterns. For example, if every 14th cell is “alive” in the initial conditions, the result is a Scandinavian sweater.
One of the most interesting rules. Tungsten classifies him to class 4, but depending on the initial conditions, he may behave as a representative of classes 1, 2, 3, or 4.
For comparison, the evolution from one point:
There are periodic structures at the left border of the triangle, a stable homogeneous state in the right half, and chaotic structures interspersed with unstable periodic, in the central and right parts of the triangle.
And here is the evolution from a random initial state filled with living cells by 50%.
It also shows periodic (which is interesting, with different periods), and chaotic.
I won’t be too long; in 2000, Matthew Cook proved that 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.), which, evolving from one point, give rise to fractal images. For example, rule 22 is a Pascal triangle modulo 2 (a kind of discrete analogue of “Sierpinski Napkins”). The link between the napkins of Sierpinski and Pascal's triangle was already adequately covered in Habré three years ago.
And all this happiness looks like this:
Rule 161 gives rise to an inverted version of the same fractal.
By the way, I forgot to mention one important point concerning the implementation of automata.
Otherwise, instead of the completely expected completely filled rectangle (the evolution of rule 161 with the initial state completely consisting of living cells) you can see something unexpected:
Rule 184 has several interesting features due to which it is widely used in mathematical modeling:
With its help, traffic flows are quite effectively modeled.
Each separately taken car moves forward while the traffic wave moves back.
(picture from Wikipedia)
It is also applicable to modeling the deposition of aerosols on the surface and to modeling the annihilation of particles. And it seems to be even (I can’t argue, since I didn’t really understand anything from the article ) on its basis it is possible to build a majority element .
Mathematics, whatever one may say, the queen of sciences (although it can hardly be considered a science), and work in it is not a great end. There are many unsolved physical problems , many of which are not solved simply because the mathematical apparatus has not yet been invented to solve them.
But sometimes it happens the other way around - there seems to be no use to any mathematical apparatus, and then a problem arises for which it suddenly turns out to be suitable (as, for example, with rule 184 and traffic flows).
And, at the end of the day, beautiful.
Atlas of the simplest cellular automata from Stephen Wolfram ;
The Book of Wolfram New Kind of Science ;
The generator of the simplest cellular automata authored by yournon- humble servant ( source code );
Another great generator from a friend called Nico Disseldorp.
In order to somehow get to know him and not to leave the coils at the same time, we humans, with our pitiful brains, have to thoughtfully look 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 is even naive to believe that we understand what is actually happening.
And you know what's amazing? This approach works great. Well, almost always. At least, we still haven't come up with anything better.
')
But actually, I'm not talking about that. I want to tell about one extremely interesting both from an aesthetic and mathematical point of view categories of these same models.
Yes, I'm talking about cellular automata, namely about their subset, the simplest cellular automaton (Elementary cellular automaton). In this article I will tell you what it is, what they are, what properties they have, and also answer the main, in my opinion, and absolutely correct question, which is often unfairly ignored in such articles. It sounds like this: And this is all why?
Looking ahead, I will say that the simplest cellular automata are used in cryptography, modeling of physical processes, behavior of people, 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?
The discrete model is a grid of arbitrary dimension, each cell of which at each moment of time can take one of a finite set of states, and the rule of transition of cells from one state to another is determined.
Examples: Conway's “Life” , Von Neumann's Automaton , Wireworld , Schelling Segregation Model .
Examples: Conway's “Life” , Von Neumann's Automaton , 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 covered 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 neighborhood of the cell can be differently determined, that is, the set of cells on which the state will depend on at the next moment in time. This could be, for example, the Von Neumann neighborhood of various ranks or the Moore neighborhood .
KA are synchronous and asynchronous . In synchronous, all cells of the system are updated simultaneously, in asynchronous, each one does it independently.
One of the most important classifications is by type of behavior . I will tell about this separately below.
one-, two-, three-dimensional, etc.
For example, Rule 110 and others covered 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 neighborhood of the cell can be differently determined, that is, the set of cells on which the state will depend on at the next moment in time. This could be, for example, the Von Neumann neighborhood of various ranks or the Moore neighborhood .
KA are synchronous and asynchronous . In synchronous, all cells of the system are updated simultaneously, in asynchronous, each one does it independently.
One of the most important classifications is by type of behavior . I will tell 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 the cell at each moment of time depends only on its own state and the states of the cells adjacent to it at the previous moment of time.
The simplest cellular automata are only 256, 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, and dozens of mathematicians were doing it before him, and to this day scientists write dissertations and scientific works on this topic.
To begin with we will be defined with terminology. Since there are only 256 variants of such automata, the same Wolfram (I will often refer to it) did not bother much and offered to call them numbers from 0 to 255. This naming convention, because of its brevity and convenience, has perfectly taken root, and since then it is called , you will not believe the " Wolfram Code ".
I understand you, I am too lazy to follow the links, so I will briefly tell you how to understand these codes. And if you know it perfectly well without me, you can not deploy the spoiler, but just read further.
What do the Wolfram codes mean?
Consider immediately an example.
Take the rule number, for example, 110.
1. 110 10 = 01101110 2 .
2. Enter the digits 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 (the first row of the table) in the next step, the cell will assume one of the states indicated in the second row.
Even more clearly, this can be represented as follows:
Take the rule number, for example, 110.
1. 110 10 = 01101110 2 .
2. Enter the digits of the binary representation of the number in the table:
| 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
| 0 | one | one | 0 | one | one | one | 0 |
Depending on the states of the neighbor on the left, the cell itself and the neighbor on the right (the first row of the table) in the next step, the cell will assume one of the states indicated in the second row.
Even more clearly, this can be represented as follows:
Wolfram also proposed to divide cellular automata into four classes according to the type of behavior:
Grade 1: all cells quickly take on the same state, which becomes stable.
For example, Rule 40:
Grade 2: the state of all cells quickly stabilizes, or periodic oscillations occur.
For example, Rules 3 and 33:
Class 3: the automaton generates chaotic, non-periodic structures. Small changes in the initial state entail significant changes in the result.
For example, rule 22:
Grade 4: the automaton generates complex, interconnected structures that can survive for a long time, but does not achieve stability.
For example, rule 193:
PKA in life
Rule 30
Sometimes elementary cellular automata are found in completely unexpected places.
Here, for example, look, what a cutie.
Just make no mistake. He doesn't love you. This is the Textile cone , the most dangerous mollusk of the Cones family for humans. Antidote to his poison yet.
The pattern on his shell is nothing more than a pattern produced by “Rule 30”. At least that's what they think at the University of Nottingham.
This is how the development of “Rule 30” from one point looks like.
The same Rule 30 until recently was used in the Mathematica package to generate 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 gives rise to repeated patterns. For example, if every 14th cell is “alive” in the initial conditions, the result is a Scandinavian sweater.
Rule 110
One of the most interesting rules. Tungsten classifies him to class 4, but depending on the initial conditions, he may behave as a representative of classes 1, 2, 3, or 4.
For comparison, the evolution from one point:
There are periodic structures at the left border of the triangle, a stable homogeneous state in the right half, and chaotic structures interspersed with unstable periodic, in the central and right parts of the triangle.
And here is the evolution from a random initial state filled with living cells by 50%.
It also shows periodic (which is interesting, with different periods), and chaotic.
I won’t be too long; in 2000, Matthew Cook proved that 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.), which, evolving from one point, give rise to fractal images. For example, rule 22 is a Pascal triangle modulo 2 (a kind of discrete analogue of “Sierpinski Napkins”). The link between the napkins of Sierpinski and Pascal's triangle was already adequately covered in Habré three years ago.
And all this happiness looks like this:
Rule 161 gives rise to an inverted version of the same fractal.
By the way, I forgot to mention one important point concerning the implementation of automata.
In order to avoid the "edge effect", that is, the influence of the borders on the border cells, it is necessary to close the machine into a ring, i.e. make the leftmost cell the rightmost neighbor of the rightmost one, and vice versa.
Otherwise, instead of the completely expected completely filled rectangle (the evolution of rule 161 with the initial state completely consisting of living cells) you can see something unexpected:
Rule 184
Rule 184 has several interesting features due to which it is widely used in mathematical modeling:
- After each step, the number of "live" cells remains unchanged.
- The rule depending on the initial state can behave as a rule of class 2 or 4.
- The less “live” cells in the initial state, the faster the automaton stabilizes
With its help, traffic flows are quite effectively modeled.
Each separately taken car moves forward while the traffic wave moves back.
(picture from Wikipedia)It is also applicable to modeling the deposition of aerosols on the surface and to modeling the annihilation of particles. And it seems to be even (I can’t argue, since I didn’t really understand anything from the article ) on its basis it is possible to build a majority element .
Conclusion
Mathematics, whatever one may say, the queen of sciences (although it can hardly be considered a science), and work in it is not a great end. There are many unsolved physical problems , many of which are not solved simply because the mathematical apparatus has not yet been invented to solve them.
But sometimes it happens the other way around - there seems to be no use to any mathematical apparatus, and then a problem arises for which it suddenly turns out to be suitable (as, for example, with rule 184 and traffic flows).
And, at the end of the day, beautiful.
Related Links:
Atlas of the simplest cellular automata from Stephen Wolfram ;
The Book of Wolfram New Kind of Science ;
The generator of the simplest cellular automata authored by your
Another great generator from a friend called Nico Disseldorp.
Source: https://habr.com/ru/post/273393/
All Articles