Gomel: TRG & VASCO & Salcombe Eesti Ltd.& Russian Academy of Noosphere, 1997.- 296 p.

In what follows, we present general of the work we have done in the mathematical theory of the classical homogeneous structures (HS; synonym Cellular Automata) over the 1969 - 1997. Indeed, we have done much more, particularly in the areas of mathematics, cybernetics, statistics, software, and mathematical theory of homogeneous structures, of course. Much of our research has been stimulated by scientific programs of the Tallinn Research Group (TRG) and the Russian Academy of Noosphere.

The HS is a parallel information processing system consisting of intercommunicating identical finite automata. Although homogeneous structures will be the usual term throughout this book, It should be borne in mind that cellular automata, iterative networks etc. are essentially synonymous. We can interpret HS as the theoretical framework of artificial parallel information processing systems. From the logical point of view the classical HS is an infinite automaton with characteristic cellular internal structure. The theory of HS can be considered to be the structural and dynamical theory of the infinite automata. HS can serve as the basis for modeling of many discrete processes and they present enough interesting independent objects for investigations as well. In recent years there has been considerable interest in the HS theory and many remarkable results have been obtained. Much of this work has been motivated by the growing interest in computer science, biological, physical and mathematical modeling. At present, the HS theory forms an original part of the modern cybernetics.

The modern point of view on the HS theory has been formed under the influence of works by John von Neumann, E.F. Moore, E.F. Codd, G. Hedlund, H. Yamada, A.R. Smith, A. Burks, E. Banks, J. Buttler, N. Margolus, K. Zuse, H. Nishio, R. Vollmar, T. Toffoli, S. Wolfram, S. Amoroso, U. Golze, T. Legendi, M. Nasu, H. Gutowitz, V.Z. Aladjev, A. Podkolzin, G. Tseitlin and many other investigators of different countries. Applied aspects of the HS theory in respect to perspective computers very intensively worked out by scientific schools of T. Toffoli in USA, R. Vollmar in Germany, T. Legendi in Hungary, and in respect to biological modeling by V. Aladjev in Estonia. In our numerous previous works we investigated different aspects of HS theory and their applications in computer science and mathematical modeling. Results in these directions meant substantial new contributions to the HS theory and its applications. The present book is to discuss the more general directions in the classical HS theory and our results obtained therein. It is rather unfortunate that there is not sufficient space here to discuss in detail the wealth of problems in this area. However, we hope that the book at hand will acquaint the reader with the general aspects and tendencies in HS as a formal model of parallel processing and perspective environment for mathematical modeling in the different areas. The book consists of the eight chapters the contents of which can be characterized as follows.

Introduction of the book presents brief history of the HS theory and its applications, including general topics in this direction and investigators, which made the most essential contribution in development of the subject. Furthermore, the most essential scientific forums, research groups and centers in this direction are briefly characterized.

In the first chapter definitions of all general terms, concepts and designations are introduced. The other are introduced as the necessity arises. General components of the classical concept of HS and degree of its community are discussed. The concepts of polygenic, nondeterministic and stochastic HS, and HS with refractority and with memory are introduced, also. Along with that, attendant individual theoretical results linked with these questions are presented. The general architecture of the HS-problems and investigation methods in the direction are discussed.

In the second chapter the nonconstructability problem in the classical HS-models is considered in detail. Questions of nonconstructability are fundamental problems in the study of the dynamical properties of HS-models and its applications. A problem of central importance has been the characterization of the global behavior (dynamics) of HS as a function of the local transition function (LTF). Since the study of histories of configurations (CFs) in HS plays a general role in investigation of HS dynamics, it is interesting to find conditions of the existence of nonconstructible CFs (NCF), i.e. constructive limitations of HS-models. Furthermore, nonconstructability problem for HS-models presents a considerable gnoseological question. In the chapter we present the more important results and the modern state of the nonconstructability problem in the classical HS-models.

Above all, for the purpose of exhaustive investigation of the problems, we introduce four types of the NCF (NCF, NCF-1, NCF-2 and NCF-3), and establish general interconnections between those concepts of nonconstructability. In the item 2.3 a number of criteria of the existence in the classical HS-models of the above typies of nonconstructability are presented. The criteria on the concepts of the mutually erasable CFs (MEC), MEC-1 and -CFs are based. The above concepts (MEC, MEC-1 and -CFs) are discussed in detail.

