Creators of the theory and practice of cellular automata

Gottfried Wilhelm Leibniz, 1646 - 1716, the great German philosopher, one of the founders of the infinitesimal calculus, the forerunner of modern mathematical logic, the author of "Monadology" (1714), where the teaching of monads was summarized on 15 pages. Coarse correspondences: the KA monad cell (“atom”), the global transition function of the principle of pre-established harmony Differences from the classical KA: There are no identical monads, the template nonlocality (the monad is “the living sercalo of the Universe”) G.G. Theoretical philosophy of Gottfried V. Leibniz. M.: MSU, p. “Monads do not have windows at all through which something could enter there or exit from there ... when we faint ... the soul does not differ in a noticeable way from a simple monad; but since this state is short-lived and the soul is freed from it, it is something more than a simple monad "interpreted Leibniz’s nature as a habit of God 5

6 John von Neumann, One of the greatest mathematicians of the 20th century. (ergodic theory, etc.), gave an algebraic formulation (in the language of operator theory) of quantum mechanics, the inventor of the computer architecture of the same name, the founder of the theory of KA (1953) KA as a matrix of finite automata / processors exchanging signals with equal delays. Below are the rules for the Neumann automaton with 29 states. > 200 thousand cells - self-reproduction. In he He worked at Oppenheimer’s atomic project “Computer” on EDVAC - ENIAC, which led to early death from brain cancer. The first works on neural networks, in particular, Walter Pitts. The logical calculus of ideas relating to nervous activity (1943) impressed Neumann. If Babbage was looking for analogies between the blocks of a counting machine and production structural units ("mill", "warehouse"), then von Neumann found these analogies in a living organism ("organ", "neuron"). J. von Neumann, Theory of Self-Reproducing Automata, A. Burks, Ed., University of Illinois Press, 1966 in Russian: 1971 and

7 In the proposed book, along with homogeneous structures, more general models of homogeneous structures are also described, which differ from those described by the presence of free exits and exits of generating automata. Kudryavtsev V.B., Podkolzin A.S., Bolotov A.A. Fundamentals of the theory of homogeneous structures. - M .: Science, - 296 p. V.Z. Alad'ev. Classic homogeneous structures. Cellular Automata, Fultus Publishing, Edward F. Moore. "Gedanken-experiments on Sequential Machines," pp. 129 - 153, Automata Studies, Annals of Mathematical Studies, no. 34, Princeton University Press, Princeton, NJ, 1956 Finite state machine (finite state machine) The theory of finite automata, despite its logical precedence, developed simultaneously with the SC and almost the same people from Princeton, within the framework of cybernetics, AI / ALife to games (collective behavior) in multi-agent systems E. Moore: the problem of simultaneous volleys (firing squad synchronization problem), the Garden Theorem Edem M.L. Zetlin. Finite automata and simulation of the simplest forms of behavior // UFM, v.18, 4, p.3-28, 1963 Psakhie, SG et al. (1995). "Method for a movable cellular automata as a tool for simulation within the framework of mesomechanics." Russian Physics Journal, 38 (11). 7 MIKHAIL LVOVICH CETLIN () A prominent Soviet scientist and distinguished engineer who did a lot in such diverse fields as mathematics, physics, biology and medicine (for example, he developed a prosthesis of a controlled hand). He opened a new productive scientific direction - the collective behavior of automata, which now largely determines the promising ways of development of artificial intelligence systems. One of the founders of domestic cybernetics, which in those years was subjected to undeserved criticism; for example, with its help the attitude towards structural linguistics was drastically changed.

8 Konrad Zusé (him. Konrad Zuse),, the Pioneer of the German computer, Stayed in destroyed Germany (Germany), to continue working on the computer series Z1-Z2-Z3-Z4 (), six months ahead of Neumann. Having saved money by selling computers in Europe, he devoted himself to painting and the utopia of “computer socialism”, i.e. planned economy with total computerization. In 1969, he published the book Computational Space (German Rechnender Raum), translated a year later by MTI employees. On its almost one hundred pages, he describes the triple alliance of “mathematics - physics - data processing specialist”, in the “analog VS digital” computer dilemma stands on the side of the latter, and within the framework of this paradigm tries to digitize Maxwell's equations through the spacecraft. eight

