The chapter describes the basic theoretical principles for the theory of cellular automata. The history of the emergence of cellular automata based on an analysis of existing information sources is presented. The modern classification of cellular automata is presented. The structures of elementary and two-dimensional cellular automata are described. In terms of the rules for the functioning of cellular automata, synchronous, asynchronous, and probabilistic cellular automata are briefly described. Researchers are presented who have made a significant contribution to the development of the theory of cellular automata.
TopThe History Of The Emergence The Theory Of Cellular Automata
In our world, any result that contributes to the rapid development of scientific and technological progress is based on the great work of many researchers who have invested a lot of work and in many cases have devoted their whole lives to moving forward in research. Therefore, it is important to know what preceded the formation of a particular theory, what ideas or scientific breakthroughs made it possible to obtain an existing result.
Today, a large number of scientists use cellular automata (CA) in their research. However, not everyone knows the history of the theory of CA. This chapter describes a brief history of the formation of the theory of CA.
So, let's start with a simple one - with the meaning of the term itself. The following definition of cellular automata is given in the book (Toffoli, Margolus 1991): «Cellular automata are discrete dynamical systems whose behavior is completely determined in terms of local dependencies». To a large extent, this is also the case for a large class of continuous dynamical systems defined by partial differential equations. In this sense, cellular automata in computer science are analogous to the physical concept of “field” ... a cellular automaton can be thought of as a stylized world. A uniform lattice, each cell, represents the space or cell of which contains several bits of data. Time goes forward in discrete steps, and the laws of the world are expressed by a single set of rules, say, a small look-up table according to which any cell at each step calculates its new state from the states of its close neighbors. Thus, the laws of the system are local and the same everywhere. “Local” means that in order to find out what will happen here a moment later, it is enough to look at the state of the immediate environment: no long-range action is allowed. “Identity” means that the laws are the same everywhere: “I can distinguish one place from another only in the form of the landscape, and not in any difference in the laws”.
There is and not such a “dry” and more figurative description: “Cellular automata are stylized, synthetic worlds, defined by simple rules, similar to the rules of a board game”. They have their own kind of matter, which is spinning in their own space and time. One can imagine the amazing diversity of these worlds. You can really build them and observe how they develop. Since we are inexperienced creators, it is unlikely that we will be able to get an interesting world on the first try; as people, we can have different ideas about what makes the world interesting, or what we might want to do with it. In any case, after we are shown the world of the cellular automaton, we will want to create it ourselves. By creating one, we will want to try to create another. After creating a few, we can create a world specifically designed for a specific purpose, with some confidence.
The machine of cellular automata is a synthesizer of worlds. Like an organ, it has keys and registers with which the instrument’s capabilities can be powered, combined and rearranged, and its color screen is a window through which you can observe the world that is being “played”.
Now, for a better understanding of the material, we turn to the background of the emergence of such a difficult definition.
It is generally accepted that the founder of the concept of cellular automata was John von Neumann. But a more detailed study of the historical prerequisites for the emergence of this topic allows us to conclude that the very idea of using this architecture appeared almost simultaneously (in the 1940s) at once by several scientists working on different tasks.
At the Los Alamos National Laboratory, John von Neumann worked on self-replicating systems. At the same time, in the same laboratory, another of her collaborators, Stanislav Ulam, was developing a mathematical model of the theory of crystal growth. It is not surprising that when these two scientists met, there was communication and mutual exchange of ideas.