AMS: 68D20, 68A05, 92A90, 03B20, 03D05

Aladjev V., Hunt Ь., Shishakov M. Mathematical Theory of the Classical Homogeneous Structures.- Gomel: BELGUPT Press, 1996.- 150 p.

For better Browsing use Netscape-2 or better and some Cyrillic font!

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 April 1996 - August 1996. Indeed, we have done much more, particularly in the areas of mathematics,statistics,software, cybernetics and mathematical theory of homogene-ous structures, of course. Much of our research has been stimulated by scientific programs of 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 etc. are essentially sy-nonymous. We can interpret HS as the theoretical framework of artificial parallel information processing systems. From the logical point of view the HS is an infinite automaton with cha-racteristic 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 modelling of many discrete processes and they present enough interesting independent objects for investigati-ons 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 grow-ing interest in computer science and mathematical modelling. At present, the HS theory fo-rms 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, H. Nishio, R. Vollmar, T. Toffoli, S. Wolfram, V.Z. Aladjev 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 Ger-many, and in respect to biological modelling - by V. Aladjev in Estonia. In our numerous previous works we investigated different aspects of HS theory and their applications in com-puter science and mathematical modelling. 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 d-dimensional HS theory and our results obtained therein. It is rat-her unfortunate that there is not sufficient space here to discuss in detail the wealth of prob-lems 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 perspec-tive environment for mathematical modelling. The book consists of the five chapters the con-tents 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 cla-ssical concept of HS and degree of its community are discussed. The concepts of non-dete-rministic and stochastic HS, and HS with refractority are introduced, also. Along with that, at-tendant individual theoretical results linked with these questions are presented.

The classical definiton of the HS makes it an ordered set of four components

where A is a finite, nonempty set called the state alphabet, and it is the set of states which each of the individual finite-state automata in the structure can assume. The state alphabet contains a distinguished element called the quiescent state, which is denoted by 0. Let the state alphabet A={0,1,2,...,a-1} contains a elements. Zd is the set of all d-tuples of inte-gers which is used to name the cells, where Z is the set of integers, and is called the array. We think that other types of regular arrays for HS achieve nothing mathematically for its be-havioral properties - the integer lattice is sufficient. Each automaton in Zd can be thought of as the name or address of the particular finite-state machine which occupies that position in the array. It will frequently be convenient to identity the automaton located at cell i with the i-cell itself.

X, called the neighborhood index of the HS, is a n-tuple of distinct d-tuples of integers and is used to define the neighbors of any cell, i.e., those cells from which the cell will directly receive information. The n neighbours of cell Z are cell z+1,z+2,....,z+n, where X={1,2,...,n}. The neighborhood index X describes the uniform interconnection pattern among the elementary automata in HS. It represents the positions relative to a gives cell k of all the cells whose automata are directly connected to cell k. If X contains the point 0n={0,0,...,0}, every cell is contained in its own neighborhood, where neighborhood con-sists of all neighbours of cell. Without loss of generality we may assume that X contains the point 0n. The first three above-mentioned components of any HS, namely, the state alphabet A, the array Zd and the neighbourhood index X, form a homogeneous space. The homo-geneous space is the static part of the HS. It describes the physical structure of the HS, but does not specify the interactions which will take place among the elementary automata in Zd.

