International Academy of Noosphere
Tallinn Research Group
Prof. Dr. Victor Zahhar Aladjev
http://sites.google.com/site/aladjev/Home
aladjev@europe.com, aladjev@gmail.com, aladjev@yandex.ru, aladjev@mail.ru
Cellular Automata: Brief historical survey
We will present our point of view on the history of cellular automata, given our familiarity with this problematics in the early stages of its formation as a separate direction. Today, the problematics of cellular automata (CA, CA–models) is rather well advanced, being quite independent direction of the modern mathematical cybernetics, having own terminology and axiomatic at the existence of broad enough domain of various appendices. In addition, it is necessary to note that at assimilation of this problematics in the Soviet Union in Russian–lingual terminology, whose basis for the first time have been laid by us at 1970 [1] for the concept «Cellular automata» the term «Homogeneous structures» (HS; HS–models) has been determined which nowadays is the generally accepted term together with a number of other our notions, definitions and denotations [1,2]. Whereas rather detailed list of various publications on CA problematics can be found, for example, here [2–8]. Therefore, during the present survey along with this term its well–known Russian–lingual equivalent «Homogeneous structures» quite can be used too.
Cellular automaton (CA) – a parallel information processing system which consists of infinity intercommunicating identical finite Mealy automata (an elementary automaton). We can interpret CA also as a theoretical basis of artificial high parallel information processing systems. From logical point of view a CA is an infinite automaton with specific internal structure. Thus, the CA theory can be considered as structural and dynamical theory of the infinite automata. In addition, CA models can serve as an excellent basis for modeling of many discrete processes, representing interesting enough independent objects for research too. Recently, the undoubted interest to the CA problematics (above all in the applied aspect) has arisen anew, and in this direction many remarkable results have been obtained. Further, by the CA we mean both cellular automata and a separate cellular automaton, depending on the context.
Thus, the CA–axiomatics provides three fundamental properties such as homogeneity, localness and parallelism of functioning. If in such similar computing model we shall with each elementary automaton associate some separate microprocessor then it is possible to unrestrictedly increase a size of similar computing system without any essential increase of its temporal and constructive expenses, required for each new expansion of computing space, and also without any overheads connected to the coordination of functioning of any supplementary quantity of elementary microprocessors. Similar high–parallel computing models admit practical implementations consisting of large enough number of rather elementary microprocessors which are limited not so much by certain architectural reasons as by a lot of especially economic and technological reasons defined by the modern level of development of microelectronic technology, however with the great potentialities in the future, first of all, in light of rather intensive works in field of nanotechnology. In addition, CA models can be used successfully for the problems solving of information transformation such as encryption, encoding, data compression and many others [3,4,7].
The above three such features as high homogeneity, high parallelism and locality of interactions are provided by the CA–axiomatics itself, whereas such property important from the physical standpoint as reversibility of dynamics is given by program way. In light of the listed properties even classical CA are high–abstract models of the real physical world, which function in a space and time. Therefore, they in many respects better than many others formal architectures can be mapped onto a number of physical realities in their modern understanding. Moreover the CA–concept itself is enough well adapted to solution of different problems of modelling in areas such as mathematics, cybernetics, development biology, theoretical physics, computing science, discrete synergetics, dynamic systems theory, robotics, etc. Numerous visual examples available for today lead us to a conclusion that CA can represent a rather serious interest as a new rather perspective environment of modelling and research of different discrete processes and phenomena, determined by the above properties; at that, by bringing the CA–problematics on a new interdisciplinary level and, on the other hand, as a rather interesting independent formal mathematical object of study [7,8].
The base modern tendencies of elaboration of perspective architecture of high parallel computer facilities, the problem of modelling of the discrete parallel processes, discrete mathematics and synergetics, theory of parallel discrete dynamical systems, problems of artificial intellect and robotics, parallel information processing and algorithms, physical and biological modelling, along with a lot of other important prerequisites in the different areas of modern natural sciences define at the latest years a new ascent of the interest to the formal cellular models of different type which possess a high parallel manner of acting; the cellular automata are certain of major models of such type. During time which has passed after appearance of the first monographs and the collected papers that have been devoted to various theoretic and applied aspects of the CA problems, the certain progress has been reached in this direction, that is connected, above all, with successes of theoretical character along with essential expansion of field of different appendices of the CA models, especially, in computer science, cybernetics, physics, modelling, developmental biology and substantial growth of a lot of researchers in this direction. At the same time in the USA, Germany, the Great Britain, Japan, Hungary, Estonia, etc., a lot of works summarizing the results of progress in those or other directions of the CA problematics including its numerous appendices in various fields has appeared. So, our monographs and reports at a certain substantial level have represented the reviews of the basic results received by the Tallinn Research Group (TRG) on the CA problematics and its application [1-7]. From the very outset of our researches on the CA problematics, first of all, with an application accent onto mathematical developmental biology the informal TRG consisting of researchers of leading scientific centers of the former USSR has gradually been formed up. At that, the TRG staff was not strictly permanent and was being changed in rather broad bounds depending on the studied problems. In works [1–7] the analysis of the TRG activity instructive to some degree for research of the dynamics of development of the CA problematics as a independent scientific direction as a whole had been represented. Ibidem, our basic directions of study can be found along with main received results.
Today, cellular automata are being investigated from many standpoints and interrelations of the objects of such type with already existing problems are being discovered constantly. For general acquaintance with extensive CA problematics as a whole along with its separate basic directions specifically, we recommend to address oneself to interesting and versatile reviews of the researchers such as V.Z. Aladjev, V. Cimagalli, K. Culik, D. Hiebeler, A. Lindenmayer, A.R. Smith, P. Sarkar, T. Toffoli, M. Mitchell, R. Vollmar, S. Wolfram, et al. [8]. A series of books and monographs of the authors such as V.Z. Aladjev, T. Toffoli, R. Vollmar, A. Adamatzky, E. Codd, M. Sipper, A. Ilachinskii, M. Garzon, M. Duff, P. Kendall, B. Voorhees, O. Martin, K. Preston, S. Wolfram, N. Margolus, B. Voorhees, V. Kudrjvcev, along with certain others contain a rather interesting historical excursus in the CA problematics; in addition, unfortunately, hitherto a common standpoint onto historical aspect in this question is absent. In view of that, here is a rather opportune possibility to briefly emphasize once again our standpoint on a historical aspect of CA problematics: a brief historical excursus presented below make it one’s aim to define the basic stages of becoming of the CA problematics, having digressed from numerous particulars.
Having started own study on the CA–problematics in 1969, we on base of analysis of large number of publications and direct dialogue with many leading researchers in this direction have a quite certain information that concerns the objective development of its basic directions, first of all, of theoretical character. That allows us with sufficient degree of objectivity to highlight the pivotal stages of its development; at the same time, numerous details of historical character concerning the CA-problematics the reader can find, for example, in a whole series of works presented in links [4,7,8].
From theoretical standpoint the CA concept has been introduced at the end of the forties of the past century by John von Neumann on S. Ulam’s advice with purpose of determination of more realistic and well formalized model for research of behaviour of complex evolutionary systems, including self–reproduction of the alive organisms. Whereas S. Ulam has used CA–like models, in particular, for researches of the growth problem of crystals and certain other discrete systems that grows in conformity with recurrent rules. The structures that have been investigated by him and his colleagues were, mainly, of dimensionality 1 and 2, however higher dimensions have been considered too. In addition, questions of universal computability along with some other theoretical questions of behaviour of cellular structures of such type also were kept in view. A little bit later also A. Church started to study the similar structures in connection with works in field of infinite abstract automata and mathematical logic [8]. J. Neumann’s СА–model has received further development in works of him direct followers whose results along with the finished and edited work of the first one have been published by A. Burks in his excellent works [8], which in many respects have determined development of researches in this direction for several subsequent years. In process of researches on the CA–problematics A.W. Burks has organized at the Michigan university the research team «The Logic of Computer Group» from which a whole series of the first–class experts on the CA–problematics has come out afterwards (J. Holland, R. Laing, T. Toffoli, and others).
At the same time, considering historical aspect of the СА–problematics, we should not forget an important contribution to this problematics which was made by pioneer works Konrad Zuse (Germany) and with which the world scientific community has been familiarized enough late and even frequently without his mention in this historical aspect. At that, K. Zuse not only has created the first programmable computers (1935–1941), has invented the first high–level programming language (1945), but was also the first who has introduced idea of «Rechnender Raum» (Computable Spaces), or in the modern terminology – Cellular Automata. Furthermore, Konrad Zuse has supposed that physical processes in point of fact are calculations, while our universe is a certain «Cellular Automaton» [8]. In the late seventies of the last century such view on the universe was innovative, whereas now this idea of the computing universe horrify nobody, finding logical place in the modern theories of some researchers which work in the field of quantum mechanics [8]. Unfortunately, even at present the K. Zuse’s ideas in many ways are unfamiliar to rather meticulous researchers in this field. Thus, for exclusion of any speculative historical aspects existing occasionally today, in the following historical study it is necessary to pay the most steadfast attention on this a rather essential circumstance. So, namely therefore, only many years later the similar ideas have been republished, popularized and redeveloped in research of other researchers such as S. Wolfram, T. Toffoli, E. Fredkin, et al. [8]. In addition, the CA concept itself has been entered by John Neumann. Perhaps, John Neumann, being familiar with K. Zuse ideas, could use CA not only for simulation of process of reproducing automata, but also for building of high parallel computing models.
From more practical standpoint and game experiment the СА models has notified about itself in the late sixties of the last century when J. Conway has presented the now known game «Life». This game became a rather popular and has attracted attention to cellular automata of both numerous scientists from different fields and amateurs [8]. At the same time, this game, probably, is the most known CA model; at that, it will possess the ability to self–reproduction and universal computing. By modelling the process of work of an arbitrary Turing machine by means of a СА model, J.H. Conway has proved ability of the model to universal computability. Later a rather simple manner of implementation of any Boolean function in configurations of the «Life» has been suggested [8]. So, even such simple CA model turned out equivalent to the universal Turing machine. Indeed, to the given CA model the significant interest exists and till now does not disappear above all to its various computer simulating [8]. Thus, early ideas and research of the first–rate mathematicians and cyberneticians such as K. Zuse, John von Neumann, S. Ulam, A. Church along with their certain direct followers we with good reason can ascribe to the first stage of formation of the CA problematics as a whole.
The necessity for a good formalized environment for modelling of processes of biological development and above all of self–reproduction process was being as one of the base prerequisites which stimulated the CA–concept beginning. At that, J. Neumann and a whole series of his direct followers have investigated a series of questions of computational and constructive opportunities of the first CA–models. The above works at the end of the fifties of the last century have attracted to the given problematics a number of researchers [8]. At the same time, homogeneous structures were being rediscovered not once and under various names: in electrical engineering they are known as iterative networks, in pure mathematics as a section of topological dynamics, in biological sciences as cellular structures, etc.
As second stage in formation of the CA–problematics it is quite possible to consider publication of the widely known works of E.F. Moore and John Myhill on the nonconstructability problem in classical CA–models which along with solution of certain mathematical problems in a certain sense became accelerators of activity, attracting a rather steadfast attention to this problematics of a lot of mathematicians and researchers from other fields [8]. So, for example, we have familiarized oneself with CA–problematics in 1969 owing to Russian translation of the excellent work edited by Prof. R. Bellman, that contained well–known articles of E.F. Moore, S. Ulam and J. Myhill [1]. Scientific groups on the CA–problematics in the USA, Germany, Japan, Hungary, Italy, France, and USSR (ESSR, TRG, 1969) are formed up. The further development and popularization of the CA–problematics can be connected with names of researchers such as E. Codd, S. Cole, E. Moore, J. Myhill, H. Yamada, S. Amoroso, E. Banks, J. Buttler, V. Aladjev, T. Yaku, J. Holland, G.T. Herman, A.R. Smith, A. Maruoka, Y. Kobuchi, T. Ostrand, G. Hedlund, M. Kimura, A. Waksman, H. Nishio, and a number of others researchers whose works in the sixties – the seventies of the last century have attracted attention to this problematics from the theoretical standpoint; they have solved and formulated a lot of interesting enough problems [8]. In the future, mathematicians, physicists, and biologists began to use the CA with the purpose of study of own specific problems. In particular, in the early sixties – the late seventies of the last century the numerous researchers have prepared entry of the CA–problematics into the current stage of its development that is characterized by join of earlier disconnected ideas and methods on the general conceptual and methodological platforms, along with a rather essential expansion of fields of its application.
We can attribute the beginning of the third period to the early eighties of the last century when to CA–problematics the special interest again has been renewed in connection with active enough researches on the problem of artificial intellect, physical modelling, elaboration of a rather perspective architecture of high–parallel computer systems, and a number of important motivations. So, in our opinion namely since the works of the researchers such as Bennet C., Grassberger P., Boghosian B., Crutchfield J., Chopard B., Culik II K., Gács P., Green D., Gutowitz H., Langton C., Martin O., Ibarra O., Kobuchi Y., Margolus M., Mazoyer J., Toffoli T., Wolfram S., Aladjev V.Z., Bandman O., etc. a new splash of interest to the CA began as a perspective environment, first of all, of physical modelling. An extensive enough selection of references, including references on both the Soviet and the Russian–language authors, can be found in links [4,8]. Thus, at present, CA–problematics are being rather widely studied from extremely various standpoints and interrelations of similar homogeneous structures with many existing problems are constantly sought and discovered. A number of rather large teams of researchers in many countries and, first of all, in Germany, the USA, the Great Britain, Italy, France, Japan, Australia, Russia deals with this problematics. Scientific activity in this direction was carried out and in the Estonia within of the TRG, whose a whole series of results has received an international recognition and composed a rather essential part of the modern CA–problematics.
The modern standpoint on the CA (HS) theory has been formed under the influence of works of researchers such as Adamatzky A.I., Aladjev V.Z., Amoroso S., Arbib M., Bagnoli F., Bandini S., Bandman O.L., Bays C., Banks E.R., Barca D., Barzdin J., Binder P., Boghosian B., Burks A. W., Butler J., Cattaneo G., Chate H., Chowdhury D., Church A., Codd E.F., Crutchfield J.P., Culik K.II, Das A.K., Durand B., Durret R., Fokas A.S., Fredkin E., Gács P., Gardner M., Gerhardt M., Griffeath D., Golze U., Grassberger P., Green D., Gutowitz H.A,, Hedlund G., Honda N., Cole S., Hemmerling A., Holland J., Ibarra O.H., Ikaunieks E., Ilachinskii A., Jen E., Kaneko K., Kari J., Kimura M., Kobuchi Y., Langton C., Legendi T., Lieblein E., Lindenmayer A., Maneville P., Margolus N., Martin O., Maruoka A., Mazoyer J., Mitchell M., Moore E.F., Morita K., Myhill J., Nasu M., Neumann J., Nishio H., Ostrand T., Pedersen J., Podkolzin A., Sato T., Richardson D., Sarkar P., Shereshevsky M., Sipper M., Smith A. Sutner K., Takahashi H., Thatcher J., Toffoli T., Toom A., Tseitlin G.E., Varshavsky V.I., Vichniac G., Vollmar R., Voorhees B., Wuensche A.A., Waksman A., Weimar J., Willson S., Wolfram S., Yaku T. along with other numerous researchers from many countries.
Along with our works in the CA problematics, it is necessary to note a lot of Soviet researchers who have received in this direction the fundamental and rather considerable results at the sixties – the eighties of the last century. Here they: Adamatzky A.I. (identification of CA models), Bandman O.L. (asynchronous CA), Blishun A. (growth of patterns), Bliumin S. (growth of patterns), Bolotov A.A. (simulation among classes of CA), Varshavsky V.I. (synchronization of CA, simulation of anisotropic CA on isotropic ones), Georgadze A., Mandzhgaladze P., Matevosian A. (growth of the finite configurations; universal stochastic and deterministic CA, CA models and parallel grammars), Dobrushin R., Vasil’ev N., Stavskaya O., Mitiushin L., Leontovich A., Toom A. (probabilistic CA), Ikaunieks E. (nonconstructible configurations), Koganov A.V. (universal CA, simulation of CA, the stable configurations), Kolotov A.T. (the models of excitable media), Levenshtein V. (synchronization in CA), Kurdiumov G. and Levin L.A. (stochastic CA), Makarevskii A.I. (implementation of Boolean functions in CA), Petrov E.I. (synchronization of 2D-CA), Podkolzin A.S. (simulation of CA; asymptotic of global dynamic; universal CA), Pospelov D. (homogeneous structures and distributed AI in CA models), Evreinov E.V., Prangishvili I. (CA–like architecture of high-parallel processors), Reshod'ko L. (CA of the excitable media), Revin O. (simulation of anisotropic CA on isotropic CA–models), Solntzev S. (growth of patterns), Tzetlin M. (collectives of automata, games in CA), Tzeitlin G. (algebras of shift registers), Scherbakov E.S. (universal algebras of parallel substitutions), and a whole series of others.
It is supposed that the CA–models can play extremely important part as both conceptual and the applied models of spatially–distributed dynamic systems among which first of all an especial interest the computational, physical and biological cellular systems present. In this direction already takes place a rather essential activity of a lot of the researchers who have received quite encouraging results [4,7,8]. At last, theoretical results of the above–mentioned and of a lot of other researchers have initiated a modern mathematical CA theory evolved to the current time into an independent branch of the abstract automata theory that has rather numerous interesting appendices in various areas of science and technique, in particular, in fields such as physics, developmental biology, parallel information processing, creation of perspective architecture of high–efficiency computer systems, computing sciences and informatics, which are linked to mathematical and computer modelling, etc., and by substantially raising the CA concept onto a new interdisciplinary level. Our concise enough standpoint on the main stages of development and formation of the CA theory is given above; for today there is a number of the reviews devoted to this question, for example [8], many works on the CA–problematics in varying degree also concern this question [2-8]. At that, it should be noted that the matter to a certain extent has a rather subjective character, and that needs to be meant.
Meanwhile, some researchers in a gust of certain euphoria try to represent the CA–approach as a universal remedy of the solution of all problems and knowledge of outward things, identifying it with a «New kind» of science of universal character. In this connection it is necessary to mark the vast and pretentious book of S. Wolfram [9], whose title has rather advertising and commercial, than scientific–based character. This book contains many results that have been obtained much earlier by a lot of other researches on CA–problematics, including the Soviet authors (see references in [4,7,8] and some others). At that, the priority of many fundamental results in this field belongs to other researchers. The unhealthy vanity of the author of the book does not allow him to look without bias on history of the CA problematics as a whole. Generally speaking, S. Wolfram enough frivolously addresses with authorship of the results that were received in CA–problematics, therefore, there can be an impression – everything made in this field belongs basically to him. At that, the book contains basically results of computer modelling with very simple types of CA–models, drawing the conclusions and many assumptions on their basis with a rather doubtful reliability and quality. In the book we can meet an irritating density of passages in which the author takes personal credit for ideas that are «common knowledge» among experts in the relevant fields. Seems, such S. Wolfram passages and inferences very similar to them cause utterly certain doubts in judiciousness and scientific decency of their author. At last, we absolutely do not agree that S. Wolfram book presents a “New kind” of science; at the same time, the book would be more pleasant to read if it were more modest. In our opinion, Wolfram book represents in many respects a speculative sight both on CA–problematics, and on the science as a whole. Here we only shall note, that contrary to the pursued purposes the book not only was not revelation for the researches working in the CA–problematics but also to a certain extent has caused a little bit deformed representation about the study domain that is perspective enough from many points of view. With relatively detailed point of view that concerns the book, the reader can familiarize in works [4,8] and some others. Meanwhile, in spite of the told above relative to the book, it can represent a certain interest, taking into consideration the marked and some other remarks. In our opinion, the S. Wolfram bulky book doesn't introduce of anything essentially new in the cellular automata theory, first of all, in its mathematical component.
At last, we will make one essential enough remark concerning of the place of the CA–problematics in scientific structure. By synchronization with the standpoint on CA–problematics that is declared by our book [3] a vision of the given question is being presented as follows. Our long–term experience of investigations in the CA–problematics both on theoretical and especially applied level speaks entirely about another, namely:
(1) CA–models (cellular automata, homogeneous structures) represent a special class of infinite abstract automata with specific internal structure that provides extremely high–parallel level of the information processing and calculations; these models form a specific class of discrete dynamic systems which function in especially parallel way on base of principle of local short–range interaction;
(2) CA can serve as a satisfactory model of high–parallel processing just as Turing machine (Markov normal algorithms, productions systems, Post machine, etc.) serve as formal models of sequential calculations; from this point of view the CA–models it is possible to consider and as algebraic processing systems of finite or infinite words, defined in finite alphabets, on the basis of a finite set of rules of parallel substitutions; in particular, a CA–model can be interpreted as a certain system of parallel programming where the rules of parallel substitutions act as a parallel language of the lowest level;
(3) the principle of local interaction of elementary automata composing a CA–model that in result defines their global dynamics allows to use the CA and as a fine environment of modelling of a rather broad range of objects, processes and phenomena; in addition, the phenomenon of the reversibility permitted by the CA does their by interesting enough means for physical modelling, and for creation of rather perspective computing structures that base on the nanotechnologies;
(4) CA–models represent a rather interesting independent mathematical object whose essence consists in high–parallel processing of words both in finite and infinite alphabets.
At that, it is possible to associate the CA–approach with a certain model analogue of the differential equations in partial derivatives which describe those or another processes with that difference, that if differential equations describe a process at the average, in a CA–model determined in appropriate way, a certain researched process is really embedded and dynamics of the CA–model enough evidently represents the qualitative behaviour of studied process. Thus, it is necessary to determine for an elementary automaton of the model the necessary properties and rules of their local interaction by an appropriate way. The CA–approach can be used for research of processes described by complex differential equations which have not of analytical solution, and for the processes that cannot be described by such equations. Moreover, the CA present a rather perspective modelling environment for research of those phenomena, processes, and objects for which there are no known classical means or they are complex enough.
As we already noted, as against many other modern fields of science, the theoretical part of the CA–problematics is no so appreciably crossed with its second applied component, therefore we can consider CA–problematics as two independent enough directions: study CA as mathematical objects and use the CA for modelling; in addition, the second direction is characterized even by the wider spectrum. The level of evolution of the second direction is appreciably being determined by possibilities of the modern computing systems because CA–models, as a rule, are being designed on base of the immense number of elementary automata, having, as a rule, rather complex rules of local interaction among themselves.
The indubitable interest to them amplifies also a possibility of practical realization of high parallel computing CA on basis of modern successes of microelectronics and prospects of information processing at the molecular level (methods of nanotechnology); whereas the CA–concept itself provides creation of conceptual and practical models of various spatially–distributed dynamic systems of which physical systems are the most interesting and perspective. Indeed, models that in obvious way reduce certain macroscopic processes to rigorously determined microscopic processes represent special epistemological and methodical interest for they possess the great enough persuasiveness and transparency. Namely, of this standpoint the CA-models of different type represent an especial interest, first of all, from the applied standpoint at study of a lot of phenomena, processes and objects in various fields, first of all, in developmental biology, physics and computer science.
If the first direction enough intensively is developed by the mathematicians than contribution to development of the second direction essentially more representative circle of researchers from different theoretical and applied fields (physics, chemistry, biology, technique, etc.) brings. So, if theoretical study on CA–problematics in general are limited to the classical, polygenic and stochastic CA–models, then the results of the second direction base on essentially wider representation of classes and types of CA–models. As a whole, if classical CA–models represent first of all the formal mathematical systems studied in appropriate context, then their numerous generalizations represent a rather perspective environment of modelling of various objects.
In the conclusion once again it is necessary to note an important enough circumstance, at discussion of the Classical cellular automata (CCA) we emphasized the following a rather essential moment. We considered CCA–models which are a class of parallel discrete dynamic systems as certain formal algebraic systems of processing of finite configurations (words) in finite alphabets whatever, as a rule, to their microprogrammed environment, i.e. without use of their cellular organization on the lowest level inherent into them, what distinguishes our approach to research of the given objects from approaches of a number of other researchers. Also, we consider CCA–models as a formal mathematical object having specific inside organization without ascribing to them a certain universality and generality in perception of the World. At such approach the CCA are considered at especially formal level not allowing using to the full their intrinsic property of extremely high parallelism in field of computations and information processing as a whole.
Naturally, for solution of a number of various applied problems in the CA–environment and obtaining of a series of thin results, first of all, of model character an approach on microprogram level is needed when a researched process, algorithm or phenomenon is directly embedded in a CA–model, using its parameters: dimension, neighbourhood index, a states alphabet and a local transition function. At such approach it is possible to receive solutions of a lot of important appendices with generalizations of a rather high level of theoretical character. In particular, by direct embedding of universal computing algorithms or logical elements into such objects it is possible to constructively prove existence of the universal computability, etc. In spite of such extremely simple concept of the CCA, they by and large have a rather complex dynamics. In many cases theoretical research of their dynamics collides with a rather complexity. Therefore, computer simulation of these structures which in empirical way allows to research their dynamics is a rather powerful tool. For this reason this question is a quite natural for investigations of the CA–problematics, considering the fact that CA–models at the formal level represent the dynamic systems of high–parallel substitutions.
Indeed, the problem of computer modelling of the CA is solved at two main levels: modelling of CA dynamics on computers of traditional architecture, and modelling on hardware architecture which corresponds to the maximal possible to the CA concept; so-called CA-oriented architecture of computer systems. So, computer simulation of the CA models plays a rather essential part at theoretical research of their dynamics; meanwhile, it is even more important at practical realizations of the CA models of different processes. At present, a whole series of interesting systems of software and hardware for help of investigations of different types of the CA models have been developed; their characteristics can be found in the references [3,8]. In our works a lot of programs in various program systems for different computer platforms had been presented. Among them a number of rather interesting programs for simulation of the CA models in the Mathematica and Maple systems has been programmed. On the basis of computer simulation many of interesting theoretical results on the CCA and their use in the fields such as mathematics, developmental biology, computer sciences, etc. had been received. However, the given matter along with applied aspects of the CA–models in the present article aren`t considered, despatching the interested reader to a rather detailed discussion of these aspects to the corresponding publications in lists of references [8] and in references given in [2-7]; a lot of interesting works can be found in Internet by the appropriate key phrases.
The problematics considered by the TRG study in many respects has been conditioned by interests and tastes of the authors along with traditions of creative activity of the TRG in this field. At last, we will note that in our activity it is possible to allocate three main directions: (1) study of classical CA as a formal parallel algorithm of processing of configurations in finite alphabets, (2) applications of classical and generalized CA in mathematics and computer facilities of highly parallel action, and (3) mathematical and developmental biology. With our results in two last directions the interested reader can familiarize in sufficient detail in [2-7] and in numerous references contained in them along with references concerning many other researchers in this field.
References
1. V.Z. Aladjev. To the Theory of the Homogeneous Structures.– Tallinn: Estonian Academic Press, 1972. (in Russian with English summary). Monograph is the first Russian book in CA problematics. It contains Russian terminology and a series of rather interesting both theoretical and certain applied results (CA–approach for biological modelling above all). This book contains early results of the Tallinn Research Group (TRG) in the CA problematics. In annual meeting of the Estonian Academy of Sciences the book was marked as one of the better works of the Academy in 1972. Монография впервые в СССР ввела русскоязычную терминологию основных понятий и определений теории однородных структур (классических клеточных автоматов), она представила ряд новых результатов и была признана лучшим монографическим изданием АН ЭССР за 1972 год, в значительной степени инициировав интерес к данной проблематике в СССР.
2. V.Z. Aladjev. Mathematical theory of homogeneous structures and their applications.– Tallinn: Valgus Press, 1980, 270 p. In this book the writer presents main of the work that Tallinn Research Group has done in the CA theory and its applications in 1970–1980. The book discusses the topics such as: architecture of the CA theory and its applications, the general aspects of CA dynamics, some CA models along with certain basic, in author's opinion, problems for the following researches in the CA problematics.
3. V.Z. Aladjev. Homogeneous Structures: Theoretical and Applied Aspects.– Kiev: Technika Press, 1990 (in Russian with English summary). In the monograph the main of the work of the Tallinn Research Group done in the mathematical CA theory and its applications in parallel processing and parallel algorithms, theoretical and mathematical biology, computer science, mathematical modelling in during 1969–1989 is presented. Much of this work has been motivated by both the CA models as an independent mathematical object and by the growing interest in computer science and mathematical modelling. At present, in our opinion, CA theory forms a self–maintained part of the modern mathematical cybernetics and complex systems theory.
4. В.З. Аладьев. Классические однородные структуры: Клеточные автоматы .– USA: Palo Alto: Fultus Books, 2009, 535 с., ISBN 159682137X (https://yadi.sk/d/Uaa6ac9vm-rp5A). The monograph is based on a special lecture course "Classical Homogeneous Structures Theory (Classical Cellular Automata)" given by the author for senior students, undergraduates and doctoral students of the Faculty of Mathematics and Computer Science of Grodno State University (West Belarus) in April – May 2008..
5. V.Z. Aladjev. Classical Cellular Automata: Mathematical Theory and Applications.– Germany: Saarbrucken: Scholar`s Press, 2014, 512 p., ISBN 97836390713459 (https://yadi.sk/d/InNJzIrWPgZbDw).
6. V.Z. Aladjev, M.L. Shishakov, V.A. Vaganov. Selected problems in the theory of classical cellular automata.– USA: Lulu Press, 2018, 410 p., ISBN 9789949987627 (https://yadi.sk/d/2A_81MOLPvRfgg).
The BookAuthority included the given book in list of the 100 Best Discrete Mathematics eBooks of All Time. As featured on CNN, Forbes and Inc, the BookAuthority identifies and rates the best books in the world, based on recommendations by thought leaders and experts; https://bookauthority.org/books/best-discrete-mathematics-ebooks; https://bookauthority.org/award/Selected-problems-in-the-theory-of-classical-cellular-automata/173095037X/best-discrete-mathematics-ebooks. BookAuthority also noted this publication among the finite automata eBooks of all time - https://bookauthority.org/books/best-selling-finite-automata-ebooks
7. В.З. Аладьев, В.А. Ваганов, М.Л. Шишаков. Базовые элементы теории клеточных автоматов.– USA: Lulu Press, 2019, 418 c., ISBN 9780359735129 (in Russian — https://yadi.sk/d/i0q8D901S-e3XA).
8. Links on the CA problematics — http://www.hs-ca.narod.ru or http://ca-hs.weebly.com
9. S. Wolfram. A New Kind of Science.– N.Y.: Wolfram Media, 2002.
10. Interview in Russian and English concerning the CA problematics – https://all-andorra.com/ru/viktor-aladev-o-bazovyx-elementax-odnorodnyx-struktur-i-teorii-kletochnyx-avtomatov
11. Aladjev Victor. Cellular Automata, Mainframes, Maple, Mathematica and Computer Science in the Tallinn Research Group.— USA: Kindle Press, 2022.— 150 p. — ISBN 9798447660208. This book, with one degree or another degree of detail, provides an overview of scientific and applied activity directions of the Tallinn Research Group throughout its activity during 1970—2022, including cellular automata theory. It is worth focusing on the fact that to a large extent the real book is of a pronounced final nature, relating to the activity of Tallinn Research Group and the associated Baltic branch of the International Academy of Noosphere, whose activity has been rather seriously decreased due to a number of significant enough circumstances since July 2022.
Useful links for free reading and downloading the above book:
https://dspace.spbu.ru/handle/11701/36376
https://elib.grsu.by/doc/82629
https://disk.yandex.ru/i/TCgmiB0LYL7dyA
https://rlst.org.by/2022/06/07/v-rntb-unikalnaya-kniga-v-otkrytom-dostupe/
https://www.iprbookshop.ru/122331.html
https://drive.google.com/file/d/1-cb0AmDwgyAZoueY47VZDNCqQQgrjEuZ/view?usp=sharing
https://bis.nlb.by/ru/documents/140947 — Беларусь у Асобах i Падзеях: Аладзьеў В.З. (in Byelorussian)
https://famous-scientists.ru/anketa/aladev-viktor-zaharovich-2763
https://www.amazon.com/author/victor_aladjev — Aladjev's page on Amazon portal