In this chapter, the author reviews the main historical aspects of the development of cellular automata. The basic structures of cellular automata are described. The classification of cellular automata is considered. A definition of a one-dimensional cellular automaton is given and the basic rules for one-dimensional cellular automata are described that allow the implementation of pseudo-random number generators. One-dimensional cellular automata with shift registers with linear feedback are compared. Synchronous two-dimensional cellular automata are considered, as well as their behavior for various using local functions. An analysis of the functioning of synchronous cellular automata for the neighborhoods of von Neumann and Moore is carried out. A lot of attention is paid to asynchronous cellular automata. The necessary definitions and rules for the behavior of asynchronous cellular automata are given.
TopThe History Of The Development Of Cellular Automata
The history of CA theories of occurrence and development are widely described in the literature (Wolfram, 1986; AUTOMATA-2008, 2008; Herrmann, & Margenstern, 2003; Wolfram, 2002; Adamatzky, 1994; Alonso-Sanz, & Margarita, 2006; Adamatzky, 2010; 10th International Conference on Cellular Automata for Research and Industry [ACRI 2012]; 11th International Conference on Cellular Automata for Research and Industry [ACRI 2014]; Twelfth International Conference on Cellular Automata for Research and Industry, [ACRI 2016]). In these works, the founders of the theory of the CA is Stanislaw Ulam and John von Neumann (1940 year). The Stanislaw Ulam has recommended to use to John von Neumann a simple grid model (Pickower, 2009) for the construction of self-replicating systems problems solutions (Neumann, 1951; Kemeny. 1955).
In 1940 Norbert Wiener and Arturo Rosenblueth developed an automaton model of excitable medium (Wiener, & Rosenblueth, 1946).
Arthur Burks developed the theory of CA. John Holland used CA to adaptation and optimization solution of problems (Holland, 1966).
In 1960 Gustav A Hedlu has described many results on CA mathematical investigation (Hedlund, 1969).
In 1970, Martin Gardner published a paper in which he has described positively the “Life” game (Gardner, 1970). In the “Life” game is described the process of dying and life of a cells and their states depend on the state of life of the neighboring cells.
Stephen Wolfram has made a great contribution to the development of the CA theory. He has published papers in which was described the elementary cellular automata theory and, based on it was formed the true randomness theory (Wolfram, 1986a). Wolfram describes the set of rules that each CA cell performs. The cell goes into a state, which depends on the state of its own and the state of the neighboring cells in the previous point in time. The cell performs the function in accordance with a predetermined rule. Stephen Wolfram explores the rules and he indicates that the rule 110 may be universal. Matthew Cook has proven this statement in the year 1990. Additionally, Wolfram proposed the PRNG based on the one-dimensional CA (Wolfram, 1986b).
In 1987, Brian Silverman proposed the Turing complete cellular automaton (Dewdney, 1990).
The new continuation of the CA theory is book, which was published by Stephen Wolfram, entitled “A New Kind of Science.” In this work, he examined the one-dimensional, two-dimensional and three-dimensional cellular automata. Wolfram argues that the world is discrete, and that it can be studied by CA. Due to the Wolfram theory the CAs gained immense popularity. Wolfram offered simple rules, which are still used for solving many problems.
Alonso-Sanz proposed CA with memory and the extensive analysis of their behavior and application was held (Alonso-Sanz, 2006; Alonso-Sanz, 2009; Alonso-Sanz, 2013).