In order to study the operation of HS, it is necessary to have a means of describing the current state of the entire homogeneous space, at any given time. The state of the entire space is called a configuration of the space and is simply the complete set of current sta-tes of each of the individual automata. A configuration (CF) is any mapping CF: Zd A; C(A,d) denotes the set of all configurations with respect to Zd and A - C(A,d)={CF|Zd A. Let c(k) be the current state of the automaton located at k-cell. The support of a CF c (denoted by [c]) is the set of all cells k such that c(k)0; i.e., the support is the nonquies-cent part of c-CF. Configurations with finite support are of considerable interest; the set of all such configurations is denoted by C(A,,d); C(A,,d) denotes the set of all configura-tions with infinite support and C(A,d)=C(A,,d)C(A,,d).

A special notation is used to represent sets of 1-dimensional CF with finite and infi-nite support, consequently C(A,) and C(A,); C(A)=C(A,)C(A,). Finite configura-tion cC(A,) is represented by x1x2x3...xm, where indicating a string of unbounded length of elementary automata in 0-state, i.e., x1x2...xm ...000x1x2...xm000... . Let null-CF C(A,). The length of a finite CF c is defined to be the distance between two extreme automata in states of A\{0}, and will be also denoted by |c|.

The operation of the HS is specified by a local transformation (function) (n), which produce the next state of an individual automaton k in terms of the states of the automata, which are directly connected to k. We shall be concerned with a local function (n), which is defined to be a mapping from An to A such that (n)(0n) always equals 0. For the rest, the local function (LTF) is any mapping (n): An A. The simultaneous application of a local transformation (n) to the neighbourhood of every automaton of the homogeneous space defines a global transformation (function) (n) (GTF) of the current CF c into the next CF c(n). The formal definition of c(n) is follows.

Let C(A,d) denotes the set of all configurations with respect to Zd and A. The image of zZd under cC(A,d) is written c(z). The neighbourhood index X and a local map (n): An A define a global map (n): C(A,d) C(A,d) as follows: c(n)=c` if and only if for any zZd, c`(z)=(n)(c(z+1),c(z+2),c(z+3),...,c(z+n)). It follows immediately from this definition that every (n) defines a unique global function (n), and that cannot be defined (n) from two different local transformations. There is, in other words, a 1-1 cor-respondence between the set of all (n) global functions (GTF) and the set of all (n) local functions (LTF) for a given A-state alphabet, d-dimension of Zd-space and neighbo-urhood X-index. It is therefore possible to speak about the (n) defined by (n), and vice versa.

The fourth component of the HS can now be defined. For a given A, Zd and X the set of admissible transformations T is any nonempty subset of the complete set of all global transitions definabled from A, Zd and X. If set T contains a single GTF (n), the such obj-ect HS=<Zd,A,(n),X> is said to be monogenic (or classical) HS. The operation of a classical HS is particularly simple: if c=co is an initial CF of the homogeneous space Zd at time t=0, then the CF at time t=m is c`=co(n)m, the result of applying GTF (n) to the homogeneous space m times. In case of so-called polygenic HS an explicitly written-out sequence of GTF is required to specify a particular computation of the HS=<Zd,A,T,>, where is function which describes the order of application of global functions of T to any initial CF of ho-mogeneous space Zd. Thus, if co is a configuration and =joj1.....jk... is a sequence of global transformations of T, then the sequence of configurations co, c1,...,ck,... is called the configuration sequence generated by -rule from the ini-tial CF co, if for each k0, ckjk=ck+1. Let <co>[] and <co>[(n)] denote the configu-ration sequences generated by -rule of polygenic HS and by GTF (n) of the classical HS, accordingly.

In the present work we shall consider the classical HS, in general. Furthermore, un-less states otherwise, by "HS" we shall mean classical 1-dimensional HS=<Z,A,(n),X>, where A={0,1,2,...,a-1} and X={0,1,2,...,n-1}. Thus, the concept of classical HS is intuitively extremely simple. In this connection questions arise about the extent of community of such concept, i.e. how much this concept admit broadenings which do not bring out over framework of some possibilities of classical concept of HS. We considered[1] only generable power of the classical HS and proved that a number of widenings of classical concept of HS show that, even in respect of enough narrow concept of equivalence of two HS, the con-cept of classical HS possesses the sufficient degree of community. In works [1,4,12,23] we defined and investigated the so-called non-deterministic, stochastic HS and HS with refractority. In the present work are discussed HS with refractority and HS`, which is very suitable for describing of many parallel discrete processes in HS-models.

HS*, by definition, is a four-tuple HS*=<Z,A,I,>, where Z and A are defined as for classical 1-dimensional HS, I is a set of impulses and is a functional algorithm (FA) of HS*. We shall associate an automaton to each point k of Z, and we shall identity it with k. FA is defined by the following discrete correllations:

where a1(i), a(i) are states of i-automaton; ir, kl are right and left income impulses of i-automaton; j1r, j1l are right and left outcome impulses of i-automaton. As stated, every HS* can be constructively embedded in the classical HS. Furthermore, under certain condi-tions HS* can be embedded in the classical HS=<Z,A`,(3),X>, where A`=AI [3,4]. The above concept of HS*-structure can be generalized on the common case of d-dimensionali-ty (d>1).

The HS with refractority can be defined as follows. Let HS=<Zd,A,(n),X>, whe-re A={0,1}{1,2,3,...,r}, is called HS with refractority {HSR(d,r,P)}, if its GTF (n), is defined by the local transition function (n), such that:

As regards the states of the automaton in HSR(d,r,P) the most general states are choosen: rest (0), excitation (1) and refractority of r-depth {1,2,3,..,r}. According to the neighbourhood X-index there is the possibility of various structural interrelations between the automata in such HSR. The general object in such structure is investigation of the dynamical distribution of automata in excitation (1) states in conformity with the initial CF, neighbour-hood X-index, threshold (P) of excitation and the r-depth of refractority.

At present, the HS theory presents highly enough developed independent area of the modern cybernetics, which has a considerable sphere of applications in different branches of science and engineering. In the our monographs [4,12] the architecture of the HS theory and its applications from our point of view is presented. The architecture takes into account the discussion of our previous attempts in this direction and the most general recent theoretical and applied results in the HS theory. We hope that the architecture will be described in detail and will be verified in the relevant limits, since its analysis can be useful in the choice of sub-sequent directions for investigations in this topic.

The following chapters of the book are devoted to the HS theory and contain the most essential results in this direction, which were obtained by Tallinn Research Group (TRG) in the course of april-august 1996 including some general results, which were received in the previous period of TRG-activity [12,23]. The present problems are discussed on the basis of 1-dimensional HS, but, practically all general results, can be generalized on the case of hi-gher dimensionalities.

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 importa-nce has been the characterization of the global behaviour (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. Further-more, nonconstructability problem in HS-models presents a considerable gnosiological ques-tion. In the chapter we present the more important results and the modern state of the non-constructability problem in the classical 1-HS, but these results, practically all, can be gene-ralized on the case of d-dimensionality (d>1). Above all, for the purpose of exhaustive inves-tigation of the problem in item 2.1 of the chapter we introduce four classes of the NCF and establish general interconnections between those concepts of nonconstructability.

Definition 1. Configuration cbC(A,d,B) of the finite d-dimensional B-hypercube (block) of automata in d-HS is nonconstructible CF (NCF) iff there does not exist CF cC(A,d) such that cbc(n)(d 1).

Definition 2. Configuration Bs of the finite d-dimensional hypercube of automata in d-HS is nonconstructible with respect to some S-set (НКФs) iff there does not exist CF c`SC(A,d) such that c`(n) (d 1).

Definition 3. A finite CF c=cbC(A=,) is nonconstructible of the type NCF-3 iff the block CF cb of d-dimensional hypercube of automata in d-HS is constructible but CF c is nonconstructible.

Definition 4. Configuration cC(A,d,) is nonconstructible of the type NCF-1 for classical d-HS iff (c`C(A,d,))(c`(n)=c) and (с*C(A,d,))(c*(n)c). Configu-ration cC(A,d,) is nonconstructible of the type NCF-2 for a d-HS iff (c`C(A,d,)) (c`(n)=c) and (с*C(A,d,))(c*(n)c).

The diagram illustrates interconnections of the above typies of nonconstructability.

Theorem 1. Any classical 1-HS has at least one type of nonconstructabi-lity NCF (and possibly, NCF-3), NCF-1 and NCF-2. Nonempty sets of NCF, NCF-1, NCF-2 and NCF-3 for classical HS-models are infinite. Each GTF (n) of classical 1-HS can possess the typies of nonconstructability according to the table 1.

Table 1

In the table 1 sign "+(-)" identifies the existence (absence) the corresponding ty-pe of nonconstructability in the classical 1-HS, defining the admitted combinations of typies.

Theorem 2. For any GTF (n) for the classical 1-HS take place the follo-wing correlations NCFC(A,),NCF-1C(A,) and NCFNCF-1NCF-2NCF-3 C(A,). There exists GTF for which is admitted the correlation NCF-2=C(A,).

Relative to the problem of nonconstructability the question about quotes of the classi-cal HS posessed by NCF of the different typies presents undoubted interest. With the aid of the interesting approaches we deduced a number of correlations.

Theorem 3. Let N(a,n) be the number of all classical 1-HS; N1(a,n),N2(a,n), N3(a,n) and N4(a,n) be number of the such structures, which accordingly pos-sess not NCF, posess NCF-1 without NCF, possess NCF-2 without NCF-3. Then ta-ke place the following correlations:

In our opinion, it should be paid much attention to the concept of nonconstructability with respect to certain sets of configurations in the classical HS in view of a number of the interesting interpretations in theoretical and applied aspects, as well.

Definition 5. Configuration cC(A,d) is nonconstructible with respect to the set of CFs BC(A,d) and GTF (n) of the classical d-HS iff (c`B)(c`(n)c).

Theorem 4. If GTF in the classical 1-HS possesses not NCF, then it pos-sesses not and NCF-3; with respect to the set B=C(A)\C such GTF possesses NCF-1 or/and NCF-3, and can possess NCF-2 or/and NCF-3 and NCF-3, if C-set be strong subset accordingly of sets C(A,), C(A,) and CC(A,), CC(A,). If GTF in the classical 1-HS possesses not NCF, then with respect to sets B=C(A)\C(A,) and B=C(A)\C(A,) such GTF has accordingly each CF cC(A,) as NCF-2 and nonconstructability of typies NCF-1 and/or NCF-3.

A number of similar results in this direction can be found in our monographs [12,23]. In the item 2.2 a number of criteria of the existence in the classical HS-models of the above typies of nonconstructability are presented. The first criterion is due to Moore and Myhill and is based on the concept of the mutually erasable CF (MEC).

Definition 6. Two CF c1,c2C(A,) (c1c2) form for GTF (n) in the classical d-HS a pair of the MEC iff c1(n)=c2(n).

Definition of the MEC formulated by Moore is equivalent to above one and can be fo-rmulated as follows.

Definition 7. Let W be some block of m adjacent individual automata of the clas-sical 1-HS and B be the set of all neighbouring automata for B-block according to the X-nei-ghbourhood index X={0,1,2,...,n-1}. Let CF(P) be arbitrary CF of the finite Р-block of the individual automata of the structure. Two block CF CF1(W)CF(B), CF2(W)CF(B) are called a pair of MEC for GTF (n) in the classical 1-HS iff take place the following cor-relations [CF1(W)CF(B)](n)=[CF2(W)CF(B)](n) and CF1(W)CF2(W); W-block is called the internal block (IB) of the pair MEC (IB MEC).

This definition is due to Moore and it is very useful for receiving of some numerical characteristics of HS; on the basis of the definition Moore and Myhiil proved the following criterion of the existence for classical d-HS the nonconstructible configurations.

Theorem 5. The existence of MEC is necessary and sufficient for the existence of NCF in the classical d-HS.

In connection with the study of the nonconstructability in the classical d-HS we con-sidered a number of problems of existence of MEC in HS, detailly. The obtained results have qualitative and numerical character, as well. In this direction we have the following theorems.

Theorem 6. There exists the classical binary 1-HS with Moore neighbo-urhood index, which has pairs of the MEC with simple IB of size L of one of the following types, only:

1) L={p+|p1}; 2) L={1+,2+,3+,p-|p4}; 3) L={1-,p+|p2}

4) L={1+,2p-,(2p+1)+|p1}; 5) L={1-,2+,p-|p3}; 6) L={1+,p-|p2}

where sign {+|-} shows that 1-HS has {has not} pairs of the MEC with simp-le IB of size L (simple IB contains not other MEC).

Theorem 7. For any integers a3 and n2 there exists a classical 1-HS with alphabet A={0,1,...,a-1} and neighbourhood index X={0,1,...,n-1}, which has pairs of the MEC with simple IB of minimal size L=n.

The results of theorems 6-7 were obtained using methods of computer modelling.

Theorem 8. If classical 1-HS has pairs of the MEC with simple IB of mi-nimal size L, then takes place correlation n L <an-1(an-1-1)+n-2.