Particular interest is due to the algorithmical aspects of the nonconstructability problem, which are presented in the item 2.4. In the items 2.5 and 2.6 the special questions for the classical and the special features for the finite HS-models of the nonconstructability problem are discussed, accordingly. Presented in the chapter results solve the nonconstructability problem in the classical HS-models as a whole. More special results in this direction are numerous and allow to investigate the problems in detail. Along with that, results in this direction allow to form rather effective methods for investigation of HS-models dynamics.

In the third chapter the questions of the existence of universal (UCF) and the self-reproducing CFs for the classical HS-models are discussed. On the basis of results on nonconstructability is proved, that for any classical HS-model there is not a finite set of the UCF. In contrast the above result, the problem of the existence of self-reproducing in Moore`s sense CFs has positive solution for the classical HS-models. A number of scientists investigated the problem and with the help of their efforts a class of linear classical HS-models was discovered. HS-models of the class posesses the universal reproductability of the finite CFs in Moore`s sense. Results in this direction allow to discover a number of useful correlations between the nonconstructability and the universal reproductability in the classical HS-models.

In the light of the above results the following extremely interesting problem can be formulated: Can a classical HS-model double any finite CF? This problem has a negative solution. On the basis of the theoretical and computer analysis of the classical HS-models with symmetrical LTF we can formulate the following extremely interesting Hypothesis: Each classical d-HS with the symmetrical LTF and template of size n> (d+1), which has the NCF-1 without NCF (NCF-3), possesses the possibility of universal reproductability of the finite CFs. A new class of the classical HS-models posessed to a considerable extent the reproductability of the finite CFs, can be defined on the basis of the special algebraical system.

In the fourth chapter the problem of complexity of the finite CFs for HS-models is discussed. At present, we know three approaches to the definition of complexity of the finite objects: combinatorial, probabilistic and algorithmical. Our approach can also be called algorithmical; the essence of the concept of complexity consists in the estimation of complexity of generating arbitrary finite configuration from some primitive one by means of the finite number of global transition functions from some basis set.

The our concept of complexity is based on two fundamental results. The first result due to Maruoka-Kimura and characterizes the constructive possibilities of the polygenic HS-models. On the other hand, the second result we received at 1985; it characterizes the dynamic properties of the classical HS-models. On the basis of the introduced concept of complexity a number of important properties of the finite CFs in the classical and polygenic HS-models were received.

On the basis of the mentioned concept of complexity A(X) of the finite CFs we presented solutions of a number of problems in the HS theory. The relations between A(X) and other known measures of complexity are presented. From our results in this direction, in particular, follows that the classical HS-models are not the finite axiomatized formal systems. In the set of all finite CFs the infinite hierarchy of complexity can be established. A number of presented results on the complexity problems in the classical HS-models allows to identify some profound distinctions between parallel and sequential information processing models.