9 M. Gardner. The fantastic combinations of John’s Conway’s new solitaire game "life" // column Mathematical games, Scientific American, v. 223 (October 1970): Martin Gardner, Space Engineer in our country, 3rd chapter of the book (1988) John Horton Conway, John Horton Conway (1937-), English mathematician with a wide range of interests, especially in topology and game theory; in 2004, he formulated and proved (together with Cohen) the “free will theorem” in quantum mechanics: if the experimenter is free, then the particle is free; in 1986 took the place of Neumann in Princeton; Now he lectures on philosophy. He invented the “Game of Life” spacecraft (Game of Life, 1970), trying to improve the von Neumann's automaton ... only after the game of three and even sexes. Acceptance of the curb of the pope of the girlfriend many patterns, triangular and hexagonal grids, as well as square, and many other laws of birth and death, including the introduction of two and even three sexes. Acres of paper in a cage were scribbled, and he, along with his graduate students, shuffled chips for poker, foreign coins, cowry shells, Go stones, and so on, until the right balance between life and death was found. 9

10 Edgar Frank Codd (Edgar Frank "Ted" Codd), As an IBM employee, developed the concept of relational databases and the notation of Beuys-Codd, the author of the Universal Designer Codd's spacecraft (1968), which improved the Neumann result (8 states instead of 29), the author of the first Textbook: Codd, Edgar F. (1968). Cellular Automata. Academic Press, New York. Christopher Langton, (Christopher Langton), Founder of Artificial Life Cybernetics (1989), connected with the SC; proposed to use - a parameter for an a priori assessment of the “effectiveness” of the rules of the spacecraft transition, the author (1986) of the two-dimensional Turing machine “Langton ant” (given as the AC) and the spacecraft “Langton Loop” Christopher Langton, "Self-Reproduction in Cellular Automata", Physica D 10, 1984, pp KA WireWorld ("World - Wire") has gained popularity since the release in 1987 of the program of Brian Silverman Phantom Fish Tank (a program for teaching children the features of Logo and "turtle graphics") and notes of Dyudeni. A cell can be in one of 4 states: "non-conductive / void", "head" (electron), "tail" and "conductor". AK Dewdney. Column "Computer Recreations": WireWorld // Scientific American, January, 1990.

11 The developer of the CAM6 system, came up with the idea of ​​a neighborhood of M. (block-swiveling spacecraft) for diffusion models (80s) Norman Margolus (Norman Margolus), Stephen Wolfram, (Stephen Wolfram) Scientist-businessman Written by beststeller-compilation on 1379 pages (2002 ); Binary 1D-KA and rule notation (eg, rule 110); Spacecraft classification into 4 types; Tommaso Toffoli, Fredkin's follower of ideas, Author (along with Margolus) of the book “Machines of the Spacecraft” (1987/1991 - en / ru), author of the Toffoli valve. He is involved in the physical aspect of computability, co-authored Levitin-Toffoli-Margolus theorem (1998) about the speed limit of calculations, proved a number of theorems on reversible spacecraft (including billiard spacecraft) Ed Fredkin (Edward Fredkin), 1934 - At 19 years old, after a year of training at CalTech, he chose the career of a fighter pilot, the developer of the PDP-1 machine (1959) , in his youth he hacked, was the director of the MAC project (1971/74) on artificial intelligence in MTI, the author of retatel SC Fredkin (replicator) and Fredkin valve. He patronized Toffoli and Margolus. Fredkin, Edward; Toffoli, Tommaso (1982), "Conservative logic", Int. J. of Theoretical Physics 21 (3-4): 219–253 11

12 12 Cit. By: Anoprienko A.Ya., Konopleva AP, Modeling of post-binary cellular automata // Mater. conf. Modeling 2010 (May 13-14, 2010, Kiev).