Theorem 9. Minimal size (L) of the NCF in the classical 1-HS is defined by the following correlation: (n+1) L < 2a(n-1).

Problem existence for classical d-HS so-called vanishing CF is very interesting with point of view of HS-dynamics, including nonconstructability problem.

Definition 8. A finite CF cC(A,) is vanishing (VCF) for the classical d-HS iff (m>0)(c(n)m=), where and (n) - are null CF and GTF of the structure accordingly.

The following theorem summarizes a number of results connected with VCF-existence.

Theorem 10. If for the classical 1-HS there exists VCF, then the struc- ture posesses the nonconstructability of NCF-type. The minimal length L(a,n) of the VCF in the classical 1-HS is determined by the following correlation: n-1 L(a,n) <an+n-1. There exists classical 1-HS with the simplest neighbourhood in-dex X={0,1}, which posesses the VCF of the minimal size L(a,2)=a-1.

Now we state the new criterion of the existence of NCF in the classical 1-HS, which is known to be generalized for higher dimensionality and which depends no of the concept of erasability in HS-models. The criterion is based on the concept of -configurations (-CF).

Definition 9. In addition to suppositions and designations of the definition 7, let P(W) be number of individual automata in arbitrary W-block of classical 1-HS. For classical 1-HS there exists -CF of W-block iff at least for one CF(W) there exist G()an-1 con-figurations-predecessors such that [CF(W)CF(B)](n)=CF(W),where B - block of au-tomata in the structure, which are adjacent to all automata of W-block according to neighbo-urhood index and GTF.