Formal grammar theory (FGT) is a part of the automata theory. Therefore, the study of HS dynamics from the point of view of the FGT appears to be worthwhile and a number of our works are devoted to this problems. The parallel L(n)-languages introduced by us in 1974 can be defined as the set of all finite CFs generated by global transition function of 1-dimensional HS-models from the some initial CFs (axioms). In this case HS-models can be considered as a formal parallel grammars (n-grammars), which does not use nonterminal symbols and rewriting in which is absolutely parallel manner. Thus, n-grammars are similar to well-known Lindenmayer`s systems and can be used for linguistic description of many parallel discrete systems, phenomena and processes.

We investigated n-grammars in conformity with traditions of the FGT with respect that a number of important characteristics of such class of parallel grammars was found and presented in the fifth chapter, which contains the systematic exposition of the n-grammars results on the profound level. Furthermore, many results in the n-grammars theory were applied to the case of nondeterministic Tn-grammars. Thus, we proved that the families of L(n)-and L(Tn)-languages display an extraordinary resistance to traditional closure operations. It is shown that n-grammars are equivalent to parallel programmed array grammars and that there is a constructive on-way bridge from parallel array grammars to n-grammars.

A number of received results in n-grammars and Tn-grammars shows that the traditional approach to working out of programming languages for homogeneous computer systems will not allow to create actually effective parallel software which might use the maximal degree of paralleling admitted by such structures of the finite automata. In our opinion, n-grammars and Tn-grammars are powerful means of mathematical semantics both for microprogramming languages of parallel microprogrammed computation structures and for description of many kinds of cellular systems of the different purposes.

In the sixth chapter is discussed the problem of modeling which plays a very important role in the HS theory itself and in its numerous applications. General aspects of this problems are linked with modeling of one HS by another: realtime modeling, modeling with suppression of certain properties of modelled HS, simplification of characteristics of modelled HS and optimal modeling. We made an attempt to obtain optimum modeling technique. In connection with that the concept of T-modeling was introduced which turned out to be very suitable also for many applications of the HS theory. On the basis of the introduced concept we carried out a detailed study of the multiaspect problem of modeling for the classical HS.

In the chapter a number of algorithms and principles of self-recovering in the real HS-models is presented, which can be useful for practical constructing in the homogeneous computation structures on the basis of HS-models. Along with applied aspects on the basis of T-modeling a sufficiently wide class of theoretical problems was investigated such as: universal computability and parallel algorithms, classes of paralleling, reversibility of modeling and so on. These theoretical results allowed to clarify a number of underlying properties of HS-models both as formal model of parallel computations and as new environment for modeling of various sorts of parallel discrete processes, algorithms and phenomena, especially in such sciences as informatics, cybernetics, biology, physics and synergetics.

In the seventh chapter results on the global decomposition problem (GDP) of global transition functions (GTF) of HS-models are presented. The GDP for HS-models immediatly adjoints the above problem of the complexity A(X). Furthermore, the problem directly concerns the question of constructive complexity of HS-models, which plays an important role both in concrete realizations of parallel computation systems on the basis of HS-models and for modeling in HS-environment. The GDP can be formulated as follows: Can any GTF of the classical HS-models be presented in the form of a composition of the finite number of more simple global functions? On a level with the well-known GDP we present a number of results on the so-called general global decomposition problem (GLDP).

On the basis of results on completeness problem for polygenic HS-models and our results on non-constructability problem for the classical HS-models the negative solution of the GDP for the common case is presented. Then, the GDP and the GLDP were investigated on the basis the number of interesting approaches (Shannon`s function, boolean algebra, K-valued logics and so on). In the item 7.3 the complexity of GTF with respect to the problems of GDP and GLDP, and some linked solvability questions are discussed. Furthermore, in the item a number of very interesting problems, which are intermediate between common and particular GDP, are considered.

We proved a slightly unexpected result, namely: the quota of all GTF defined in alphabet Ap={0,1,2,...,a-1} ( a - prime), which have positive solutions GDP/GLDP, is equal to zero. From our results on the GDP/GLDP among all d-dimensional GTF, defined in Ap-alphabet, the infinite hierarchy of complexity with respect to the GDP/GLDP is established. Moreover, on the basis of some results in GLP-problems and definition of the complexity concept of d-dimensional GTF with respect to the problem GDP/GLDP the solvability of complexity levels of arbitrary global transition functions is proved. The presented in the chapter 7 general results solve the GDP/GLDP problems for the classical HS-models as a whole.

Chapters 27 present the general theoretical aspects of the HS-problems, they contain a number of enough simple and lucid examples which allow to illustrate the considered material. Furthermore, proofs of the some results in the HS theory demonstrate elements of proof technique, which can be used for investigation of the HS-models dynamics and some other aspects of the HS-problems.

At last, in the eight chapter a number of applied aspects of the HS-problems are presented. The applied aspects of the HS-problems present the extremely enormous province, therefore in the chapter we concentrate our attention on applications of HS-models in mathematics, developmental biology and computer sciences. The mathematical applications of HS-approach are used for solution of known problems such as a Steinhays`s combinatorical problem and an Ulam`s problem of the number theory. On the other hand, investigations of HS dynamics on the basis of algebraical approach facilitated appearance of an algebraical system for polynomial representation of K-valued logical functions.

The biological applications of HS-approach are used for modeling of a number of general processes in developmental biology such as growth, self-reproduction, cellular differentiation, regulation and regeneration. Furthermore, applied aspects of HS-problems in computer sciences and some other topics are discussed. Enough wide bibliography embraces the considerable part of the modern HS-problems.

Tallinn, November 1997 Authors

Tallinn Research Group (TRG)   

---

---

Visitor Checking Machine