Cell Steppers
This article suggests rules for a two-dimensional cellular automaton, which, on the one hand, is very similar to the game Conway's Game of Life (John Conway's Game ), and on the other hand, it has significant differences. First of all, it is distinguished by an increase in the number of cell states to three, an increased ability to self-organize, an unlimited time of active evolution, and an unlimited number of moving configurations.
For stable configurations, the new rules coincide with the rules of the game Life, therefore all stable configurations in the game Life exist in the new rules. In the described cellular automaton there is a large class of moving configurations, spacecraft. All these configurations move along the same translational mechanism, which resembles the movement of a stepper excavator and a person on crutches. I called such space ships a stepper ( stepper ), and the rule itself Steppers. So we will call it in the future.
There are quite a few oscillators in Steppers, and some oscillators from the Life game also work in Steppers, which speaks of the continuity of the rules. And finally, the famous Conway glider also exists in the proposed rules. The article will consider the dynamics of randomly filled arrays, reveal the mechanism for the movement of steppers, describe the oscillators and steppers found so far. There will also be examples of collisions and complex functional behavior.
')
[00] An example of a moving configuration that generates a stream of steppers.
In 1988, I worked in a technical vision laboratory. Studying the skeletonization algorithm of a raster monochrome image, I wrote a program for its implementation. The skeletonization algorithm itself was not useful to us and was abandoned, and the written program, after a little refinement, turned out to be quite a decent cellular automaton with a graphic editor and a graphical output. The first test for her, of course, was the game The Life of John Conway. After a while, I wanted to experiment with other rules, and I remembered about the article “ Evolution of the Game of Evolution ” read earlier in the magazine “Science and Life” for 1975 [1]. In this article, trying to develop the game of Life, the author I. Sidorov added a third state for newly born cells. According to the new rules, a cell can be in three states, empty, young and old. The young cell does not die under any circumstances, and in the next generation becomes old.
[01] Designation of cell states
Fully all the rules I. Sidorov formulated as follows:
In the cellular automaton of I. Sidorov there are two ships described by him. Later I managed to find two oscillators. Unfortunately, when a certain critical mass is exceeded, the population loses its structure and grows rapidly. Since it was not interesting to watch this, I undertook to develop my own laws of life and death.
After selecting various options, the following rules were formed:
More visually the rules can be presented in the form of tables. The number of young and old neighbors is postponed along the axes.
[02] Tabular representation of the rule I. Sidorov
[03] Tabular representation of the Steppers rule
This rule seemed so interesting to me that I wrote my article and sent it to the same Science and Life magazine. After a while I received the answer that in the near future publications on cellular automata are not planned. For more than twenty years, I slowly, with long interruptions, dealt with this cellular automaton, but did not attempt to publish it anywhere. And only with the advent of the remarkable program Golly, in which you can create cellular automata by arbitrary rules, the opportunity to share your modest research appeared. Golly is free and can be downloaded from http://sourceforge.net/projects/golly/ .
All illustrations in this article are indexed, if you wish, you can download the archive MilhinSA.Golly2.5.zip in which rle-files with all the examples are located under the appropriate index. In this case, you can not be content with static pictures, but see the process in action. The Golly program can open this archive with a rule and examples without prior unpacking.
In March 2012, I posted a message about the Steppers cellular automaton on the English-language forum Conway's Game of Life . The message aroused some interest among the forum participants, some of whom took part in the Steppers study and shared their findings.
The best way to check the integral characteristics of a cellular automaton is to send a noise signal to its input, or, in other words, a randomly populated population. The following figure shows the evolution of the randomly filled toroidal grid of the game Life and Steppers in the generations 32, 320 and 3200. It can be seen that the population of Steppers decreases more slowly than in the game Life and stabilizes at some stage.
[04] Evolution of the random population of the game Life and Steppers
To obtain statistically reliable data, the following computational experiment was conducted. For each rule, a randomly filled toroidal field measuring 256 x 256 cells with a density of 50% was formed. The cellular automaton worked up to 10,000 generations. For each generation, the field density was calculated in percent, as well as the percentage of cells that changed their state. The last parameter characterizes the activity of the cellular automaton. For each machine, this process was repeated 1000 times, then the output data were averaged.
Below are graphs of density and activity. From these graphs it can be seen that the density and, accordingly, the activity of the game Life quickly falls at the very beginning of development and in the 3000-4000 generation decreases on average to 3% density. Activity drops, on average, to 1%. It is easy to understand that these are the remaining stationary configurations and simple oscillators. Cellular machine Steppers is evolving in another scenario. For about 20 generations, a balance is established between the young and old cells, which leads to a damped oscillatory process. Then the density begins to decrease, and in the 500-700 generation it stabilizes by 21%. Activity stabilizes at 14%. Thus, the evolution of a random field of sufficient size continues indefinitely.
[05] Graphs of changes in density and activity
Graphs of changes in density and activity show the average value for the entire field, but the density and activity of cells changes not only in time but also in space. With the evolution of a uniformly filled random field, it can be seen that the cells are grouped into active regions, forming some kind of texture. To highlight areas with increased activity, a special cellular automaton mapping algorithm was applied. It works as follows. For each cell over 32 generations, the number of births and deaths is calculated. Then the image of the cellular automaton is displayed in the black-red-yellow-white palette. The following figure shows that the active cells in the game Life break up pretty quickly into isolated areas that subsequently fade out. In the Steppers cellular automaton, the active regions continually change shape and size, merge and disintegrate. Quite large areas remain free and there are hospitals, oscillators, as well as gliders and steppers. Due to this, even with the evolution of a random field as a result of self-organization, a rather interesting picture emerges, which is interesting to observe.
[06] Changes in population activity in the process of evolution
It should be recognized that the rule of stepper is not only very tenacious, but also very explosive. Often, the interaction of the simplest configurations leads to an unstoppable growth of the population. Minimum size configurations were found on the Conway's Game of Life forum, causing unlimited population growth. The following figure shows the 5-cell pattern, as well as its state in the 1500 generation, and not completely. The population size is slightly less than 20,000 cells.
[07] 5-cell pattern in 1500th generation
The linear 7-cell pattern develops even more intensively. Here he is depicted in the 500 generation, the population size is 8,124 cells. In the 3000 generation, the population size will exceed 500,000 cells.
[08] 7-cell pattern in the 500th generation
At the moment, two types of moving configurations are found in the Steppers cellular automaton. Moreover, the only type referred to in the first type is called Life Glider in the game. It can be seen that the glider in the Steppers is very slightly different from the glider from the game Life. With such a significant difference in these rules, the existence of gliders was quite unexpected.
[09] Comparison of the gliders of the game Life and Steppers
The steppers are of another type, and their number is unlimited, since their size is unlimited. All steppers are combined in the same way of movement. And this method owes its existence to the birth rule. Let me remind you that it sounds like this: “A young cell is born on an empty cell if it has exactly three neighbors, among which there are at least two old cells”. I will try to explain why the birth rule caused such an effect.
In the game of Life there is such a thing as the speed of light. This is the speed limit at which an endless or closed row of cells can move and is equal to one cell per generation. In Steppers, a row of young cells cannot produce a new row; for this, it first needs to grow old. Therefore, the speed of propagation of an infinite row of cells in Steppers is twice as low as in the game Life and makes up one cell in two generations.
[10] The evolution of an infinite number of cells in the game Life and the Steppers
Now consider the evolution of a finite number of cells. In the game Life opposite the extreme cells, a new cell cannot be born, since it has only two neighbors, therefore each subsequent generation of a new row becomes two cells shorter, and after some time disappears. The same picture is observed with the evolution of a number of cells in the spacecraft Steppers, only two times slower.
[11] The evolution of a finite number of cells in the game Life and Steppers
But if in the Steppers on one side of the row we add to the extreme cells one neighbor at a time so that it does not die out in the first generation, the picture changes completely. You can add neighbors in one of the following ways.
[12] The transformation of a number of cells in the stepper
In this case, at the aging stage, a single cell is born at the edges of the row, and its width is restored. Two old and one young cells can already spawn a new cell and, thus, a number of cells continue to move, continuously restoring their width.
[13] Restoration of cell width
Using this technique, you can create a stepper of any size. Below is a series of 100 cells and a graceful stepper that came out of it after a few hundred generations. His period is eight.
[14] 100-cell stepper
Steppers can be adjacent or composite, they can interact closely or even move as a whole. Here is a small example of various steppers.
[15] Examples of steppers
The sizes of steppers can be unlimitedly large, not only in width, but also in length. As the participant of the forum Conway's Game of Life Emerson J. Perkins ( Emerson J. Perkins (knightlife) ) showed , using regular elements in arbitrary order, you can construct a stepper of arbitrary length.
[16] Designing a stepper of arbitrary length
Unfortunately, at this time, other types of moving configurations are unknown except for gliders and steppers. But I still hope that they exist. The steppers depicted above do not leave behind any configurations, that is, they are spacecraft. Other steppers in the process of movement can leave various stationary configurations, emit gliders and steppers, and often they are followed simply by unabated chaos.
In accordance with the terminology of the game Life, moving configurations that leave trash behind are called puffers . In the following picture you can see a selection of steam locomotives, which, when moving, leave behind a chain of stationary configurations. A locomotive generating a chain of two blocks differs in a record-breaking small period, p 6. At a speed of c / 2 , the blocks are stacked with a period of only three cells. Closer is just impossible. The last steam locomotive forms a continuous line at all. This allows it to be classified as a wickstretcher .
[17] Steam locomotives
Locomotives generating moving configurations are called rake. Such an unexpected name is the result of inaccurate translation. According to Muller’s vocabulary, the word rake has many meanings, including naval “shelling with longitudinal fire” . I suspect that this is what the authors of the term rake meant. But we have got accustomed to the rake, we will have to accept this. Depending on the direction of shooting, the rakes are divided into front, side and reverse. In Steppers, rakes shoot with gliders and steppers. Below you can see the various options rake shooters.
[18] Glider shooting rake, forward and reverse
[19] Side rake
[20] Reverse rakes
Not all locomotives have such a narrow specialization. The steam locomotives in the following figure, along with the stationary configurations, produce reverse steppers.
[21] Reverse rake plus stationary configurations
And this locomotive leaves behind for one period two barges, two small boots, four side steppers and four inverse, including one big stepper 12 cells wide.
[22] Reverse, lateral rakes plus stationary configurations
Unfortunately, the locomotives leaving oscillators, periodic configurations, have not yet been found. In fact, there is a locomotive that generates a couple of buoys, but they are difficult to see against the background of other garbage. So it is rather an exception to the rule.
Breeders are configurations that provide quadratic population growth. The essence of quadratic growth is that the breeder generates configurations, which, in turn, also generate some configurations. There are two types of breeders in Steppers, these are rakes shooting rakes and those shooting locomotives leaving stationary configurations (I hope that this proposal will never be taken out of context).
In the following picture you can see a breeder, such as MMS (moving-moving stationary) . This means that a moving object generates a moving object, which generates stationary objects. With a period of p240, he produces four locomotives that form a chain of buckets.
[23] MMS type multiplier
The next breeder is MMM (moving-moving-moving) . With a period of p32, he releases rakes firing simple steppers. It should be noted the small size of this breeder, a total of 15 cells limited by a rectangle of 5 × 9 cells. In the game of Life, the smallest configuration with quadratic growth is “26-cell quadratic growth” , its size, as the name implies, is 26 cells, and the size is 16,193 × 1,589 cells.
[24] Breeder type MMM
Emerson J. Perkins discovered a very interesting breeder. In his opinion, this is not the case in other known cellular automata. When two identical transverse rakes interact, the same rakes are generated. That is, the two configurations directly generate their own kind.
[25] Two identical configurations generate similar ones.
Emerson J. Perkins designed several more “synthetic” breeders. Below are the multipliers of MMS and MMM type. When creating them, elements of glider synthesis were used, which gives hope for its possibility.
[26] MMS Perkins Breeder
[27] MMM perkins multiplier
There are configurations that release the reverse rake in the opposite direction. These configurations are not destined to become propagators, since the stream of steppers from the first released reverse rake destroys all subsequent ones. Despite this, such patterns are of particular interest. The fact is that in collisions of a newly released reverse rake with a stream of steppers from the first reverse rake, an unexpected effect is manifested. Each released rake destroys the first stepper in the stream, but at the same time restores all previously destroyed ones. But this is exactly how a binary counter works. If we consider the chain of steppers as a sequence of bits and, at the same time, take the missing stepper as “1” and present as “0”, then we can see how the released reverse rake is calculated
[28] Counter
Let's try to create a counter based on this pattern and check how it works. We restrict ourselves to 16 bits, that is, we leave 16 steppers in the stream. Take an arbitrary number, for example, 9780. Its binary representation is 0010011000110100. Given that the period of our counter is equal to p48 , the specified number of reverse rakes will be released in 9780 * 48 = 469440 generation. Now compare the state of the counter in the 0 and 469440 generation. You can verify that the meter is working. The sequence of steppers contains the number given by us.
[29] Example of the counter
A gun (Gun) is called a fixed configuration, releasing gliders or spaceships. At the moment, there are three shotguns shooting steppers, glider guns have not yet been found. The first of these rifles produces four steppers four cages wide. Its period is p32 . The figure shows the sequence of generations T = 0, 6, 12, 18, 24, 32.
[30] Shotgun shooting steppers 4 cells wide in four directions
The second gun has a period of p14 and produces four steppers five cells wide. The figure shows the sequence of generations T = 0, 3, 6, 9, 12, 14.
[31] Shotgun shooting steppers 5 cells wide in four directions
And finally, the gun, which, as expected, shoots in one direction. His period is p10 and it releases six-cell steppers.
[32] Shotgun shooting 6-cell steppers
Oscillators are fixed configurations that are predecessors of themselves. In their development, they after several generations return to some initial state. Currently, about 200 oscillators are known. Some of them have counterparts from the game Life. It is seen that due to the aging of the cells, their period changes upwards. However, not all. The cauldron ( cauldron ) is the oscillator in the last row, in the game Life has a period of p8 . In Steppers, his period was reduced to p5 .
[33] Changing the periods of oscillators from the game Life
As an experiment, a large group of oscillators from the game Life was transferred to the Steppers cellular automaton. Some of them survived, that is, they remained oscillators. Below, shows some of them.
[34] Oscillators that exist in the game Life
To search for oscillators, a special program was created in Steppers, with a rather primitive algorithm. In the center of the toroidal lattice with a size of 256x256 cells, a 16x16 area was filled with cells with a random state. Randomly selected 12 types of symmetry of the contents of the square. Then, over 500 generations, the contents of the central region were compared with 32 previous states. If more than a period ago, the current state has already been encountered, its contents were output to a text file. Once derived patterns were repeatedly not presented again. Then, from a rather voluminous text file, we managed to manually select quite interesting oscillators. Here are some of them.
[35] Examples of oscillators found in Steppers
And here is almost a complete collection of currently known oscillators.
[36] Steppers Cellular Oscillators
There are a lot of collisions in Steppers, it is connected with a big variety of steppers. Because of this, it is difficult to make at least a complete overview of the collisions even for simple steppers. Nevertheless, experiments have shown that in collisions gliders and steppers can be destroyed, born, change direction. Due to the increased survivability of the Steppers cellular automaton, often the result of collisions is an irrepressible increase in population.Probably, this may become an obstacle for the tasks of glider synthesis and synthesis with the participation of steppers.
And now a few examples. Below are shown options for colliding a glider with a block. As can be seen, the result of the collision can be a stepper, a beehive (beehive) and a ship (ship) . Conversely, the result of a collision of a glider with a hive may be a block.
[37] Examples of collisions of a glider with a block.
The following illustration shows examples of collisions of two simple steppers. With a frontal collision, a pond remains, and with a side-oscillator a beacon.
[38] Examples of the collision of two steppers
Member Forum Conway, NH's the Game of Life Juho Pystynen (Tropylium) offeredinteresting and functional examples of collisions. With his permission, publish some of them.
In the first example, four stepper streams collide from the diverging inverse rake. In a non-central collision, they annihilate, emitting four flows of gliders.
[39] Four streams of steppers generate gliders.
In the following example, seven gliders are reflected from two parallel streams of steppers generated by the corresponding inverse rake. In the event of a collision of gliders with a stream of steppers, a sequence of blocks is formed.
[40] Glider Reflection
The article presents the results of a rather superficial study of the Steppers cellular automaton. Many questions remain unclear. For example:
I hope that these open-ended questions will attract amateurs to research the Steppers cellular automaton. I am sure that at the moment it is incomparably easier to make any discovery in Steppers, than, in up and down studied Life game.
MilhinSA.Golly2.5.zip (48.2 kb) - The MilhinSA rule and rle-files of examples.
Steppers-catalog.zip (221 kb) - Catalog of cellular automata Steppers configurations.
SidorovI.Golly2.5.zip (18.9 kb) - Rule SidorovI with examples.
SidorovI.Science_and_Life_1975.03.djvu (187 kb) - I. Sidorov's article in the Science and Life magazine, 1975.03.
For stable configurations, the new rules coincide with the rules of the game Life, therefore all stable configurations in the game Life exist in the new rules. In the described cellular automaton there is a large class of moving configurations, spacecraft. All these configurations move along the same translational mechanism, which resembles the movement of a stepper excavator and a person on crutches. I called such space ships a stepper ( stepper ), and the rule itself Steppers. So we will call it in the future.
There are quite a few oscillators in Steppers, and some oscillators from the Life game also work in Steppers, which speaks of the continuity of the rules. And finally, the famous Conway glider also exists in the proposed rules. The article will consider the dynamics of randomly filled arrays, reveal the mechanism for the movement of steppers, describe the oscillators and steppers found so far. There will also be examples of collisions and complex functional behavior.
')
[00] An example of a moving configuration that generates a stream of steppers.
The history of the development of rules
In 1988, I worked in a technical vision laboratory. Studying the skeletonization algorithm of a raster monochrome image, I wrote a program for its implementation. The skeletonization algorithm itself was not useful to us and was abandoned, and the written program, after a little refinement, turned out to be quite a decent cellular automaton with a graphic editor and a graphical output. The first test for her, of course, was the game The Life of John Conway. After a while, I wanted to experiment with other rules, and I remembered about the article “ Evolution of the Game of Evolution ” read earlier in the magazine “Science and Life” for 1975 [1]. In this article, trying to develop the game of Life, the author I. Sidorov added a third state for newly born cells. According to the new rules, a cell can be in three states, empty, young and old. The young cell does not die under any circumstances, and in the next generation becomes old.
[01] Designation of cell states
Fully all the rules I. Sidorov formulated as follows:
- A young cell does not die of overpopulation or loneliness in one move. After one move, the young cell turns into an old one.
- In each empty cell, a new (young) cell is born, if this cell had three neighbors (both old and young cells could be neighbors).
- An old cell dies from overpopulation if it is bordered by four (or more) old cells or if it is bordered by three (or more) cells, among which there is at least one young one.
- An old cell dies of loneliness if it is isolated or has only one neighbor (both old and young cells can be neighbors).
In the cellular automaton of I. Sidorov there are two ships described by him. Later I managed to find two oscillators. Unfortunately, when a certain critical mass is exceeded, the population loses its structure and grows rapidly. Since it was not interesting to watch this, I undertook to develop my own laws of life and death.
After selecting various options, the following rules were formed:
- A young cell does not die of overpopulation or loneliness in one move. After one move, the young cell turns into an old one (this rule is left unchanged).
- A young cell is born on an empty cell if it has exactly three neighbors, among which there are at least two old cells.
- The old cell continues to exist in the next generation, if it has two or three adjacent cells, among which no more than one is young.
More visually the rules can be presented in the form of tables. The number of young and old neighbors is postponed along the axes.
[02] Tabular representation of the rule I. Sidorov
[03] Tabular representation of the Steppers rule
This rule seemed so interesting to me that I wrote my article and sent it to the same Science and Life magazine. After a while I received the answer that in the near future publications on cellular automata are not planned. For more than twenty years, I slowly, with long interruptions, dealt with this cellular automaton, but did not attempt to publish it anywhere. And only with the advent of the remarkable program Golly, in which you can create cellular automata by arbitrary rules, the opportunity to share your modest research appeared. Golly is free and can be downloaded from http://sourceforge.net/projects/golly/ .
All illustrations in this article are indexed, if you wish, you can download the archive MilhinSA.Golly2.5.zip in which rle-files with all the examples are located under the appropriate index. In this case, you can not be content with static pictures, but see the process in action. The Golly program can open this archive with a rule and examples without prior unpacking.
In March 2012, I posted a message about the Steppers cellular automaton on the English-language forum Conway's Game of Life . The message aroused some interest among the forum participants, some of whom took part in the Steppers study and shared their findings.
Dynamics
The best way to check the integral characteristics of a cellular automaton is to send a noise signal to its input, or, in other words, a randomly populated population. The following figure shows the evolution of the randomly filled toroidal grid of the game Life and Steppers in the generations 32, 320 and 3200. It can be seen that the population of Steppers decreases more slowly than in the game Life and stabilizes at some stage.
[04] Evolution of the random population of the game Life and Steppers
To obtain statistically reliable data, the following computational experiment was conducted. For each rule, a randomly filled toroidal field measuring 256 x 256 cells with a density of 50% was formed. The cellular automaton worked up to 10,000 generations. For each generation, the field density was calculated in percent, as well as the percentage of cells that changed their state. The last parameter characterizes the activity of the cellular automaton. For each machine, this process was repeated 1000 times, then the output data were averaged.
Below are graphs of density and activity. From these graphs it can be seen that the density and, accordingly, the activity of the game Life quickly falls at the very beginning of development and in the 3000-4000 generation decreases on average to 3% density. Activity drops, on average, to 1%. It is easy to understand that these are the remaining stationary configurations and simple oscillators. Cellular machine Steppers is evolving in another scenario. For about 20 generations, a balance is established between the young and old cells, which leads to a damped oscillatory process. Then the density begins to decrease, and in the 500-700 generation it stabilizes by 21%. Activity stabilizes at 14%. Thus, the evolution of a random field of sufficient size continues indefinitely.
[05] Graphs of changes in density and activity
Graphs of changes in density and activity show the average value for the entire field, but the density and activity of cells changes not only in time but also in space. With the evolution of a uniformly filled random field, it can be seen that the cells are grouped into active regions, forming some kind of texture. To highlight areas with increased activity, a special cellular automaton mapping algorithm was applied. It works as follows. For each cell over 32 generations, the number of births and deaths is calculated. Then the image of the cellular automaton is displayed in the black-red-yellow-white palette. The following figure shows that the active cells in the game Life break up pretty quickly into isolated areas that subsequently fade out. In the Steppers cellular automaton, the active regions continually change shape and size, merge and disintegrate. Quite large areas remain free and there are hospitals, oscillators, as well as gliders and steppers. Due to this, even with the evolution of a random field as a result of self-organization, a rather interesting picture emerges, which is interesting to observe.
[06] Changes in population activity in the process of evolution
It should be recognized that the rule of stepper is not only very tenacious, but also very explosive. Often, the interaction of the simplest configurations leads to an unstoppable growth of the population. Minimum size configurations were found on the Conway's Game of Life forum, causing unlimited population growth. The following figure shows the 5-cell pattern, as well as its state in the 1500 generation, and not completely. The population size is slightly less than 20,000 cells.
[07] 5-cell pattern in 1500th generation
The linear 7-cell pattern develops even more intensively. Here he is depicted in the 500 generation, the population size is 8,124 cells. In the 3000 generation, the population size will exceed 500,000 cells.
[08] 7-cell pattern in the 500th generation
Movement, steppers
At the moment, two types of moving configurations are found in the Steppers cellular automaton. Moreover, the only type referred to in the first type is called Life Glider in the game. It can be seen that the glider in the Steppers is very slightly different from the glider from the game Life. With such a significant difference in these rules, the existence of gliders was quite unexpected.
[09] Comparison of the gliders of the game Life and Steppers
The steppers are of another type, and their number is unlimited, since their size is unlimited. All steppers are combined in the same way of movement. And this method owes its existence to the birth rule. Let me remind you that it sounds like this: “A young cell is born on an empty cell if it has exactly three neighbors, among which there are at least two old cells”. I will try to explain why the birth rule caused such an effect.
In the game of Life there is such a thing as the speed of light. This is the speed limit at which an endless or closed row of cells can move and is equal to one cell per generation. In Steppers, a row of young cells cannot produce a new row; for this, it first needs to grow old. Therefore, the speed of propagation of an infinite row of cells in Steppers is twice as low as in the game Life and makes up one cell in two generations.
[10] The evolution of an infinite number of cells in the game Life and the Steppers
Now consider the evolution of a finite number of cells. In the game Life opposite the extreme cells, a new cell cannot be born, since it has only two neighbors, therefore each subsequent generation of a new row becomes two cells shorter, and after some time disappears. The same picture is observed with the evolution of a number of cells in the spacecraft Steppers, only two times slower.
[11] The evolution of a finite number of cells in the game Life and Steppers
But if in the Steppers on one side of the row we add to the extreme cells one neighbor at a time so that it does not die out in the first generation, the picture changes completely. You can add neighbors in one of the following ways.
[12] The transformation of a number of cells in the stepper
In this case, at the aging stage, a single cell is born at the edges of the row, and its width is restored. Two old and one young cells can already spawn a new cell and, thus, a number of cells continue to move, continuously restoring their width.
[13] Restoration of cell width
Using this technique, you can create a stepper of any size. Below is a series of 100 cells and a graceful stepper that came out of it after a few hundred generations. His period is eight.
[14] 100-cell stepper
Steppers can be adjacent or composite, they can interact closely or even move as a whole. Here is a small example of various steppers.
[15] Examples of steppers
The sizes of steppers can be unlimitedly large, not only in width, but also in length. As the participant of the forum Conway's Game of Life Emerson J. Perkins ( Emerson J. Perkins (knightlife) ) showed , using regular elements in arbitrary order, you can construct a stepper of arbitrary length.
[16] Designing a stepper of arbitrary length
Unfortunately, at this time, other types of moving configurations are unknown except for gliders and steppers. But I still hope that they exist. The steppers depicted above do not leave behind any configurations, that is, they are spacecraft. Other steppers in the process of movement can leave various stationary configurations, emit gliders and steppers, and often they are followed simply by unabated chaos.
Locomotives and rakes
In accordance with the terminology of the game Life, moving configurations that leave trash behind are called puffers . In the following picture you can see a selection of steam locomotives, which, when moving, leave behind a chain of stationary configurations. A locomotive generating a chain of two blocks differs in a record-breaking small period, p 6. At a speed of c / 2 , the blocks are stacked with a period of only three cells. Closer is just impossible. The last steam locomotive forms a continuous line at all. This allows it to be classified as a wickstretcher .
[17] Steam locomotives
Locomotives generating moving configurations are called rake. Such an unexpected name is the result of inaccurate translation. According to Muller’s vocabulary, the word rake has many meanings, including naval “shelling with longitudinal fire” . I suspect that this is what the authors of the term rake meant. But we have got accustomed to the rake, we will have to accept this. Depending on the direction of shooting, the rakes are divided into front, side and reverse. In Steppers, rakes shoot with gliders and steppers. Below you can see the various options rake shooters.
[18] Glider shooting rake, forward and reverse
[19] Side rake
[20] Reverse rakes
Not all locomotives have such a narrow specialization. The steam locomotives in the following figure, along with the stationary configurations, produce reverse steppers.
[21] Reverse rake plus stationary configurations
And this locomotive leaves behind for one period two barges, two small boots, four side steppers and four inverse, including one big stepper 12 cells wide.
[22] Reverse, lateral rakes plus stationary configurations
Unfortunately, the locomotives leaving oscillators, periodic configurations, have not yet been found. In fact, there is a locomotive that generates a couple of buoys, but they are difficult to see against the background of other garbage. So it is rather an exception to the rule.
Multipliers
Breeders are configurations that provide quadratic population growth. The essence of quadratic growth is that the breeder generates configurations, which, in turn, also generate some configurations. There are two types of breeders in Steppers, these are rakes shooting rakes and those shooting locomotives leaving stationary configurations (I hope that this proposal will never be taken out of context).
In the following picture you can see a breeder, such as MMS (moving-moving stationary) . This means that a moving object generates a moving object, which generates stationary objects. With a period of p240, he produces four locomotives that form a chain of buckets.
[23] MMS type multiplier
The next breeder is MMM (moving-moving-moving) . With a period of p32, he releases rakes firing simple steppers. It should be noted the small size of this breeder, a total of 15 cells limited by a rectangle of 5 × 9 cells. In the game of Life, the smallest configuration with quadratic growth is “26-cell quadratic growth” , its size, as the name implies, is 26 cells, and the size is 16,193 × 1,589 cells.
[24] Breeder type MMM
Emerson J. Perkins discovered a very interesting breeder. In his opinion, this is not the case in other known cellular automata. When two identical transverse rakes interact, the same rakes are generated. That is, the two configurations directly generate their own kind.
[25] Two identical configurations generate similar ones.
Emerson J. Perkins designed several more “synthetic” breeders. Below are the multipliers of MMS and MMM type. When creating them, elements of glider synthesis were used, which gives hope for its possibility.
[26] MMS Perkins Breeder
[27] MMM perkins multiplier
Counters
There are configurations that release the reverse rake in the opposite direction. These configurations are not destined to become propagators, since the stream of steppers from the first released reverse rake destroys all subsequent ones. Despite this, such patterns are of particular interest. The fact is that in collisions of a newly released reverse rake with a stream of steppers from the first reverse rake, an unexpected effect is manifested. Each released rake destroys the first stepper in the stream, but at the same time restores all previously destroyed ones. But this is exactly how a binary counter works. If we consider the chain of steppers as a sequence of bits and, at the same time, take the missing stepper as “1” and present as “0”, then we can see how the released reverse rake is calculated
[28] Counter
Let's try to create a counter based on this pattern and check how it works. We restrict ourselves to 16 bits, that is, we leave 16 steppers in the stream. Take an arbitrary number, for example, 9780. Its binary representation is 0010011000110100. Given that the period of our counter is equal to p48 , the specified number of reverse rakes will be released in 9780 * 48 = 469440 generation. Now compare the state of the counter in the 0 and 469440 generation. You can verify that the meter is working. The sequence of steppers contains the number given by us.
[29] Example of the counter
Shotguns
A gun (Gun) is called a fixed configuration, releasing gliders or spaceships. At the moment, there are three shotguns shooting steppers, glider guns have not yet been found. The first of these rifles produces four steppers four cages wide. Its period is p32 . The figure shows the sequence of generations T = 0, 6, 12, 18, 24, 32.
[30] Shotgun shooting steppers 4 cells wide in four directions
The second gun has a period of p14 and produces four steppers five cells wide. The figure shows the sequence of generations T = 0, 3, 6, 9, 12, 14.
[31] Shotgun shooting steppers 5 cells wide in four directions
And finally, the gun, which, as expected, shoots in one direction. His period is p10 and it releases six-cell steppers.
[32] Shotgun shooting 6-cell steppers
Oscillators
Oscillators are fixed configurations that are predecessors of themselves. In their development, they after several generations return to some initial state. Currently, about 200 oscillators are known. Some of them have counterparts from the game Life. It is seen that due to the aging of the cells, their period changes upwards. However, not all. The cauldron ( cauldron ) is the oscillator in the last row, in the game Life has a period of p8 . In Steppers, his period was reduced to p5 .
[33] Changing the periods of oscillators from the game Life
As an experiment, a large group of oscillators from the game Life was transferred to the Steppers cellular automaton. Some of them survived, that is, they remained oscillators. Below, shows some of them.
[34] Oscillators that exist in the game Life
To search for oscillators, a special program was created in Steppers, with a rather primitive algorithm. In the center of the toroidal lattice with a size of 256x256 cells, a 16x16 area was filled with cells with a random state. Randomly selected 12 types of symmetry of the contents of the square. Then, over 500 generations, the contents of the central region were compared with 32 previous states. If more than a period ago, the current state has already been encountered, its contents were output to a text file. Once derived patterns were repeatedly not presented again. Then, from a rather voluminous text file, we managed to manually select quite interesting oscillators. Here are some of them.
[35] Examples of oscillators found in Steppers
And here is almost a complete collection of currently known oscillators.
[36] Steppers Cellular Oscillators
Collisions
There are a lot of collisions in Steppers, it is connected with a big variety of steppers. Because of this, it is difficult to make at least a complete overview of the collisions even for simple steppers. Nevertheless, experiments have shown that in collisions gliders and steppers can be destroyed, born, change direction. Due to the increased survivability of the Steppers cellular automaton, often the result of collisions is an irrepressible increase in population.Probably, this may become an obstacle for the tasks of glider synthesis and synthesis with the participation of steppers.
And now a few examples. Below are shown options for colliding a glider with a block. As can be seen, the result of the collision can be a stepper, a beehive (beehive) and a ship (ship) . Conversely, the result of a collision of a glider with a hive may be a block.
[37] Examples of collisions of a glider with a block.
The following illustration shows examples of collisions of two simple steppers. With a frontal collision, a pond remains, and with a side-oscillator a beacon.
[38] Examples of the collision of two steppers
Member Forum Conway, NH's the Game of Life Juho Pystynen (Tropylium) offeredinteresting and functional examples of collisions. With his permission, publish some of them.
In the first example, four stepper streams collide from the diverging inverse rake. In a non-central collision, they annihilate, emitting four flows of gliders.
[39] Four streams of steppers generate gliders.
In the following example, seven gliders are reflected from two parallel streams of steppers generated by the corresponding inverse rake. In the event of a collision of gliders with a stream of steppers, a sequence of blocks is formed.
[40] Glider Reflection
Conclusion
The article presents the results of a rather superficial study of the Steppers cellular automaton. Many questions remain unclear. For example:
- It is not known whether glider guns exist.
- Not a single spacecraft has been discovered that would not be a stepper or glider, although there is no reason to think that they are impossible.
- No locomotives leaving oscillators are found
- Agars have not been studied at all. These are configurations covering the whole plane and periodic in space and time.
- No devourers, configurations, absorbing gliders or steppers were found without harming themselves.
- Glider synthesis is not studied as well as synthesis using steppers.
I hope that these open-ended questions will attract amateurs to research the Steppers cellular automaton. I am sure that at the moment it is incomparably easier to make any discovery in Steppers, than, in up and down studied Life game.
Download Files
MilhinSA.Golly2.5.zip (48.2 kb) - The MilhinSA rule and rle-files of examples.
Steppers-catalog.zip (221 kb) - Catalog of cellular automata Steppers configurations.
SidorovI.Golly2.5.zip (18.9 kb) - Rule SidorovI with examples.
SidorovI.Science_and_Life_1975.03.djvu (187 kb) - I. Sidorov's article in the Science and Life magazine, 1975.03.
Source: https://habr.com/ru/post/237629/
All Articles