In the book we present certain results of the work we have done in the theory of ClassicalCellular Automata (CA). At present, these results form an essential constituent of the CAproblematics. In particular, we have studied such problems as the nonconstructability problem in the CA,the decomposition problem of global transition functions in the CA,extremal constructive possibilities, theparallel formal grammars and languages defined by CA,complexity of finite configurations and global transition functions in the CA,simulation problem in classical CA,etc. At present, the CAproblematics is a rather well developed independent field of the mathematical cybernetics that has a rather considerable field of various appendices.In addition,with the equal right theCAproblematics can be considered as a component of such fields as discrete parallel dynamical systems, discrete mathematics, cybernetics, complex systems and some others. In our viewpoint, the book will represent an indubitable interest for students, post–graduates and persons working for doctor's degree of the appropriate faculties of universities, above all, of naturally scientific level along with teachers in subjects such as mathematical and physical modelling, discrete mathematics, automata theory, computer science, cybernetics, theoretical biology, computer technique, and a lot of others. In recent years, the classical CA models are one of the most promising simulating environments for various highly parallel discrete processes, objects and phenomena admitting reversible dynamics, that is enough important from a physical point of view, in the first place.
Excerpt:
First of all, a few words about the terminology used below. Today, the problems of Cellular Automata (CA, CA-models) is rather well advanced, being quite independent field of the modern mathematical cybernetics, having own terminology and axiomatics at existence of broad enough domain of various appendices. In addition, it is necessary to note that at assimilation of this problems in the Soviet Union in Russian-lingual terminology, whose basis for the first time have been laid by us at 1970, 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 whole series of other notions, definitions and denotations [1-6]. Therefore, during the present monograph along with this term its well-known Russian-lingual equivalent «Homogeneous structures; HS» can be used too.
Cellular Automaton (CA) – a parallel information processing system that consists of intercommunicating identical Mealy automata (elementary automata). We can interpret CAs as a theoretical basis of artificial high parallel information processing systems. From the logical standpoint a CA is an infinite automaton with specifical internal structure. So, the CA theory can be considered as structural and dynamical theory of the infinite automata. At that, 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 problems (above all in applied aspect) has arisen anew, and in this direction many remarkable results have been obtained. Further, by CA we mean both cellular automata and a separate cellular automaton, depending on the context.
So, the CA–axiomatics provides three fundamental properties such as homogeneity, localness and parallelism of functioning. If in a similar computing model we shall with each elementary automaton associate a separate microprocessor then it is possible to unrestrictedly increase the sizes of similar computing system without any essential increase of its temporal and constructive expenses, required for each new expansion of the computing space, and also without any overheads connected to coordination of functioning of an arbitrary supplementary quantity of elementary microprocessors. Similar high–parallel computing models admit practical realizations consisting of rather large number of rather elementary microprocessors which are limited not so much by certain architectural reasons as by a lot of especially economic and technologic reasons defined by a 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. Along with it the CA models can be used for problems solving of information transformation, such as encryption, encoding and data compression [7].
The above three such features as high homogeneity, high parallelism and locality of interactions are provided by the CA–axiomatics itself, while 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 lot of physical realities in their modern understanding. Moreover the CA– concept itself is enough well adapted to solution of various problems of modelling in such areas as mathematics, cybernetics, development biology, theoretical physics, computing sciences, discrete synergetics, dynamic systems theory, robotics, etc. Told and numerous examples available for today lead us to the conclusion that the CA can represent a rather serious interest as a new perspective environment of modelling and research of many discrete processes and phenomena, determined by the above properties; in addition, raising the CA–problematics onto a new interdisciplinary level and, on the other hand, as an interesting enough independent formal mathematical object of researches [7,21,82].
