COMPUTATIONS ON NONDETERMINISTIC CELLULAR AUTOMATA Y.I.Ozhigov 8 9 9 DepartmentofMathematics,MoscowState TechnologicalUniversity”Stankin”, 1 Vadkovsky per. 3a, 101472,Moscow, Russia n e-mail: [email protected] a J Abstract 6 1 The work is concerned with the trade-offs between the dimension and the time and space complexity of computations on nondeterministic cellular automata. We 1 assume that the space complexity is the diameter of area in space involved in v computation. 1 It is proved, that 0 0 1). EveryNCA ofdimensionr,computingapredicateP withtimecomplexity A 1 T(n)andspacecomplexityS(n)canbesimulatedbyr-dimensionalNCAwithtime 0 1 r and space complexity O(Tr+1Sr+1) and by r+1-dimensional NCA with time and 8 space complexity O(T1/2+S), where T and S are functions, constructible in time. 9 / 2) For any predicate P and integer r > 1 if is a fastest r-dimensional NCA s A computing P with time complexity T(n) and space complexity S(n) , then T = a g O(S). - 3). If T is time complexity of a fastest r-dimensional NCA computing predi- p r,P m cate P then T =O((T )1−r/(r+1)2), r+1,P r,P o c Tr−1,P =O((Tr,P)1+2/r). : v Similar problems for deterministic CA are discussed. i X r a TypesetbyAMS-TEX 1 2 Y.I.OZHIGOV 1.Introduction It is well known that nondeterministic computations are more powerful than deterministic ones. The interrelation between deterministic and nondeterministic time complexity of computations was established by S.Cook in the work [2] where heshowedtheexistanceofNP-completeproblems. However,itisstillunknowncan nondeterministiccomputationsbefulfilledonphysicaldevicesornot. Inthispaper we show how the complexity of computations on a nondeterministic device depend onitsdimension. Notethatthesimilarproblemfordeterministiccomputersisopen (look at the section 6). Cellularautomata(CA)provideaconvenientframeworkforstudiesonthisprob- lem. A cellular automaton is a dynamical system with local interactions operating indiscretespaceandtime, andsimultaneouslyCAmaybe usedasa generalmodel ofcomputationaldevice. CAwereintroducedbyS.Ulaminthework[7]andJ.von Neumann in the work [5] and since then various problems pertaining to CA were treated in a great many works (look, for example, at [1],[3],[6],[9],[11],[12]). Let r 1 be an integer, Zr be the space, ω be a finite alphabet for possible states of≥any cell ¯i Zr. Cellular automaton of dimension r in alphabet ω is a ∈ function of the form: :ω2r+1 ω . A −→ Acellularautomatondeterminesthe specialclassofevolutionsinZr sothatthe states of all cells ¯i Zr evolve synchronously in discrete time steps according to ∈ the states of their nearest neighbours. Itmustbe mentioned,thatamoregeneralapproachcanbe ofinterestforappli- cations, where the function depends on¯i or t. It is not our intention to regard A such possibilities here. A configurationis anensemble ofstates of allcells atsome instantof time. It is apparentthatanevolutionofCAisuniquelydeterminedbytheinitialconfiguration. Ifweconsideramultifunctioninsteadof ,weobtainthedefinitionofanonde- A terministic cellular automaton (NCA). Generally speaking, evolutions of NCA are not uniquely determined by initial configurations. A behaviour of NCA may be described by a state transition network (look at [4]). It is a graph, each of whose nodes represents some configuration. Directed arcs join the nodes to represent the transition between configurations. All nodes have out-degree one iff the cellular automaton is deterministic. Moreover, if the cellular automaton at hand is in fact nondeterministic and we consider the configurations in unlimited space Zr, then out-degrees of some nodes in the state transition network will be infinitely large. The difference between one and high dimensional CA has emerged from the solution of the predecessor existence problem (PEP) for CA. It is the problem of existence of a predecessor for the given configuration. S.Wolfram showedin article [8]thatPEPisdecidableforonedimensionalCA,andT.Takuinarticle[10]showed that PEP is undecidable for some CA of dimension r where r =2,3,.... The computationalequivalence ofCA andTuringMachines is awellknownfact (look at[2],[11]). The time complexity (n) andthe spacecomplexity (n) canbe T S defined routinely for any CA . A This brings up the question: given an arbitrary predicate , how does the min- P imal complexity of r dimensional CA, computing , depend on r? P More precisely, if some predicate is computable on CA of dimension r with P time complexity (n) > O(n) is it possible to compute substantially faster on CA of dimensionTr′ >r ? P COMPUTATIONS ON NONDETERMINISTIC CELLULAR AUTOMATA 3 This is called TCD-problem. This problem is open for CA. AdifferentsituationariseswithTCD-problemforNCA.Forexample,itisfound that if some predicate can be computed on NCA with time complexity T(n) = P O(nα) and space complexity O(nα/2) then the increase of dimension by one unit allows to compute in time O(nα/2). Moreover,given β >0, the time complexity P O(nβ) can be attained for the computation of such predicate if we increase the dimension of NCA to a suitable value. A similar result takes place also for faster increasing functions T(n). It means that multi-dimensional NCA will become the faster instrument for computation as the dimension increases. We proceed with the exact definitions. All constants are assumed to depend on the dimension r. 2. The main definitions and results Let ω = c ,...,c be an alphabet for possible states of cells. Let t takes the 0 k { } values from the set N= 0,1,... . { } An evolution in Zr is a function of the form a: N Zr ω. A configuration × −→ is a function of the form a(t) : Zr ω. Any evolution a may be displayed as a −→ sequence (1) a(0),a(1),... of configurations at the instants of time t = 0,1,..., where a(t)(¯i) = a(t,¯i). jth componenet of i Zr will be denoted by i . If ¯i = (i ,i ,...,i ) Zr, we shall j 1 2 r write a(t,i ,...,i∈) instead of a(t,¯i). ∈ 1 r The following notations are fixed for the cells¯i(j) comprising the neighborhood of the cell¯i: ¯i(0)=¯i, ¯i(1)=(i 1,i ,...,i ), 1 2 r − ¯i(2)=(i +1,i ,...,i ), 1 2 r ¯i(3)=(i ,i 1,i ,...,i ), 1 2 3 r − ¯i(4)=(i ,i +1,i ,...,i ), 1 2 3 r ... ¯i(2r)=(i ,i ,...,i +1). 1 2 r We put : a (t,¯i)=a(t,¯i(j)). j We’ll consider only such evolutions a that C : ¯i : ¯i > C a(t,¯i) = c , 0 ∃ ∀ k k therefore all configurations a(t) will be finite objects. Let l be a fixed computable one-to -one mapping l : N Zr such that r r −→ l (n) = O(n1/r). This function represents an embedding of one dimensional r k k space into r dimensional with the least norm l (n) . r Given an alphabet σ, the set of all wordskoverkσ is denoted by σ∗. If B = c c ...c ω∗, then the initial configuration corresponding to the word B is j1 j2 js ∈ defined by c if 0 l−1(¯i)=k s, a(0)(¯i)= jk ≤ r ≤ ( c0 otherwise, we denote this configuration by a(0). B 4 Y.I.OZHIGOV A nondeterministic cellular automaton of r dimensions is a function of the form : ω ω ω 2ω. A × ×···× −→ 2r+1 times | {z } Let ¯b ω2r+1, c (¯b). Any word of the form ¯b c is called a command of this auto∈maton. Th∈isAcommand is called trivial if (−¯b→) = c and ¯b has the form A { } (c,u ,...,u ). AsetGofcommandsof whichcontainsallnontrivialcommands 1 2r A is called a program of . The behaviour of is defined by its program. If ¯b ω2r+1 andA (¯b) consists of exaActly one element, then in fact has ∀ ∈ A A the form ω2r+1 ω, and we obtain the definition of a deterministic cellular −→ automaton. We assume that (c ,...,c ) = c . This letter c plays the role of blank, it is 0 0 0 0 A denoted by 0(ω). AnevolutionofNCA isasequenceaˆoftheform(1)where t=0,1,..., ¯i A ∀ ∀ ∈ Zr (2) a(t+1,¯i) (a (t,¯i),a (t,¯i),...a (t,¯i)). 0 1 2r ∈A It is obvious that in deterministic case a(t) depends on ,t,a(0), and in nonde- A terministic case, in addition, on the choice of elements (2). The set of all values of a function f is denoted by Imf. Letthealphabetω bedividedintotwononintersectingparts: ω =ω′ ω′′,where ω′ is the set of main letters, ω′′ is the set of auxiliary letters, and let∪E ω′′ be the set of end letters, where ck−1,ck E. We denote ω′∗ by Σ, ck by suc⊂c( ), E byE( ). Letforthe evolution(1)of∈NCA Im a(0) ω′ c . Letτ(aˆ)bAe the 0 A A ⊆ ∪{ } least value of t such that there exists one and only one letter c E Ima(t). This ∈ ∩ letter c is denoted by res(aˆ, ) andis calledthe resultof the operationof onthe A A initial configuration a(0) in evolution aˆ. A configuration aˆ is called a resulting τ(aˆ) configuration for a(0). In general terms, the result of the operation of is defined uniquely only in A the deterministic case. The set of all results in evolutions which begin with a(0) is denoted by [a(0)]. A A predicate P on the set Σ is an arbitrary subset of Σ. NCA computes a predicate P iff B Σ A ∀ ∈ succ( ) [a(0)], if B P, A ∈A B ∈ (succ( ) / [a(0)], if B / P. A ∈A B ∈ It’s obvious that such a predicate P is defined uniquely for if it exists. We denote this predicate by PA. A cell ¯i Zr is called accessiblAe in evolution aˆ iff t′ τ(aˆ): a(t′,¯i)=c . ∈ 0 ∃ ≤ 6 The diameter of the set of all accessible cells is denoted by D(aˆ). Given B P, the least value of τ(aˆ) from all evolutions aˆ , where a(0) = ∈ (0) aB , res(aˆ,A)=succ(A) is denoted by τA(B). Let DA(B) denotes the least value of D(aˆ) from all evolutions aˆ where a(0) = a(B0), res(aˆ,A)=succ(A), τ(aˆ)=τA(B). COMPUTATIONS ON NONDETERMINISTIC CELLULAR AUTOMATA 5 The time complexity of NCA is the function A : N N defined by A T −→ A(n)=max τA(B) B PA, B n , T { | ∈ | |≤ } where B denotes the length of B. | | The space complexity of is the function A : N N defined by A S −→ SA(n)=max DA(B) B PA, B n , { | ∈ | |≤ } Without loss of generality we may anticipate that (c ,...)=c for all c E. i i i A ∈ Functions A(n) and A(n) can be very complicated, and it’s convenient to use T S their best upper approximations TA, SA : A(n) = O(TA(n)), A(n) = ∈ K T S O(SA(n)) instead of them, where is the class of functions constructible in time K (see below). Given the space Zr, a function f : N N is called constructible −→ in time on r-dimensional NCA, if there exists a constant c and NCA with time complexity (n)=c(f(n)+n1/r) such that for every word B ω∗, BA =n there T ∈ | | exists the single resulting configuration for a(0) which has the form B c , if¯i 1,2,..., (n)/2 r, a (¯i)= 1 ∈{ T } τ (c0, in the opposite case. It means that r-dimensional cube of side (n)/2 can be isolated in time (n), T T where O(n1/r) is the size of necessary domain for input word B. For example, the constructibility in time for n4 and 22n is in fact proved in the section4(groupG1),forthefunctionsnα,qαn, q,α Qandfortheircombinations ∈ with additions, multiplications and superpositions the constructibility in time may be proved along similar lines. A pair of functions (TA,SA) is called a complexity of NCA . Thus in what A follows TA, SA (or, simply T, S with or without indices) will be constructible in time. The class of predicates P, computable on NCA of dimension r with complexity (T,S) is denoted by NC(r,T,S). We’ll write T < O(T) instead of the following: C > 0 N n N T (n) 1 1 ∀ ∃ ∀ ≥ ≤ CT(n). r-dimensional NCA, computing predicate P with complexity (T,S) is called a fastest NCA if P can not be computed on r-dimensional NCA in time T <O(T). 1 Let T denote the time complexity of a fastest r-dimensional NCA computing r,P predicate P. Here are the main results of this paper. Theorem 1. NC(r,T,S) NC(r+1,√T +S,√T +S). ⊆ Theorem 2. NC(r,T,S) NC(r,T ,T ), 1 1 ⊆ 1 r where T1 =Tr+1Sr+1 Theorem 3. Let be a fastest NCA of dimension r. Then A (3) TA(n)=O(SA(n)). Theorem 4. 1). Tr−1,P =O((Tr,P)1+2/r), 2). T =O((T )1−r/(r+1)2). r+1,P r,P 6 Y.I.OZHIGOV Now we shall give the outline of the following sections. All these results are based on two main methods of speeding up computations: The method of direct simulation in r + 1 dimensional space (section 3, Proof of Theorem 1) and the method of optimization of NCA in the same space (section 4, Proof of Theorem 2). Theorem 3 will be simply derived from Theorem 2. Point 1) of Theorem 4 will be proved by the method of simulation in r 1 dimensional space (method of − evolvents,section 5). Point2) of Theorem 4 will be provedin two steps: reduction of space complexity in r+1 space and the following optimization. Note that the both two method of speeding up require nondeterminism. 3. Simulation in r+1-dimensional space. Direct method Proof of Theorem 1. Let P = PA NC(r,T,S), be a cellular automaton of dimension r with ∈ A alphabet ω and complexity (T,S), 0(ω)=c . 0 Inthissectionwe’llpresentthedirectmethodofspeedingup: weshallconstruct the nondeterministiccellularautomatonNCA1ofdimensionr+1,whichsimulates in time O(T1/2+S). A The rough idea is that we expand the alphabet of the cellular automaton at A hand and use r+1stdimension to code H state transitions of into one big r+1 A dimensionalstatetransitionofthenewautomatonNCA1simulating ,whereH = A O(√T +S). The single obstacle which will remain is that the initial configuration for NCA1 is not a(0), but the ascending map, corresponding to input word B (the B definition is in the next section). This obstacle will be overcomein the last part of this section. Definition A port is a list p of the form: (4) p=(Mark(p),con(p),env (p),env (p),...,env (p)), 1 2 2r+2 whereA,Barethespecialnewletters,Mark(p) A,D ,theothermembersoflist ∈{ } (4)arearbitrarylettersfromω,andthefunctionscon(p),env (p), j =1,...,2r+2 j are defined by equality (4). Alphabet of NCA1 Let ω be the set of all ports with the exception of (D,c ,...,c ). Then the 0 0 0 alphabet of NCA1 is ω = ω ,b , where ,b are new letters, and let 0(ω ) = 1 0 1 ∪{∅ } ∅ (A,c ,...,c ). 0 0 Commands of NCA1 Since the dimension of NCA1 is r+1, the commands of it have the following form: (p ,p ,...,p ) p . 0 1 2r+2 −→{ } Letallp ω , q =0,1,...,2r+2. Theset p consistsofallelementsp ω to q 1 1 be described∈below. Let s+ = 0,2,3,4,...,2r{+}2 ,s− = 0,1,3,4,5,...,2∈r+2 , { } { } j+1, for j odd, k(j)= j 1, for j even. (cid:26) − We’ll consider separately five different cases. COMPUTATIONS ON NONDETERMINISTIC CELLULAR AUTOMATA 7 Case 1. Let the following conditions be satisfied: j s+ p ω , Mark(p )=A, j 0 j ∀ ∈ ∈ j s+ 0 con(p )=env (p ), con(p )=env (p ), j j 0 0 k j ∀ ∈ −{ } where k =k(j) and con(p ) (con(p ),con(p ),...,con(p )). 2 0 3 2r+2 ∈A In this case p is such a port that Mark(p)=D, or p is p . 0 Case 2. Let the following conditions be satisfied: − j s p ω , Mark(p )=D or p =0(ω ), j 0 j j 1 ∀ ∈ ∈ − j s 0 con(p )=env (p ), con(p )=env (p ), j j 0 0 k j ∀ ∈ −{ } where k =k(j) and con(p ) (con(p ),con(p ),...,con(p )). 1 0 3 2r+2 ∈A In this case p is such a port that Mark(p)=A, or p is p . 0 Case 3. Let p =b, Mark(p )=D or p =b. 1 0 2 Then p is p or p is obtained from p by the following redefinition: we put 0 0 A, if Mark(p )=D, 0 Mark(p)= (D, if Mark(p0)=A. Case 4. If j s+ s− : p =b, we put p=b. j ∃ ∈ ∩ Case 5. In all other cases we put p= . ∅ NotethatNCA1isnondeterministiceventhough maybeaCAofdeterministic A type, because in the cases 1 and 2 the choice of p is not uniquely defined. Let t be time step, H be some positive integer. We suppose that H is arbitrary till Lemma 3. SomepeculiarconfigurationsofNCA1arecalledH,t-maps. Mapswillbeoftwo sorts. Definition. An Ascending map of high H at time step t (A,H,t -map ) is such a configuration a(t) for NCA1 that ¯i Zr+1 10 If i / 1,H , then a(t)(¯i) ∀ω∈ . If a(t,¯i) = 0(ω ), then 1 i H, and 1 0 1 1 ∈ {− } ∈ 6 ≤ ≤ a(t, 1,i ,...,i )=a(t,H,i ,...i ) =b; 2 r+1 2 r+1 20−If¯i: 0 i <H 1, then 1 ≤ − con(a(t,i +1,i ,i ,...,i ))= (con(a (t,¯i)),con(a (t,¯i)),...,con(a (t,¯i))), 1 2 3 r+1 0 3 2r+2 A 30 If 2j, if ǫ=1, s(j)= 2j 1, if ǫ= 1, (cid:26) − − then j : 1 j r+1 ǫ 1, 1 con(a(t,i ,...,i +ǫ,...,i ))=env (a(t,¯i)), 1 j r+1 k ∀ ≤ ≤ ∃ ∈{ − } if the two parts of this equality exist. 8 Y.I.OZHIGOV Definition. A Descending map of high H at time step t (D,H,t-map) is such a configuration a(t) for NCA1, that ¯i Zr+1 ∀ ∈ 10 See above. 20 If 0<i <H, then 1 con(a(t,i 1,i ,i ,...,i ))= (con(a (t,¯i)),con(a (t,¯i)),...,con(a (t,¯i)). 1 2 3 r+1 0 3 2r+2 − A 30 See above. The following proposition relates evolutions of to those of NCA1. A Lemma 1. α(0),...,α(τ),... is evolution of iff there exists an evolution A (5) a(0),...a(t),... of NCA1, where for every τ =0,1,... the following condition C is fulfilled: τ C . t=t(τ) N q =q(τ): 0 q H 1 ¯i Zr con(a(t,q,i ,i ,...,i ))= τ 1 2 r ∃ ∈ ∃ ≤ ≤ − ∀ ∈ α(τ,¯i), where for t even: τ = t(H 1)+q, and a(t) is A,H,t-map, for t odd: − τ =(t+1)(H 1) q and a(t) is D,H,t-map. − − Proof. 1. Necessity. Let α be an evolution of . An evolution a of NCA1 is called A τ-evolution if the condition C is fulfilled. At first let us prove by induction on τ τ that for any τ there exists τ-evolution. Basis: τ = 0 follows from the definition of A,H,t-map. Step: follows from the definition of NCA1. (cid:3) Nowweintroducetheorder onN 0,1,...,H 1 bythefollowing: (t ,q ) 1 1 ≺ ×{ − } ≺ (t ,q ) iff t t or (t = t - even and q q ) or (t = t - odd and q q ). 2 2 1 2 1 2 1 2 1 2 2 1 ≺ ≺ ≺ Note that if τ < τ , then (t(τ ),q(τ )) (t(τ ),q(τ )). Consequently, in view of 1 2 1 1 2 2 (cid:22) the definition of τ-evolution, if a is τ -evolution, d is τ -evolution, then for every 1 2 pair(t,q) (t(τ ),q(τ )) wehave ¯i Zr a(t,q,¯i)=d(t,q,¯i). Thus weobtainthat 1 1 (cid:22) ∀ ∈ there exists the evolution a of NCA1 which coincides with every τ-evolution on all lists (t,q,¯i), where (t,q) (t(τ),q(τ)). Necessity is proved. (cid:22) 2. Sufficiency. Follows from the definition of NCA1. Lemma 1 is proved. Lemma2. Ifa(0),a(1),...a(t),... is evolutionofNCA1anda(0) isH,0-map, then a(t) is H,t-map iff (6) ¯i Zr+1 : 0 i H 1 a(t,¯i)= . 1 ∀ ∈ ≤ ≤ − 6 ∅ Proof. Induction on t. Basis: t=0. Follows from the condition. Step follows from the definition of NCA1 and those of H,t-map. Lemma 2 is proved. Let [x] denote integral part of x R. ∈ Lemma 3. Let some predicate P be computed on NCA with complexity (T,S), A H [ T(n)] < T(n)/2 , B Σ, α(0) be the initial configuration of , corre- | − | ∈ A sponding to B, t=2[ T(n)], n= B . p p | | If B P then for some evolution of NCA1 of the form (5) the condition (6) is ∈ p fulfilled and (7) ¯i Zr+1 :con(a(t,¯i))=succ( ) ∃ ∈ A and if A / P then for any evolution of NCA1 of the form (5) with the condition ∈ (6) the following property takes place (8) ¯i:con(a(t,¯i))=succ( ). ∀ 6 A COMPUTATIONS ON NONDETERMINISTIC CELLULAR AUTOMATA 9 Proof. Follows immediately from the definition of computation on NCA, Lemma 1 and Lemma 2. Lemma 3 is proved. 4. Auxiliary automata To finish the proof of Theorem 1 we must construct two auxiliary NCA: 1). NCA2 – which begins to operate from d(0) – initial configuration, corre- sponding to B Σ in Zr+1 , so that for some evolution a from Lemma 1 and for some t′ α(t′) =∈a(0), H [ T(n)] < T(n)/2, n= B . | − | | | 2)CA3 – deterministic CA, whichbegins to operate fromarbitrarychosenH,t- p p map from (5) and has the result only if (6) is fulfilled, and in this case succ(CA3) CA3[a(t)], if (7), ∈ (succ(CA3) / CA3[a(t)], if (8). ∈ If now we combine the sets of commands of NCA1 , NCA2 and CA3, and put succ( ) = succ(CA3), E( ) = E(CA3), then in view of Lemma 3 the resulting B B NCA will satisfy the conditions of Theorem 1. B Now let us describe NCA2 and NCA3. Real work of NCA2 is such that at first the group G1 will operate, and after that, groups G2 and G3 will operate simultaneously. NCA2. The program contains 3 groups of commands: G1 : Realization of function H =O( TA(n)+SA(n)). G2: Isolation of area for modeling. p G3: Construction of A H 0-map. − − If , for example,TA(n)=22n, SA(n)=n4, then G1 consistsof allcommands of the following forms: (ci,...,y,?)−→c¯i, (c0,c0,...c¯i)−→d, (c¯i,...)−→ci, (c¯i,...,c0)−→c+i , (c ,...,c¯ ,?) c∗, (c+,...) c , i j −→ i i −→ i (c∗i,...c¯j,?)−→c¯i, (ci,...,6=c¯s,c+j )−→c+i , ′ (d,c0,...,c¯i) d, (y,...,c+) e, −→ i −→ where i,j,s take all values from 1,2,... , ? means an arbitrary letter, y c ,d,d′ , c¯,c∗,c+ are new differe{nt specia}l letters for any c ω. ∈ { 0 } i i i i ∈ Group G2 consists of all commands of the following forms: ′ (c ,d,...) d, (e,...) c , 0 0 −→ −→ (d,d′,...) d′ (z ,c ,z ,...c ) c , 1 0 2 0 0 −→ −→ (d′,=d′,...) d, (z1,c0,c0,...,c0) b, 6 −→ −→ (...,b,...) b, (c0,c0,e,...) b, −→ −→ where z ,z d,d′ . 1 2 ∈{ } 10 Y.I.OZHIGOV Group G3 consists of all commands of the following forms: (c ,b,...) h , j j −→ (c ,h ,...) h , 0 i s −→ (h ,...) h , i i −→ (h ,...) Γ , i i −→ (h ,...,Γ ,...) , s j −→∅ (Γ ,...h ,...) , j s −→∅ wherei,j,stakeallvaluesfrom 1,2,... ,h arespecialnewletters,corresponding i { } to each i, and Γ takes values from the set of all ports p such that con(p)=c . i i For TA(n)=n4, SA(n)<O(√T) the group G1 consists of all commands of the following forms: − ′ (c ,...,=c ,?) c , (c ,...,c ) d, i 6 j −→ i 0 i −→ (c−,...,c′,?) c+, (c ,...,c ,=c0) c+, i j −→ i i 0 6 j −→ i (c′,...,=c−) c′, (c+,...,=c ) c′, i 6 j −→ i i 6 0 −→ i (c′,...,c−) c , (c ,...,c+,?) c∗, i j −→ i i i −→ i (c+,...,c ) c0, (c∗,...,=c ) c , i 0 −→ i i 6 0 −→ i (c0,...) c , (c∗,...,c ) c−, i −→ i i 0 −→ i (c ,...c0) c0, (c , =c+,c−) c−, i j −→ i i ···6 s j −→ i (z,...c0) e, (c ,...c∗,=c−) c∗, i −→ i j 6 s −→ i (d,...c ) d′, i −→ where z d,d′ . NCA2 is described. ∈{ } CA3. Put E(CA3)= c′,c′ . { k k−1} (Γ ,= ,b, ... ) ρ0 , cp 6 ∅ −→{ p} no ∅ (ρip,|.{.z.})−→{ρip+1}, i=0,1,...,2r, p∈{k,k−1}, no ∅ (= ,= ,ρ2r+1, ... ) ρ0 , 6 ∅ 6 ∅ p |{z} −→{ p} no ∅ (b,ρip|,{.z.}.)−→c′p, (..., ,...) , ∅ −→∅ where every letter of NCA1, NCA2 may occur in ”...”. Theorem 1 is proved. The general form of ”successful” operation of resulting cellular automaton is shown on Figure 1. The technique evolved allows to derive the following amplification of Theorem 1.