Our definition of -CF is slightly different from Maruora-Kimura`s definition of so-called k-balanced GTF, but it is easy to see that they are equivalent. In view of definition 9 the fol-lowing theorem can be proved.

Theorem 11. The classical 1-HS posesses the nonconstructability of NCF-type iff for the structure there exist -CF.

Theorem 11 gives another criterion of the existence of NCF in the classical HS-models and it is more convenient for theoretical investigations of HS-models. The criterion allows to receive more acceptable estimations for some numerical characteristics of HS-models.

Theorem 12. If for the classical 1-HS there exist -CF of the length B, then for the structure there exist NCF of the length

where: n - is size of neighbourhood template of the structure, G() - correspond to the definition 9 and ]Z[ - denotes integer Z.

In a number of cases instead of optimum estimation of NCF size it is enough to have a simple formula as a function of the general parameters of HS-models. In this direction the following theorem takes place.

Theorem 13. If for the classical 1-HS with Moore neighbourhood index X={-1,0,1} there exist -CF of length B, then for the structure there exist NCF of minimal L-length according to the correlation: B L 2(B+n-1)(n-1)an-1]Ln a[.

The theorem gives estimations for minimal size of NCF in the classical 1-HS as func-tion of general parameters: sizes of -CF and template, and the cardinality of state alphabet of 1-HS, only. These results can be useful for the theoretical and numerical investigations in HS problems, as well. Furthermore, the results can be easily spreaded on HS-models of hig-her dimensionality with arbitrary neighbourhood index.

The method of NCF and NCF-1 is a very powerful tool in analysis of HS-models. The effectiveness of this approach depends very much upon the quantitative knowledge of gene-ral correlations between MEC,NCF,NCF-1 and -CF on the level of local functions and glo-bal functions as well. At present, full knowledge of this topic does not exist. We present some special results in this direction.

Theorem 14. Let (n)=(m)(p) be decomposition of GTF (n) on two functi-ons (m), (p) of the same 1-dimensionality and defined in the same А-alphabet. If GTF (m) has not MEC and (p) has D-set of -CF, then GTF (n) has the same D-set of -CF. If GTF (m) has not MEC and (p) has MEC, then GTF (n) has the same set of NCF that GTF (n). There exists GTF which has MEC with limited size of minimal simple IB and NCF of any earlier given minimal size. There exists GTF, for which any pair of MEC contains NCF. Let GTF (n) has a M-set of pairs MEC. Then GTF (n)m (m>1) has identical with function (n) М-set of MEC iff at least one CF of each pair MEC of М is NCF for GTF (n). In opposite case (k1)(MkMk+1), where Mk - set of all pairs of MEC for GTF (n)k (k1).

Theorem 14 takes place for general HS-models and in view of it, it can be easily seen that there exists function (n) with the different sets of MEC and the same sets of NCF. In connection with the result we have the following interesting theorem.

Theorem 15. For each integer n2 there exists classical 1-HS, for which minimal block (B) sizes of MEC and NCF are linked the following correlations B(MEC)/B(NCF)=n or B(MEC)/B(NCF)=1/(n+1) for minimal B(-CF)=1, accordi-ngly. For each integer n 2 there exists GTF (n) of the classical 1-HS, which posesses no NCF and NCF-3, but which has NCF-1 of minimal size L n-1. For each integer n 3 there exists GTF (n) of the classical binary 1-HS, which po-sesses -CF of minimal size L = n and IB MEC of minimal size L=1.

Now we shall consider similar questions for the other concepts of nonconstructability in the classical HS-models (NCF-1,NCF-2 and NCF-3), which accordingly to theorem 1 can combines in very wide limits. From definitions 1-4 and theorem 1 it can be easily seen that CF cC(A,d,) cannot be NCF,NCF-1,NCF-2 and NCF-3 simultaneously. Consequently, the intersections any pairs of nonconstructible CF of above typies for any GTF is an empty sets. The following theorem gives a criterion of the existence of NCF-1 (NCF-2) for classical HS-models without NCF and NCF-3.

Theorem 16. The set C(A,d,) is closed with respect to GTF (n) of the classical 1-HS, if (c`C(A,d,))(c`(n)C(A,d,)); in the opposite case the C(A,d,)-set is not closed. The classical d-HS, which has not NCF-3 and/or NCF, posesses NCF-1 (NCF-2) iff a set C(A,d,) is not closed (is closed) with respect to the global transition function.

In view of our supposition that null-CF C(A,d,) can be formulated the result of theorem 16 in other terms. In a number of cases the result presents the more comfortable criterion of existence of nonconstructability of typies NCF-1 and NCF-2 for the classical d-HS, which posesses not NCF and NCF-3.

Theorem 17. For the classical d-HS, which posesses not NCF and NCF-3, there exists NCF-1 (NCF-2) iff for its GTF (n), there exists (are absent) CF cC(A,d,) such, that с(n)=.

The theorem gives a more convenient criterion of the existence of NCF-1 and NCF-2 for the classical HS-models, which posesses not NCF and NCF-3. The concept of erasability is directly linked with the nonconstructability problem in the classical HS-models. For purpo-ses of the following generalization we introduced a new, more common concept of erasability in HS-models, and on the basis of such a generalization a number of interesting dynamic pro-perties of HS-models was discovered.

Definition 10. Two CF c1,c2C(A) (c1c2) form for GTF (n) of the classical d-HS a pair of MEC-1 iff for these CF takes place the correlation: c1(n) = c2(n) = сC(A,).

On the basis of the concept the essential generalization of the well-known Moore-My-hill criterion of the existence of NCF for the classical HS-models was given.

Theorem 18. The classical d-HS posesses typies of nonconstructability NCF (possibly NCF-3) and/or NCF-1 iff for the structure there exists pairs of MEC-1. If such structure posesses not MEC-1, then structure posesses NCF-1; inverse affirmation is wrong in the common case.

The concept of nonconstructability of type NCF-3 is the consequence of the differe-nce between configuration and block nonconstructability. The criterion of the existence of nonconstructability of type NCF-3 presents the following result.

Theorem 19. The configuration c=cb is for the classical 1-HS nonco-nstructible of type NCF-3 iff block CF cb for the structure is constructible and block CF c`b=0mcb0m (m an+n-1) is NCF.

Particular interest in due to the algorithmical aspect of the nonconstructability pro-blem, which is presented in item 2.3. The general results in this direction can be formulated as follows.

Theorem 20. With respect to the arbitrary block or finite CF the problem of determination of its type (constructible, NCF, NCF-1, NCF-2 or NCF-3) for the classical 1-HS is algorithmically solvable.

Theorem 21. The problem of the existence for classical 1-HS nonconst-ructability of typies NCF, NCF-1, NCF-2 and NCF-3 is algorithmically solvable. The problem of the existence for the classical 1-HS the combinations of noncon-structability typies accordingly to table 1 is algorithmically solvable.

In convenience with theorems 5 and 8 the problem of the existence pairs of MEC (and NCF) for the classical 1-HS is algorithmically solvable. The following theorem gives similar re-sult for the common case of MEC-1.

Theorem 22. The problem of the existence pair of MEC-1 for the classi-cal 1-HS is algorithmically solvable.

The properties of parallel maps defined by GTF of the classical HS-models play the fundamental role in the study of the theoretical properties of HS-models. Many scientists wo-rked in this direction and their results are well known. Our general results in this direction can be presented as follows.

Theorem 23. The problems of the determination of the mutual 1-1-corre-spondence of parallel global maps (n):C(A,) C(A,), (n):C(A,) C(A,) and (n):C(A) C(A) for the classical 1-HS are algorithmically solvable. The problem of the existence for parallel global map (n):C(A) C(A) the inverse parallel n-1-map for case of the classical 1-HS is algorithmically solvable.

In this connection the T. Yaku proved the following interesting result: The problem of the existence of the predecessors for arbitrary CF cC(A,d) in the classical d-HS (d>1) is algorithmically unsolvable. In the 1-dimensional case we have the opposite re-sult, which is based on the following theorem.

Theorem 24. The problem of the determination of c`-predecessors and their typies for the arbitrary CF cC(A,) in the classical 1-HS is algorithmi-cally solvable.

Presented in the chapter results solve the nonconstructability problem in the cla-ssical d-HS as a whole. More special results in this direction are numerous and allow to inve-stigate the nonconstructability problem in detail. Along with that, results in this direction allow to form rather effective methods for investigation of HS-models dynamics. A number of the similar results are discussed below; many interesting ones in this directions can be found in our monographs and papers [1-77].

The special questions linked with the nonconstructability problem are considered in the item 2.4. Closely connected to the Yamada-Amoroso Completeness problem is the prob-lem of existence of universal configurations (UCF) for the classical d-HS, which was for-mulated by S. Ulam for the case of regular lattice. It can be formulated as follows: for a gi-ven monogenic d-HS, does there exist finite configuraion (a finite set of configu-rations) from which the set C(A,d,) can be produced by the HS`s GTF?

Definition 11. The set of the CF ckC(A,) forms for GTF (n) of the classical d-HS the set of the universal configurations (UCF), if k<ck>[(n)]=C(A,) (k=1p).

Using the results in the nonconstructability problem, we have shown that this problem has a negative solution for any classical d-HS.

Theorem 25. For any classical d-HS (d 1) there is not a finite set of the universal configurations.

Theorem 25, to some degree, has something in common with introduced below the concept of complexity of the finite configurations in the classical d-HS. Furthermore, under certain conditions one has the following stronger result. This result allows to clear some pre-cise properties of the nonconstructability problem in the HS-models.

Theorem 26. If for the classical d-HS (d 1) without NCF there exists a G-set of NCF-1, then there is not finite set of configuration cjC(A,) such, that

On the basis of an algebraical approach and results in the nonconstructability problem we proved the more strong result, which essentially generalizes the above theorem.

Theorem 27. Let (n) be an arbitrary GTF of the classical d-HS with alp-habet A (a - prime), which posesses the GSA-set of NCF and, possibly, NCF-3 and/or NCF-1. Then, there not exist d-dimensional finite sets of configurati-ons cjC(A,d,) and GTF (nj) in alphabet А={0,1,2,3,...,a-1} such, that take place the following two correlations:

On condition that А-alphabet (а - composite) is used, takes place the above for-mulation of the result with the second correlation, only; analogous result take place for case of А-alphabet (а - prime) and nonconstructability of type NCF-2, i.e. GTF (n) posesses the GSA-set of NCF-2.

Structures with refractority d-HSR(r,P) present undoubted interest with many points of view. The general object in such HS-models is investigation of the dynamical distribution of individual automata in the excitation 1-states in conformity with the initial CF co, the neigh-bourhood index X and the depth r of refractority. We studied the most common properties of d-HSR(r,P) by means of both theoretical and computer modelling approaches.

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 GTF of the classical 1-HS from the some initial CF (axiom). 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 the well-known Lindenmay-er`s systems and can be used for linguistic description of many parallel discrete systems and processes. We investigated n-grammars in conformity with traditions of the FGT with respe-ct that a number of important characteristics of such class of parallel grammars was found and presented in our monographs [4,12], which contains the systematic exposition of the n-grammars theory. Furthermore, many results in the n-grammars were applied to the case of non-deterministic Tn-grammars. Thus, we proved that the families of L(n)- and L(Tn)-la-nguages 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 tradi-tional approach to working out of programming languages for homogeneous computer systems will not allow to create actually effective parallel software which might use the ma-ximal 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 mic-roprogramming languages of parallel microprogrammed computation structures and for des-cription of many kinds of cellular systems of the different purposes.

In contrast the nonconstructability, the study of the common properties, which reflect the maximal constructive possibilities of the classical HS-models, deserves great interest and a number of results in this direction are presented in the item 2.4. One of them can serve the so-called universal reproductability, i.e. each finite CF in the classical d-HS is self-re-producing in Moore`s sense. Moore`s definition captures the essence of reproductabili-ty and allows us to concentrate on it alone.

Definition 13. We will say, that a CF сC(A,,d) contains m copies (with an ac-curacy of rotation and shift of homogeneous space Zd) of the block cb-configuration, if there exist m disjoint subsets of the Zd, and each of these subsets contains at least a co-py of the block cb-CF. The finite CF сC(A,,d) is self-reproducing in Moore`s sense for the classical d-HS,if for any before given integer m>0 there exists integer t>0 such that CF с(n)t contains at least m copies of the initial c-configuration.

A number of scientists investigated this question and with the help of their efforts a class of linear classical d-HS was discovered. The local transition function of such stru-ctures can be characterized by the following algebraical function:

The class of the linear classical d-HS posesses the universal reproductability of the finite configurations in Moore`s sense. The following theorem summarizes the results of such scientists as: Waksman, Winograd, Ostrand, Cooper, Fredkin, Smith, Amoroso and others.

Theorem 28. For the linear classical HS-model any finite configuration cC(A,d,) is self-reproducing in the Moore`s sense.

Using the result of theorem 150 [12], we essentialy generalized the above result, na-mely: any classical d-HS (d 1) with the local transition function of the type

where a=pk (p -prime; m,k - positive integers; bj,xjA; j=1n), has all finite CF as a self-reproducing in Moore`s sense. It is necessary to note that the d-HS of such type is only one out of many known at the present time. Is there a class of such HS-models and can it be characterized? In this direction the following partial result can be presented.

Theorem 29. The linear classical 1-HS with alphabet А={0,1,2,3,...,a-1} (a - prime) form the isolated semigroup with respect to composition of their global transition functions.

A number of special results in this directions can be founded in our books [1,4,12,23]. The class of the classical HS-models with universal reproductability is attractive in many res-pects. Results in this direction allow to discover a number of useful correlations between the nonconstructability and the universal reproductability in the classical HS-models, and to solve a number of mathematical problems as shown, also in the item 2.4.

Theorem 30. The existence of nonconstructability of type NCF-1 without NCF and NCF-3 for the classical HS-model is necessery (is not sufficient) condi-tion in order for the model posesses the universal reproductability in Moore.

In the light of above results the following extremely interesting problem can be sol-ved: Can a classical d-HS double any finite CF? This problem has a negative solution.

Theorem 31. There not exists the classical d-HS doubled any finite CF.

On the basis of the theoretical and computer analysys of the classical 1-HS with sym-metrical LTF (GTF) we can formulate the following extremely interesting Hypothesis: Each classical 1-HS with the symmetrical GTF (n) (n 3), which has the NCF-1 with-out NCF (NCF-3), possesses the possibility of universal reproductability of the finite configurations.

A new class of the classical HS-models posessed to a considerable extent the repro-ductability of the finite CF, can be defined on the basis of special algebraical system [73] AS=<Aa;+;#>, where alphabet Aa={0,1,...,a-1} (a - composite), (+) - operation of addi-tion in (mod a) and (#) - operation of multiplication, which is defined by the table 2.

multiplication-table 2

On the basis of the above algebraic system AS can be defined the interesting class of 1-HS, whose local transition function are defined by the parallel transition rule of the type:

where #-multiplication is defined by the table 2. Let S(a,m) be the set of all finite configu-rations of type c=x1x2x3...xm for xkA\{0} (j=1m), and (a,m) be the set of all fi-nite configurations of length m. Consequently, the density (a,m)=S(a,m)/(a,m) has asymptotic behaviour defined by the following correlations:

Lim (a,m)=0 Lim (a,m)=1

m m

Lim (a,m) = Lim (a,m)=e-1/p , if Lim a/m=p=const

m a m,a

In such a manner, under certain circumstances the set S(a,m) of self-reproducing in Moore`s sense finite CF can serve as a characteristic of the so-called essential self-repro-ductability in the classical HS-models. In the item 2.4 the interesting discussion in the pro-blems is presented. Similar questions can be founded in our books [1,4,5,23,27].

In the third chapter of the book the problem of complexity of the finite configu-rations for HS-models is discussed. The complexity is one of the most intriguing and vague concepts of the modern science. We regard that intuitive essence forms the basis of such situation. The well-developed theory of computational complexity within computer scien-ce and the modern approaches to the estimation of the complexity of growing self-organizing cellular systems corroborate the above-said. At present, we know three approaches to the definition of complexity of the finite objects: combinatorial,probabilistic and algorith-mical. For the last case A.N. Kolmogorov defined the relative complexity of some finite object G (comparative to object S) by the minimum length of Turing machine`s program of deriving G from S. Our approach can also be called algorithmical but it essentially differs from Kolmogorov`s one. The essence of our concept of complexity consists in the estima-tion of complexity of generating arbitrary finite configuration from some primitive one by means of the finite number of global transition functions from some finite basis set Tf.

The our concept of complexity is based on two fundamental results. The first result due to Maruoka and Kimura (1974). That result characterizes the constructive possibilities of the polygenic HS-models and can be formulated as follows.

Theorem 33. Any non-null d-dimensional CF cC(A,d,) can be gene-rated from primitive CF cpC(A,d,) by means of some finite sequence of global transition functions of polygenic d-HS (d 1).

On the other hand, the second fundamental result we received at 1985 [61-65]. That result characterizes the dynamic properties of the classical monogenic HS-models and can be formulated as follows.

Theorem 34. For any finite А-alphabet there not exist the finite sets of d-dimensional CF ckC(A,d,) and GTF (nk)k defined in the same А-alphabet, such that takes place the following correlation:

Let Gf be the finite set of d-dimensional GTF, defined in A-alphabet, on the basis of which we can to generate any finite c-CF from some primitive CF cpC(A,d,) for the fini-te number of steps of polygenic d-HS, i.e. there exist the following derivative rules:

where mk denotes mk-tuple application of GTF kGf (k=1n). In this case it is said, that CF cC(A,d,) is generated from primitive CF cpC(A,d,) at least for N=kmk steps of GTF kGf (k=1n). We shall say that two global transition functions i,jGf are diffe-rent (I j) iff (cC(A,d))(ci cj). If in derivative sequence (20) there exist (n-1) pairs <i,j> (j=1n-1) of the different GTF, then we shall say that in generation of c-CF from primitive CF cp there exist (n-1) levels Lk, which are defined by the following function:

The following figure splendidly illustrates the process of generation c-CF from primitive CF cp:

Lk-levels (с)

n-1 cn-1 c

n-2 A B

. .

. .

. .

. .

. .

4 c4 .....

3 c3

2 c2

1 c1

1 2 3 4 ...... n-1 n T

0 cp m1 m2 m3 m4 ...... mn-1 mn

This figure can serve as a good illustration for many considerations linked with our co-ncept of complexity. Then, the complexity of the arbitrary CF cC(A,d,) can be defi-ned as follows.

Definition 14. The complexity (SL) of arbitrary configuration cC(A,d,) of HS-model (d 1) is calculated on the following formula:

where Pk is the k-th prime and mk are defined from the sequence (20).

On the basis of the definition a number of important properties of the finite configura-tions in the classical and polygenic HS-models were received. These properties are chara-cterized with respect to the introduced concept (21) of complexity [4,12,23,27,50,57,58,61]. The following theorem presents a number of results in this direction.

Theorem 35. For any integer d 1 the set of all d-dimensional finite CF contains configurations of any earlier given complexity with respect to arbitrary finite basis Gf-set of d-dimensional GTF, defined in some finite А-alphabet of the classical HS-model.

A number of more special results in this direction and the interesting consequences can be found in our works [4,6,24,27,61]. On the basis of theorem 35 and a number of other our results in this direction the result, which has exteremy inportant role both for investigation of the dynamic properties of the classical HS-models and for the further development of co-mplexity concept of the finite CF, can be expressed by the following theorem.

Theorem 36. For any dimensionality d 1 there exists GTF Gf, which generates finite configurations of any earlier given complexity in the sense of definition 14 from CF cC(A,d,) of the limited complexity.

The result generates a number of interesting questions, one of which is question abo-ut number of configurations of the same complexity with respect to the given basis Gf-set. The following important result allows to clear this question.

Theorem 37. There exists infinite number of the basis Gf-sets of d-di-mensional GTF,defined in А-alphabet, comparatively each of which there exist infinite sets of the finite configurations of the same complexity.

In connection with the above defined concept of complexity an interesting question arises about the minimal basis Gf-set of the global transition functions. In the common ca-se the question is open, but for class of the binary GTF a number of interesting results in this direction are received.

Theorem 38. There exists the minimal basis Gf-set, which contains four 1-dimensional binary GTF,only; at least one GTF of the set posesses the noncon-structability of type NCF-1. With respect to the minimal basis Gf-set of 1-dime-nsional binary GTF there exist the infinite sets of the finite CF of the same complexity in the sense of definition 14.

The following result characterizes the constructive possibilities of the 1-dimensional binary GTF, which compose the minimal basis Gf-set.

Theorem 40. The minimal basis Gf-set contains four 1-dimensional bina-ry GTF, the corresponding LTF of which are defined by the parallel substitutions (21.ad); global transition functions of such Gf-set posess the typies of nonco-nstructability according to the table 3. The minimal basis Gf-set for the 1-dime-nsional non-binary case consists of GTF, which posess NCF and/or NCF-1, NCF-2 and, possibly, NCF-3.

Table 3

The result of the above theorem allowed to solve a number of problems of our mono-graphs [4] and can be used for investigation complexity problem in the 1-dimensional case with arbitrary A-alphabet. On the basis of the theorem can be presented the more simple su-bstantiation for the introduced concept of complexity in the 1-dimensional binary case. The result of such substantiation can be formulated by means of the following theorem.

Theorem 41. Any 1-dimensional binary CF cC(B,) is monotonously ge-nerated from the primitive CF cp=1 by means of GTF of some fixed finite GS-set. At the same time, there not exist the finite system of pairs {ck,(nk)jk} su-ch, that take place the following correlation:

The set GS of the binary global transition functions can be choosen as a Gf-set, comparatively to which the concept of complexity of 1-dimensional binary finite configurations is defined.

The above theorem allows the generalization on the case of arbitrary A-alphabet and more common typies of the finite systems of pairs {ck,(nk)jk}.

On the basis of the introduced concept of complexity A(X) of the finite configurations we presented solutions of a number of problems in the HS theory. The relation between A(X) and other known measures of complexity is presented. From our results in this direction, in particular, follows that the classical HS-models are not the finite axiomatized formal systems, i.e. it is impossible to define a finite set of the finite CF (axiom) from which the set C(A,d,) of all finite CF in the classical HS-model can be drawn. In the C(A,d,)-set the infinite hie-rarchy of complexity can be established. A number of presented results in the complexity problem of the finite CF in the classical HS-models allows to identify some profound distinc-tions between parallel and sequential formal information processing models.

In the fourth chapter is discussed the problem of modelling which plays a very im-portant role in the HS theory itself and in its numerous applications. General aspects of this problems are linked with modelling of one HS by another: real-time modelling, modelling with suppression of certain properties of modelled HS, simplification of characteristics of modelled HS and optimal modelling. We made an attempt to obtain the optimum modelling technique. In connection with that the concept of T-modelling was introduced which turned out to be very suitable also for many applications of the HS theory. On the basis of the introduced con-cept we carried out a detailed study of the multi-aspect problem of modelling for the clas-sical d-HS. In the chapter a number of algorithms and principles of self-recovering in 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-modelling a sufficiently wide class of theoretical problems was investigated such as: universal computability and parallel algorithms, classes of paralleling, reversibility of modelling 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 modelling of various sorts of parallel discrete processes, algorithms and phenomena.

A number of scientists has dealt with the problem of modelling of one classical d-HS by another, of which works of H.Yamada,S, Amoroso,E. Codd,H. Nishio,A.R. Smith, T. Toffoli,E. Banks,J. Batler,A.S. Podkolzin,V.Z. Aladjev and some others can be commended. Enough detailed discussion of general results in the problems can be founded in our books [1,4,12,23]. In the item 4.1 of the chapter our concepts of modelling in the cla-ssical d-HS are introduced and some related results are presented.

We introduce to this end the concept of 1-modelling of one d-HS by another d-HS, definition of which can be illustrated by the following diagram. The diagram enough lucidly illustrates the principle of modelling of arbitrary classical d-HS by other one of the same type.

с*o GS-Coder co

*

с*1o GS-1-Decoder c1o

In the modelled d-HS any CF coC(a,d,) defined in the A-alphabet is transferred into next CF co=c`o by means of the GTF . Let GS() be a some recursive method of co-ding of symbols A and GS-1() be the recursive decoding method of a set of -symbols from A*-alphabet; let GS[x] and GS-1[y] be the recursive coding and decoding of con-figurations x and y, respectively. Then for the second d-HS any CF c*o=GS[co] is transfer-red by the GTF * into the next CF c*1o for which GS-1[c*1o]=c`o. One says that one cla-ssical d-HS 1-models another HS of the same dimensionality if their dynamics satisfies the above-mentioned requirements. Let Tx be the length of the edge of an d-dimensional cube which contains the template of the modelled classical HS=<Zd,A,X,>. On the basis of the above suggestions we can formulate the following interesting result.

Theorem 43. For arbitrary classical d-HS=<Zd,A,(n),X> there exists the structure <Zd,A*,(m),X*>, which 1-models the first one; Tx,Tx*-templates and A,A*-alphabets of both structures are linked by the following correlations:

To our knowledge, this result is the best of its kind. In works [1,3,4,12] we considered some more special cases of modelling of one classical d-HS by another. Now we shall consi-der the algorithmical properties ot the classical d-HS. It is well known that the classical d-HS is parallel algorithm for rewritting of d-dimensional words defined in the finite A-alphabet. Because the study of d-HS in this regard is of great significance fo treating the behavioural properties of such structures and their numerous applications, we begin with a discussion of the concept "one algorithmT-models (slightly T-models) another algorithm".

Let M1 be an algorithm whose alphabet is A, and M2 be an algorithm whose alphabet is A* (AA*). Let Mk1s=sk (Mo1s=s) be the result of the k-fold rewriting of words defined in A-alphabet by means of M1-algorithm. Then, for an arbitrary s-word defined in A-alphabet the M1-algorithm generates the following sequence of the finite words:

Mo1s, M11s, M21s, ..., Mk1s, ... (23)

Let s* be arbitrary finite word defined in A*-alphabet (which in A-alphabet is equal to s-word) and M2-algorithm generates a sequence of the words from the initial s*-word of the type:

Mo2s*, M12s*, M22s*, ..., Mk2s*, ... (24)

Definition 15. We say, that М2-algorithm Т-models М1-algorithm, if there exists some recursive GS-procedure, which allows for any s-word defined in A-alphabet to evolve from word sequence (24) the subsequence of the following type:

Moos*, Mj12s*, Mj22s*, Mj32s*,..., Mjk2s*, ...

such that in А-alphabet takes place the correlation (kN)(Mjk2s* Mk1s) and jk=T+k. If value jk depends on the length of the rewritten s-words {jk=F(|S|)} in the modelled M2-al-gorithm, then we say that M2-algorithm slightly T-models the starting M1-algorithm.

In the item 4.2 of the chapter we present some of our results on the T-modelling of known successive algorithms for the rewriting of finite words in the finite alphabets by the cla-ssical 1-HS. Let a Turing machine (MTsq) has a symbols on the tape and q internal states.

Theorem 44. For an arbitrary MTsq there exists the classical 1-HS with А-alphabet of cardinality a=s+q+9 and Moore neighboorhood index X={-1,0,1}, which 8-models it. For an arbitrary MTsq there exists the classical 1-HS with А-alphabet of cardinality a=s+q and neighboorhood index X={-2,-1,0,1,2}, whi-ch 1-models it.

As consequences of the theorem we have a number of interesting results on the algo-rithmic unsolvability of some problems concerning the dynamics of the finite CF in d-HS.

Definition 16. The finite configuration coC(A,) for global transition function (n) of the classical d-HS is said to be accordingly:

limited, if (p)(k)(ck<co>[(n)] D(ck) p), where D - minimal diameter of block of the homogeneous space ot the structure, which contains ck-configuration;

(k-m)-periodical, if (m)(k)(co(n)m=co(n)k) (m 0; k-m1); periodical, if (k1)(co(n)k=co), and passive for k=1;

vanishing, if (m)(co(n)m=), where - null configuration of structure.

On the basis of the above definition we can formulate the following important result.

Theorem 45. In general the following problems concerning the dynamics of the finite configurations in the classical d-HS are unsolvable:

- the problem of recursivity of the set of configurations <co>[(n)];

- the problem of limitation of arbitrary configuration coC(A,d,);

- the problem of (k-m)-periodicity or periodicity of arbitrary co-CF;

- the problem of the existence of passive and/or vanishing configurati- ons for the arbitrary set <co>[(n)].

We used above special simulation technique called T-modelling (slightly T-mode-lling) for modelling a number of known algorithms for rewriting finite words defined in the fi-nite alphabets (such algorithms as: TAG- and LAG-systems,Markov`s normal algorith-ms,Post`s production systems,SS-machines,Buchi`s regular systems, and so on) by means of the classical 1-HS, and vice versa. In particular, on the basis of T-modelling of SS-machine by means of the classical 1-HS the following important result can be received: There exists the classical 1-HS with Moore`s neighbourhood index, which has a creative set of all vanishing finite configurations. At last, a number of interesting re-sults linked with T-modelling of Turing machines with k-heads and heterogeneous periodi-cally defined transformations by means of the classical 1-HS are discussed.

In the item 4.3 of the chapter a number of general results linked with the T-model-ling of the classical d-HS by means of HS of the same class are presented. A number of scientists have dealt with the problem, but it is necessary to note that neither the neighbo-urhood nor the state-set reduction techniques are necessarily optimum, and here we made an attempt to obtain the optimum technique along these lines. On the basis of our approaches we can formulate a number of the following interesting results.

Theorem 46. An arbitrary classical d-HS (d>1) is 1-modelled by a binary structure of the same dimensionality with template of size

where p1xp2x ... xpd - size of the minimal d-dimensional parallelepiped, which contains the template of the modelled d-HS, under conditions the following de-terminable correlation: Log2Log2 4(a-1) d is executed.

Theorem 47. Any classical 1-HS with alphabet A={0,1,...,a-1} and tem-plate of n-size is 1-modelled by the binary classical 1-HS with template of size L=(n+1)[Log2 a + n + ], where =4 for a 219 and =5, otherwise.

Theorem 48. An arbitrary classical 1-HS with A-alphabet (а 6) and tem-plate of n-size 1-modelled by the binary classical 1-HS with template of size L=n[2Log2 (a+2)+1]-2. An arbitrary classical 1-HS with A-alphabet for 4 а 21 and template of n-size is 1-modelled by means of the classical 1-HS with alpha-bet A*={0,1,2} and template of size L=6n-1. An arbitrary classical 1-HS with A-alphabet (5 а 14) and template of n-size is 1-modelled by the classical 1-HS with alphabet A*={0,1,2,3} and template of size L=5n-2.

In connection with the definition of universal computability of the classical HS by means of T-modelling of the universal Turing machine (UMT) a question arises about mi-nimum complexity of HS which can T-model the UMT. For estimation of the complexity of a HS, the product axn can be introduced, where a is cardinality of A-alphabet and n is the size of HS template. Establishing the minimum product axn is a problem which is, in our opinion, as difficult as finding the minimum product sxq for the universal MTsq. The smallest re-sult for product axn is a 1-dimensional universal HS (1-UHS) was given by A.R. Smith, who has found the following 1-UHS: axn=2x40, 3x18, 6x7, 8x5, 9x4, 12x3 and 14x2. Notice the existence of the classical 1-UHS with template of minimal size n=2. On the basis of the above-mentioned Smith`s results and our result (theorem 48) for the minimal product axn for the classical 1-UHS the following estimations were established: axn=2x16,3x11 and 4x8. The result of theorem 48 can be generalized on the higher dimensionality.

Theorem 49. Any classical d-HS (d 1) with A-alphabet and template, co-ntained in the minimal d-dimensional parallelepiped p1xp2x ... xpd, is 1-model-led by means of the binary classical d-HS with the template of size

In the item 4.4 of the chapter a number of special questions of modelling in the clas-sical d-HS is presented. Above all, the following result characterizes the possibilities of mode-lling of an arbitrary non-deterministic 1-HS by means of the classical 1-HS.

Theorem 50. Any non-deterministic structure SH(1,a,n,N) is modelled by the corresponding classical 1-HS with Moore`s neighbourhood index and A*-alphabet of cardinality N(an+1-1)/(a-1)+a+n.

In our monograph [4] we quite justly noted constructive defects of the classical d-HS with symmetrical local transition functions. On the other hand, from our results in modelling in the classical d-HS it may be drawn that HS with symmetrical and asymmetrical local transition functions are equivalent with respect to constructability.

Theorem 51. If any MTsq realizes some S-algorithm in T-time, then there exists the classical 1-HS with A-alphabet of cardinality 2(s+2q+1), Moore`s nei-ghbourhood index and symmetrical GTF, which models the same S-algorithm in time 4T.

On the basis of this result the following interesting theorem can be formulated [42].

Theorem 52. For an arbitrary classical 1-HS with Moore`s neighbourhood index there exists the structure of the same dimensionality and neighbourhood index, A*-alphabet of cardinality 2(4a2+5a+12) and the symmetrical GTF, which models the first one in 4L-time, where L is length of the processed finite CF in the modelled structure.

In connection with a number of problems the classical d-HS with symmetrical LTF (GTF) present definite interest. The symmetrical LTF is defined by parallel transition rules of the type: x1x2 ... xn x`1 and (x1x2 ... xn)R x`1, where XR is symmetrical inversion of X-string. Using above theorem, we can easily verify that by means of symmetrical GTF it is possible to computer any partially recursive function, but on a constructive plane symmetrical HS-models are less powerful, far and by, than asymmetrical ones. Thus, if for modelling of a number of processes in the classical HS (especially asymmetrical ones) the asymmetrical LTF are most suitable, than for concrete realizations of HS-models, for instance, by means of microelectronics or for more fir interpretations of HS the symmetrical LTF are more suitable. The class of symmetrical GTF presents special interest with many points of view. The follow-ing result can be useful for many interesting considerations.

Theorem 53. Any classical 1-HS with symmetrical GTF and neighbourhood index X={0,1} possesses the nonconstructability of typies NCF and/or NCF-1.

In connection with problems of universality and modelling in the classical HS the reversibility problem presents the undoubted interest. The enough detailed discussion of the problems is presented in the item and monograph [12]. The classical d-HS is reversib-le iff it possesses not the nonconstructability of typies NCF,NCF-1 and NCF-3. In the item is presented discussion of such definition of reversibility for the classical d-HS. The rever-sibility problem generates a number of the interesting attendant questions. In the common case, the problems is characterized by the question about possibility to model an arbitrary classisal HS by means of structure of the same class, but without the given properties of the modelled structure. With respect to the nonconstructability of typies NCF-1 and NCF-2 we have the following general result [12].

Theorem 54. The arbitrary classical d-HS is Т-modelled by d-HS (d 1) of the same class, which possesses not NCF-1 and/or NCF-2.

For case of the nonconstructability of NCF-type the question is more difficult. To this effect we introduced two concepts of modelling: WM- and W-modelling in the classical d-HS, which embrace a wide class of methods of modelling. On the basis of investigations of the above concepts of modelling we can formulate the following results.

Theorem 55. The arbitrary classical d-HS (d 1) cannot be WM-model-led by reversible structure of the same class and dimensionality.

Theorem 56. The arbitrary classical d-HS (d 1) cannot be W-modelled by reversible structure of the same class and dimensionality.

Linked with modelling in the HS is the reliability problem, which plays a very impor-tant role in practical realizations of computation HS-models. We presented [12,42] a number of algorithms and principles of self-recovering in real HS, which can be useful for practi-cal constructing in the homogeneous computation structures on the basis of HS-models.

In the item 4.5 of the chapter the parallel algorithms defined by the classical d-HS (abbreviated d-PADHS) are discussed. The d-PADHS play a considerable role in describing some biological processes and programming systems based on computational homogeneous structures, as well as for the theory of algorithms, as such. Here we will consider parallel algo-rithms defined by the classical HS-models with point of view of some of their possibilities.

We present some results on the complexity of 1-PADHS: complexity in Markov-Nago-rnyi`s sense and computational complexity. The 1-PADHS are defined as follows.

By definition, 1-PADHS(a,n) operates on string of symbols (configurations of C(A,)-set or words) defined in А-alphabet. The mode of operation is described by the GTF (n) of some classical 1-HS, defined by LTF with parallel transition rule of the following type:

n

For every word cC(A,) the parallel algorithm 1-PADHS(a,n) defines the sequen-ce of words <c>[(n)], in which word ck is called final, if take place the following correla-tion: ck-1=ck-1(n)=ck. Let C(A,) be the word set which are processed by the algorithm 1-PADHS(a,n), and F be the partial word function in А-alphabet, if for some finite word cj C(A,) takes place the correlation F(cj)=c*jC(A,). Let then F be a word function whose domains of the existence and value are EF and VF, respectively. We will say that the word F-function, defined in A*-alphabet, is PADHS-computable, if there exists a parallel algorit-hm 1-PADHS(a,n) in alphabet A={b}A* (bA*) such, that for any c*oC(A*,), if co is a representation of word c*o of the form: c*o=bp+201b20p+1c*obp+2, then carry out two following general conditions:

1) if word c*o belongs to EF-domain of the existence of F-function, then the sequ-ence <co>[(n)] contains a passive CF - the final cf- word of the following form:

2) if word c*o belongs not to EF-domain of the existence of F-function, then the sequence <co>[(n)] does not contain a passive final cf-word of the form (28).

It then can be proved that a word F-function is PADHS-computable iff it is Turing-computable. The equivalence of such precise formalizations of the intuitive notion of a co-mputable function is one of the strongest arguments in favour of Church`s thesis. The prob-lem of estimation of complexity of parallel algorithm 1-PADHS is extremely important and in this direction we have the following interesting result [39].

Theorem 57. Any partial recursive word F-function, defined in some finite A*-alphabet, is PADHS-computable in the extended alphabet A={b}A*(bA*).

Consequently, the parallel algorithms 1-PADHS are equivalent to Markov normal algo-rithms in Markov-Nagornyi`s sense. At the same place, we discussed the concept of comple-xity of the 1-PADHS, in detail, and the concept of parallelism of such class of algorithms. We defined a class of algorithms which was called locally realizable algorithms (LRA). The essence of LRA consists in the possibility to present an algorithm by means of local identical algorithms above separate subwords of any processed word. Typical example of such algori-thm is the symbolic sorting. In our opinion, LRA can be realized by means of the parallel d-PADHS. For such algorithms the linear time realization in HS-models is allowed. For ins-tance, the problems of symbolic sorting and reverse map of words are realized by the 1-PADHS in the linear time. At present, the question of the advantage of parallel algorithms is often discussed. To this question the following theorem is related [3].

Theorem 58. If parallel algorithm 1-PADHS(a,n) computes some partial recursive word F-function in Т steps, then suitable Turing machine can com-pute the same F-function in T` {(n+1)T2+(n-1)T}/2 steps.

The possibility of parallelibility permitted by 1-PADHS can be tracked up on the follo-wing example. It is well known that two-way pushdown machine (TWPM) is equivalent to one-head Turing machine with time of work no more than Xk|X|, where X is the length of in-put word X and k - constant. Characterization of the TWPM in terms of the parallel algorith-ms gives much better result as regards time [3].

Theorem 59. If TWPM admits some set of the finite words in Т steps, then the corresponding parallel algorithm 1-PADHS can admit the same word set in no more than 2Т2 steps.

Thus, by means of parallel algorithms 1-PADHS for a number of sequential algorithms we can obtain much better results as regards time than by MTsq. It is appropriate to note that parallelism intrinsic in the 1-PADHS was used only for modelling of one algorithm by another and it did not use the parallelism intrinsic in the essence of the modelled algorithms itself. The so-called bc-automata present the undoubted interest for the theory of structural programming. In connection with the sequential bc-model the following interesting result can be presented [3].

Theorem 60. If some bc-automat expends Т steps for processing of so-me input finite word, then the corresponding parallel algorithm 1-PADHS can carry out the same work in no more than 2(Т+1)2 steps.

It will be noted, that the estimation appearing in this theorem is overstated, in general. Thus, affecting the essence of computability parallelism allows us to considerably save time, generally speaking. Such saving of time we can obtain only at the price of increase of some computational resources of the classical HS-models.

In the fifth chapter our results on the global decomposition problem (GDP) of GTF in HS-models are presented. The GDP in HS-models immediatly adjoints the above problem of the complexity A(X). Furthermore, the problem directly concerns the question of const-ructive complexity of HS-models, which plays an important role both in concrete realizatio-ns of parallel computation systems on the basis of HS-models and for modelling in HS.

The GDP can be formulated as follows: Can any GTF of the classical d-HS be presented in the form of a composition of the finite number of more simple glo-bal functions? It is said that global function (n) in A-alphabet is more simple than global function (m) defined in the same A-alphabet if n<m. Such a problem is called the Compo-sition problem. The more formal definition of the GDP can be presented as follows.

Definition 17. The global decomposition problem of GTF (d-GDP) is formu-lated as follows: Can arbitrary GTF (n) be presented in the form of a composition of the finite number of more simple global functions of the same class, i.e.

where GTF (n),(nj) (j=1k) are defined in the same A-alphabet and have the same dime-nsionality that the initial global (n)-function.

On a level with the well-known GDP we present a number of results on the so-called general global decomposition problem (GLDP). The GLDP is the question whether or not any GTF can be presented in the form of a composition of the type (29) as which can be used arbitrary global functions (nj) (j=1k), with the exception of trivial cases. It is proved, the GDP and the GLDP are, in general, not equivalent. In the item 5.1 of the chapter the GDP for the some special global transition functions is discussed.

On the basis of Yamada-Amoroso`s results in completeness problem for polygenic HS-models and our results in nonconstructability problem for classical HS-models the ne-gative solution of the GDP is presented.

Theorem 61. For arbitrary A-alphabet there exists the infinite set of 1-dimensional GTF, for which the 1-GDP has negative solution.

For the class of 1-dimensional binary injective GTF we have the following result.

Theorem 62. In the class of all binary injective 1-dimensional GTF the 1-GDP has, in general, negative solution.

The GDP with respect to class of the linear GTF was considered. Such functions po-ssess the G-property of the universal reproductability. The GDP is considered with res-pect to the subclass, the functions of which are defined by the LTF of the following type:

Such set of GTF is denoted as M*(A,1,G), which can be presented as unification of two subsets M*1(A,1,G) and M*2(A,1,G) (for breivity M*1 and M*2) of GTF (n) (n 2) with connected and unconnected templates of size n, accordingly; i.e. M*(A,1,G)M*1 M*2 and M*1M*2=, where - an empty set. The global transition functions of these subsets are denoted as 1(n) and 2(n), accordingly. Under the suppositions takes place the following general result [42].

Theorem 63. The set M*(A,1,G) and its subset M*1 are not closed with respect to composition operation. Any GTF 1(n)M*1 cannot be presented in the form of composition of two more simple functions of the same M*1-subset.

Widening of GTF-set, admitted as elements of representation (29) for arbitrary fun-ction of set M*1, on M*2-set of functions allows to receive the positive solution of the 1-GDP for GTF of M*1-set.

Theorem 64. Any GTF 1(2k)M*1 can be presented in the form of compo-sition: 1(2k)=1(k)2(k+1)=2(k+1)1(k), where 1(k)M*1 and 2(k+1)M*2 with template X2={0,k} (k=2,3,4,...). Any GTF 1[p(2k+1)]M*1 can be presented in the form: 1[p(2k+1)]=1(p)2[p(2k+1)-2]=2[p(2k+1)-2]1(p), (p=3,5,7,9,...; k=1, 2,3,4,...). Any GTF 1(n)M*1 (under condition n=pxq) can be presented in the form: 1(n)=2(n-p+1)1(p)=2(n-q+1)1(q), where GTF 1(n) of M*2-set has the simmetrical template.

The following result reflects the situation for case of GTF 1(n)M*1 (n - prime).

Theorem 65. The GTF 1(n)M*1 can be presented as a composition of the finite number of more simple GTF of M*(A,1,G)-set iff when n is complete.

For case of GTF 2(n)M*2 takes place the quite different picture, namely [61].

Theorem 66. For arbitrary integer n 5 and A-alphabet there exist at least n-4 GTF 2(n)M*2, which can be presented as composition 2(n)=2(n-1)1(2).

For class of the structures with refractority [d-HSR(r,P)] we have the results [42].

Theorem 67. The GDP in the class of all structures d-HSR(r,P) (d 1) with refractority has negative solution.

Theorem 68. In the class B(r) of all 1-dimensional refractory GTF with depth of refractority r 1 any global transition function cannot be presented in the form of composition of the finite number of functions of the same B(r)-set; B(r) presents the set of the isolated refractory global transition functions with respect to composition operation.

In the item 5.2 some interesting approaches to investigation of the GDP are presen-ted. On the basis Shannon`s function and some results of the theory of boolean functions the following theorem can be presented [42].

Theorem 69. For any given finite basis Gf-set of 1-dimensional binary GTF there exists integer no > 0 such that for any integer n no there exists at least one binary GTF (nj), for which the 1-GDP has negative solution.

On the basis of the theory of a-valued logics the following results can be presented.

Theorem 70. The class L(a,0) of local transition functions (n) (n 2, a > 2) has not the finite basis.

On the basis of the result (similarly to binary case) can be received negative solution of the GDP for the common case [42].

Theorem 71. Among all d-dimensional GTF, defined in A-alphabet and having arbitrary template, there exists the infinity set of functions for which d-GDP (d 1) has negative solution.

Using the algebraic approaches, the interesting results on properties of L(a,d)-semi-group of the parallel global maps (n): C(A,d) C(A,d) are presented. The set of all such maps can be presented as unification of seven non-intersecting subsets, which respect to the consisting GTF possess the following characteristics:

G1: GTF possess the all typies of nonconstructability (NCF,NCF-1,NCF-2,NCF-3);

G2: GTF possess the nonconstructability of typies NCF (NCF-3) and NCF-1 without NCF-2;

G3: GTF possess the nonconstructability of typies NCF (NCF-3) and NCF-2 without NCF-1;

G4: GTF possess the nonconstructability of type NCF-2; the defined by GTF the pa- rallel global maps are not mutually one-valued;

G5: GTF possess the nonconstructability of type NCF-1, only;

G6: GTF possess the nonconstructability of type NCF (NCF-3), only;

G7G6: GTF possess the mutually one-valued parallel maps (n): C(A,d) C(A,d).

The sets Gk (k=16) with respect to composition operation form the non-commu-tative semigroups, and set G7 forms the group. Consequently, semigroup L(a,d) of all parallel maps (n): C(A,d) C(A,d) in d-HS can be presented as unification of the finite number of non-intersecting subsemigroups and a group, i.e. L(a,d)=kGk (k=17). Struc-tural analysis of subsemigroups Gj and G7-group allows to formulate the following general result on reprentation of the L(a,d)-semigroup.