TH E UNIVERSITY OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department DESTRUCTION OF A UNIVERSAL COMPUTER-CONSTRUCTOR IN CODD'S CELLULAR SPACE Ulrich Golze August 1972 Technical Report No. 137 with assistance from: National Science Foundation,'."' Grant No. GJ-29989X. \ Washington, D.C. and the "..... Computational Facilities of, "';' The Technical University of Hanover, Getmany " -'

:-;- -. K..,, 64, I,

A universal self-reproducing computer can be embedded into the cellular space designed by E.F. Codd in CELLULAR AUTOMATA. This paper shows that destruction, the reverse process of self-reproduction, is possible in Godd's space. in other words, a universal computer can self-reproduce and, hereafter, erase its offspring again.'elfreproduction is useful for highly computational programs while destruction permits adaptation to programs requiring a lot of storage space The first step in destroying a machine is to paralyse its activity. Then the destroying machine makes the passive network part of its own construction (destruction) arm, and retracts it.

hIntroduction and Summary 2. Description and Paralysation of the Extended UCC 2.1 New Components 2.2 The Modifications of the UCC 35 Destruction 351 Assumptions 3.2 Cutting up a Straight Path 3.3 Removing Path Components 3,4 Justification of Transition Function Changes

1 Introduct ion and Su nmary Parallel operation is one of the most characteristic features of cellular spaces. Universal Turing machines can be implanted into cel-..r spaces to make them computation-universal. However, Turing machines are sequential so that the power of parallel operation takes effect only on a level where several machines operate simultaneously. Therefore self-reproduction becomes a useful. property. Assume a problem requiring a lot of computational work is to be computed by a cellular machine, It could first reproduce itself, say n times, and then the n+1 machines might start computing in a parallel manner. Several computation-universal self-reproducing cellular machines have been designed (J. von Neumann [L4 and J.W. Thatcher [3], E.F. Codd [lC7 A.R. Smith III [2] ). The background material for this paper will be Codd's CELLULAR AUTOMATA L17. The space described there is minimal in the sense that it is a strongly rotation-symmetric 8-5 space (each cell has 8 states and 5 neighbors) while von Neumann's and Smith's spaces are weakly rotation-symmetric 29-5 and not rotationsymmetric 7-7 spaces respectively. Compared with the latter Codd's space is not minimal if one applies the following complexity measures: (1) The ratio cellular time steps per simulated Turing machine time step ("distance to real-time simulation"), and (2), the number of cells required to simulate a Turing machine, Even problem-oriented Turing programs are not very efficient. To use universal Turing machines for practical purposes is absurd. As

- 2 - f.mich points out, his 7-7 space is only capable of simulating a unitv.'r~';'I'tI:- i; v.iflt i.e his cell constructions are highly TuringI:,,;,,. n-t:Jcx: ~ WoI o example, a (relatively small) loo-state Turing program would generate a lool-state cellular space. Moreover a realtime simulation of a universal Turing machine in the 7-7 space is, of course, not real-time with respect to the original Turing machine simulated by the universal machine. Codd's self-reproducing universal computer-constructor (UCC) embedded in an 8-5 space is Turing-machine-independent, i.e. capable of simulating every Turing machine. It shows interesting structural similarities to real computers. The UCC offsprings are separated in such a way that they can operate without interference if desired, while the UCC copies in Smith's space have to share one common tape. Though a reasonable technical realization has not at all been found,, we think that among the cellular computers:mention-ed above Codd's UCC is best adapted to practical purposes. There is still a gap pointed out by Codd in one of the open questions concluding his work: "Can the partial transition function specified in Chapter 4 be extended (without adding new states to the space) so as to make possible the destruction of a machine which is active but not actively defending itself?" In other words, is there a reset-program that restores the initial situation of only one machine being in the space? -'" Ml1v deal with a finite subspace, a

- 3problem involving a lot of computation time has been computed in ~,f llt y tj r)v rproductifor: of' anr original UCC, a second problem might need a great deal of storage space. Now one of the computers might destroy some of the copies again and use the space occupied by them previously as storage space. Another application might be found in taking universal computing machines as simulators of biological cells or organisms. Destructing a machine and reconstructing it somewhere else may be regarded as a movement of the organism, moreover, one machine destroying another one might simulate the killing or dying of cells or organisms. The present paper shows that the UCC in Codd'E 8-5 space can be modified and extended in such a way that a UCC is capable of destroying an active copy of itself. This takes place in two main steps. 1. Paralysation: The destroying machine turns off the periodic emitter, the source for all signals, of the machine to be destroyed thus converting it to a passive network of paths, corners, T-junctions, and gates. 2. Erasure: A subroutine S enables the destroying machine to "cut up" a path. With the help of this subroutine the network can be removed. From a different point of view, step 2 constitutes a way to erase an important subclass of the oonfigurations over {0,1,2,3. Before, only techniques for erasing (0,1) configurations were known in Codd's cellular space. Comparing this result with von Neumann's 29-5 space

- 3t-:.:tt uts4 nrsote t}taLt todaiy no way is known to me that sho'ws how in von.::-.~*:~'. a.; a ([-di:ono sional) passive (0,1) configuration, not to.i-nion ar ac tive UCGC, could be erased. Let us fix the result of this paper precisely. The reader is assumed to be familiar with the definitions and terms introduced by Codd in U1]. We add the definition: The configuration c dst the configuration d disjoint from c if there exists a time t such that Ft((od)l sup d is quiescent. In other words, c erases the support of d within t time steps. Although there are trivial cases, erasing is non-trivial in the following Theorem: The transition function in Codd's 8-state, 5-neighbor space can be extended and slightly modified in such a way that there exists a self-reproducing universal computer-constructor (UCC) with the following property; Let there be in the construction site of a universal computer-constructor UCC1 a second one, say' UCC2, - accessible for UCC1 - executing any computation or construction task. Then UCC1 is able to destroy UCC2. The information stored in UCC2's memory section and additional UCC's in the space are not affected by the destruction process, (Applying the definition exactly, one had to say: If the initial configuration of the whole space oontaining UCC1, UCC2, tapes, additional UCC's eto. is o, then (o - UCC2) - the oonfiguration ~'outside of.UCC2" - destroys UCC2.)

4 - 2. ds scri tion and Paral sation of the Extended UCC In this chapter we are going to describe an extension of Codd's UCC with additional properties useful in chapter 3. ve will show that the new UCC can be paralysed by the injection of a single signal (analogous to the activating signal) with the result that it becomes a passive configuration over 0,1,2,3}. In other words, all signals circulating in the UCC are annihilated. Ann end-of-paralysation signal is sent to the destroying machine, 2,1 New Components A B 07 two-way - lock Norm. Norm. off.D n I -_____................_________...._.~,07..070. K Fig* 1 Periodio emitter wi th turn off

-5i * I.^l,,w Lhe p, io'i,i]jo ur itcrx' with turn off. The first input:i-~,, v: ^ A starts the periodic emission of 07 outputs at K until a second 07 input is given. Without the heavily printed lines AC and FCEID we have exactly the periodic emitter shown in f 1, Fig. 5.7. Copies of the first 07 input turn gates C and G on and reach via junction TF the points G and K, The one at G is annihilated, the other one begins to circulate clockwise. Every circulation produces (periodically) a copy leaving the circle at K and copies at F and H, which are annihilated by gate C and the two-way lock respectively, Now the second input turns gate C off imjping that gate D is turned on by the next copy produced at F by the circulating signal. Because we may assume that FCEID < FGHKD, the circulating signal is annihilated at D and the emitter stops working. The component switch symbolized by AJ 1.,,e At A has two inputs A and S and two outputs Al and A2. An aotivating input 07 at S enables the switoh to work properly: All signals (0s)s=4,5,6,7 entering the switch at A leave it unchanged at A1 until a switch input 07 is given at S. The next input at A will be converted to 07 and leave

6 the switch at A2 o There is the restriction that the first input at A is a 07. This requirement, however, will be met automatically when u^.in< the component in the UCCo i, o 2 shows the details of the switch, From now on let us make the assumption, although not always necessary, that -- represents a one-way lock. A1 $W A Norm. off D _ FF ", ^ C t ~Norm. on n Norm, off G i S Fig. 2 Switch The activating input at S turns gate E2 on, The first input at A is a 07 signal duplioating at D, F and C. Copy 1 prooeeds via H to gate E2

- 7 turnwing it off. Copy 2 is annihilated by gate El which was turned on before by copy 3 via C. This is guaranteed by the delay after F implying DC2E1 < DFE1 and DHIGE2 < DFE2. Finally, copy 4 leaves the switch at output Al. So do all the following inputs at A. Their remaiinng three copies, however, are annihilated between H and G, C and E1 aT n1 at L E. The situation changes when a switch input at S turns gate E2 on thus converting the two gates E1 and E2 to a. signal transformer type 7 The next input Os at A is converted to 07 leaving A2 and turning B on before the copy Os from C leaves the delay after C (DFEIB < DCB). Thus no output occurs at A1. 2.2 The Modifications of the UCC We extend the memory section shown in r1j, Fig. 6.2 by three additional construction paths C1, C2, and C3 (though their purpose is destructive rather than constructive), a timimg path T which is merely a straight path and 8 position tapes PX, X ^ C1,C2,C,C3,D,K,M,P1 as shown in Fig. 3. The position tape PX, X* 1D,K,M,P1 contains the natural number n if the n-th cell of tape X is scanned by its tape path. The easiest way to represent n is a string of n 1's. Whenever tape path X moves one step to the right or to the left, the tape path PX does this too while at the same time, however, marking or erasing a'1' after or before the move respectively.

Construction site i'Path C1 Cl ~^~~ ~ Path C2 B I C 2 c Construction path C C ~-~ — ~i~ ---.....Path C3 C3 Timing path T T D a t ap D 3~K lOlcounter tape K M [IMarker tape M P ItProgram tape P PC sition tape for C1 — PCq PC~ PC2 PC2 PC3 1 PD PK e A Figs 3 PM pse Pr Memory seotion

cic lo Fc~oEcho discri~ storage Pejmitoc s Control a, se ctionon ~ __ 1 r Decoder 1 0F0 707 except 0 aEcdinho o~ ~ storage conn ic tionsver toal gaterdi0es crossor emitter p 34beh with' turn off E $30 additional mn connections r i 1s-way.locks os Warm g6 up to all gates de-la except crossover echo switch injection echo discr. receiver 1-way locks

- lo - Analo'ous the position tapes PX, X = C1,C CC3 keep track of the ocs. - ions of the construction paths. One possible way to do this is to represent'extend' by'1','extend right' by'01', and'extend left' by'001'. Ihenever a retract operation is executed, the corresponding code 1', fG01', or'001' has to be erased. For example, the position obtained by the instruction sequence x-x-x-xr-x-xl-x-x-r is represented by 1110110011 Let us now consider the differences between the execution section of the old UCC as designed in. [1, Fig. 6.2.and the one of the new UCC in Fig. 4. The periodic emitter is replaced by one with turn off, we added a switch and the locks 2 and Q and we replaced the linkage between the periodic emitter and the transformers type 456 as well as the subordinate-restored gate A by the simple input A. That avoids crossing a path with periodic signals proceeding on it. Furthermore we do not need an injection receiver because section 3 describes a way to connect and disconnect two paths. How is the new UCC operating? Let there be in the construction site of UCC1 the (0,1) skeleton of UCC2. We show how UCC1 activates UCC2 and lateron destroys it, The pseudo-injection receiver Q of UCC2, an ordinary unsheathed path end, is connected with the construction path C of the stimulating machine UCC1. The sheath signal 06 and the activating signal 07 are injected. The activating signal turns on the new periodic emitter and all gates as described in Fig. 4. Furthermore it calls for the first

- 11 - microprogram step and activates the switch. Thus the switch now connects the memory section with the echo discriminator, Note that the first echo signal to pass back from the memory section is 07. After the injection of 06 and 07 the paths C1 and C2 of UCC1 will disconnect its path C and the pseudo-injection receiver ) of UCC2 (see section 3,2). troram execution takes place almost like in the old machine. If a 07 signal is to be sent to the transformers 456, we do this directly rather than releasing a signal from the periodic emitter by means of a subordinate-restored gate, Moreover, the microprogram in the control section keeps the position tapes up to date whenever one of the construction paths or paths D, K, M, or P are moved. Note that the position tape PC3 holds implicitly the information about the current length of the timing path T because we want to assume the following rule: The length of T is kept t units longer than the length of C3 where t is a fixed positive integer. Now the destructing machine UCC1 connects its path C with the pseudo-injection receiver Q again. We assume that the paralysation signal (a single 07) is not injected too early, i.e. UCC2 is at least completely activated, thus either testing the start cell or executing a program or having finished the execution again testing the start cell. The paralysation signal flips the switch. After an unknown but finite time an echo from the memory section enters the switch and leaves it via 5( converted to 07. This signal turns the periodic emitter off.

12 The last signals produced by the emitter are annihilated somewhere because the control section is waiting for a (never arriving) response from the echo discriminator.'. it Is clear that no signal circulates in UCC2 when the e:.-of-paralysation signal - a copy of the 07 output at ( - leaves (4 towards UCC1. Paralysation has taken place. At first sight, one might ask if one could not do without the switch. The paralysation signal could turn off the emitter directlye This would stop any activity except for a sense-and-wait signal which might already be on the way at the time the emitter is turned off..o UCC1 had only to wait until the echo would return and die somewhere in the control section. The cru? lies in the word "until". Since the length of a tape is unbounded, only the returning signal itself can tell after what (finite) time a sense-and-wait operation is terminated,

- 13 - 3. Destruction In this chapter we show how the paralysed UCC2, a network of sheathed - aths canr b destroyed. Th is.ill complete the proof of our theorem. Note that any arbitrarily fancy signal sequence which might be able to dissolve a path when passing, would fail at the first of many one-way locks. Therefore the network can be destroyed only "from the outside"' 3.1 Assumptions.;e make the following assumptions about the extended UCC. 1. The distance between two corners or a corner and a gate node is at least 23 units. (A corner may have two or three arms. In the latter case it is usually called T-junction.) 2. All paths running parallel have a distance of at least 23 units. 3. Turning on a gate does not happen while a signal is passing on the subordinate path. Thus we avoid the neighborhood state 2 0232 This requirement is met if we design the particulars of the UCC carefully and provide a sufficiently long distance between two successive signals. The only exceptions to assumptions 1 and 2, which provide enough operation space for the destruction paths, concern the construction and tape paths. However, also they should avoid zigzagging (produced e.g. by'extend right'-'extend left') and should not have their sheath in contact with that of any other path.

14 In passing we note that the only uncertainty about state and location Qc a araalysed UCC concerns the positions of the memory paths and the states of the gates. Under these assumptions we can now reduce the destruction of a paralysed UCC to the problem how to tcut up" a straight path. The solution of this problem follows. 3.2 Cutting up a Straight Path We are going to extend and slightly modify the partial transition function f given in [17, table 4.1o which enables us to define 10 subroutines useful in cutting up a straight path. Subroutine S1 - extend to a path: Fig. 5 shows the extension of a construction arm to a path sheath using the signal sequence x = (07-06). Though the old UCC defined in [1] does not require this operation, no extension of f is necessary. 2222222 2222222 1111111. 11111 2222222 x into 222222 constr, path 2 212. 212 212 212 construction ~ Ftpath Fig. 5 Extend to a path

- 15 - Subroutine S2 - retract from a patth: This operation is inverse to 21. The required signal sequence is r = (04-05-06-06). However,'.1^ ^a.sit* ion function f has to be extended, 2 2 2 1222222 22222 22222 2222 2) 2222 2222T 22222 r222 ^^^a~~ 1 a? ~' 1 77 117 iai11 111111 1111111i 22222 22222 22222 2222 2222 2222 22222 22222 22222 2 2 2 2 2 2 212 212 2 2 312 352 31 363 2 212 to 2142 202 212 tO5 202 212 to6 202 212 T06 212 L212 o 02! 2 212 2121 2 212 212 oonstr (a) path (b) (o) (d) (e) (f) (g) (h) (i) Fig. 6 Retract from a path Fig. 6 gives detailed shots of the retract operation. Tos means that we send signal Os in the construction path. The additional transitions are 2 0204 2 c (4/3) 2 0205 2 e (4/3) For example, in Fig. 6.e the cell in row 4 and column 3 emphasized by O faces the undefined neighborhood state 2 0205. Subroutine S3 - cut away first'2' of a sheath: The initial situation (Fig. 7) is produced by subroutine S1 and requires a turned on gate in the construction path.

- 16on C C Fig. 7 Initial situation for S3, S4, and S5 As Fig. 8 shows, the signal sequence c2 = (o6-o4-04) (cut away'2 of a sheath) produces an undesired echo. Gate C1, however, will annihilate this echo immediately. Afterwards the gate may be turned off and path C1 can be retracted using subroutine S2, 2222222 2222222 2222222 2222222 2222222 2222222 111111 1111111 1111111 1111111 1111111 1111111 2222222 2222222 2222222 222222 222.222 222.222 2 H+2 212 12 2 312 312. 212 1t060-o4 242 202 212 212't0 202 21? 202 212 212 212 212 2_12 212 212 212 212 2 (a) (b) (c) (d) (e) (f) 22 222222 2 222222 222222 2222222 1111111111 111111 111111111111 22222 22222 222 222 222 22222 2~2.0.2 9 2a 212 2 242 212 04 212 212 242 202 212 212 212 242 (g) (h) (i) (j) Fig. 8 Cut away first'2' of a sheath

171'. r euired new transitions are 0 0204 4 c (4/4) / 2 1242 0 d (3/4) 0 0243 0 d (4/3) 0 0242 0 d (4/5) 4 0203 4 f (5/4) 1 0042 0 g (5/3) 0 0024 3 h (5/4) 7/ 2 0023 0 i (5/5) 0 2433 1 i (6/4) The two transitions denoted by / are a modification rather than an extension of f We will take special care of them in section 34 Subroutine S4 - cut away additional'2' of a sheath on the right of aSgap: Using the same initial situation (Fig. 7) and the same signal sequence o2 as in the last subroutine, we add the two transitions 2 0124 0 d (3/4) 0 0043 0 d (4/3) to obtain the results shown in Fig. 9 2222222 2222222 2222222 2222222 2222222 2222222 1111111 11111111 1 111111 1111111111..2222 2..2222 2. 2222 2...222 2.. 222 2...222 2. 04. 212 22 242 312 12 242 312 312 2 22 1 06-o04 242 202 212 212 4 1 2 212, 202 212 212 212 as in Fig. 8, 212 212 212 212 212 212 (f),'..,(j) 212 (a) (b) (o) (d) (e) (f) Fig. 9 Cut away additional'2' of a sheath on the right of a gap

18 - tL~_ _ ~-1'2222 222 2222222 22222 2222222 222222 222222 111 1 1 i 1111111 1 11'111 1111111 1 11111111 1 1 11111 111 1 1| 2222... 2222... 2222... 222... 222.... 22.... 222.... 2..4 3.2.2 212 212 22 31 312 32 12 3 342 212 t06 212 T04 202 212 212 212 04 202 212 212 212 212 212 212 212 22 12. 212 212 212 22 2 (a) (b) (c (d) (e) (f) (g) 2222222 2222222 1222222 2222222 2222222 2222222 1111111 1111111:1111.111 1111111 111 1111 1111111 22 2.... 1 222. 22. 22.... 1 222...222 222 2 2 2 ~ a 1,-2..1212 212 2 212 242I 212 041 | 06 212 t6 2r 212 212 212 242 202 212 212 212 212 212 242 212 212 (h) (i) (j) (k) (l) (m) Fig. lo Cut away additional'2' of a sheath on the left of a gap Subroutine S5 - cut away additional'2' of a sheath on the left of a gap Again, we start in the initial situation of subroutine S3, but we use an extension of c2, namely the signal sequence c21 = (o6-0 o404-06-06), to induce the construction path to execute the desired out away operation (Fig. lo). For a proper operation of the subroutine we have to add the transitions 2 0421 0 d (3/4) 3 0024 2 h (4/4) 4 1132 0.h (5/4) 0 0224 1 i (5/4) 0 1243 1 j (6/4)

- 19 Furthermore we should take care that the second 04 of c21 is not too closely followed by 06 so that a collision between the latter and the 04 echo is avoided. Subroutine S6 - cut awa first II' of a ath: Assume sufficiently many 2's of the path sheath have been cut away. Extending the construction path to the 1' shown in Fig. 11.a is the same as if a (0,1) configuration is approached. Moreover, we can use the erase sequence e = (06-07-04-0o5-0606). However, the transition table requires two additional rows: 1 0124 1 h (2/4) 1 0421 1 h (2/6) Fig. 11 gives the details. 22222222 22222222 22222222 22222222 22222222 11111111 1111111 11111111 11111111 11111111 22*.2... 22 2.3. 22..... 22..3... 212-' 212 212 312 313 212 0to6 212 _7 212 04 212 05 212 212 212 212 212 212 212 212 212 212 212 (a) (b) (c) (d) (e) 22222222 222 22222 22222222 22222222 22222222 111111 11 11111. 1 1 11141 111111.111 111.111 22 3. 3*,* 22..4.. 22...... 22. o0.... 22...... 363....... 2 ~O'6 202 212 212 212 - 212 212 212 212 212 212 212 212 212 212 212 (f) (g) (h) (i) (j) Fig. 11 Cut away first'1' of a path

=ubrouine S7 - out away additional'11 of aath on the right of a'a-: The same initial situation as in the previous subroutine9,!.. e: s-iral sequence e and only one more transition, namely 1 0214 o b (2/4) are required to perform subroutine S7 as shown in Fig. 12, 2222222 2222222 2222222 2222222 2 4 212..... 2 212 1 06-_07-04-05-06 _ 212 212 T 0o6 212 212 | 212 212 212 212 | 212 212 212 (a) (b) (c)' (d) Fig. 12 Cut away additional'1' of a path on the right of a gap Subroutines S6 and S7 enable the construction arm to cut away the core of a path from the left to the right. Analogously, 23 and S4 are sufficient to remove the sheath of a path. One might ask, why S5 is necessary at all. However, the main subroutine S will call S5 when generating norm ends. Subroutine S8 - cut away first'2' of a 2-chain: After removing the sheath and the core of a path a simple chain of 2's is left over. Subroutine S8 cuts away the first'2' of such a chain, namely the one determined by the initial position of the construction path in Fig. 13.

- 21 - Siuroutine S1 is useful in obtaining this positionO ~;7! - *e - el 1. * * e. *.! e e e e e H ~ ~ 122222222 22222222 222 22 22. 222 2222.222 i1I2oo 11l o2e. 1 1.3o. 1 3 1 l1. a o 212 | | 272 | | 212 212 2 212 107 202 212 212 212 212' 212 212 212 2 212 (a) (b) (c) (d) (e) Fi g 13 Cut away first'2' of a 2-chain We call the required signal sequence c2c (cut away'2' of a chain) which is 07 concatenated with the retract sequence: c2c = (07)-r = (07-04-05-06-06). This time we have to alter a row of the transition table: / 2 0232 0 c (2/5) Subroutine 9 - cut away additional 2_' of a 2-chain: The sequence c2c also permits the removal of a'2' of a 2-chain located to the right or to the left of a gap, as is demonstrated in Fig. 14 and Fig. 15 respectively. However, the subroutine is not able to annihilate a single 2'

22 - 0..22221..2222...222 222 2 3 2 1 2 _I 212 212 212 2IL 212 212 212 (a) (b) (c) (d) Fig, 14 Cut away additional 12' of a 2-chain on the right of a gap 2222.. 222). 22222.o 222. 0 2 3 2 0 212 i _.7 212 212 tr 2 212 -> 2112 212 212 212 212 212 212 (a) (b) (c) (d) Fig. 15 Cut away additional'2 of a 2-chain on the left of a gap In Fig 15.b there occurs a neighborhood state whose image under the transition function is now defined differently than in [1]: / 2 0032 0 b (2/4) Subroutine S - cut up a straight path and generate norm ends: This subroutine calling all the previous ones is the heart of the process of destruction. Fig. 16 shows how S cuts up a straight path. Not explicitly mentioned are the various extend and retract operations executed by the deetruoting paths. For some of them SI and S2 are called. Paths C1 and C are omitted in Fig. 16.

- 23 - 22222222222222222222222 11111111111111111111111 22222222222222222222222 4S3 22222222222222222222222 11111111111111-11111111 2222 222222222222222222 22222222222222222222222 11111111111111111111111 2222 o. o *.......... 2222 2222222222222222222222 111111.111111111111111 2222..............2222 4S7 22222222222222222222222 q11111,~~~...... o111111 2222... s... o o e.. 2222 s8 22222222.22222222222222 ~111111..0.0.....111111 2222..,.......... 2222 JS9 22222222...... 22222222 111111 0.,0. 0 111111 2222..... 000000...2222 Fig, 16 Cutting up a straight path Now the oonstruotion path C can easily move through the gap and produoe norm ends defined by Fig. 17.

- 24 - 2222o............2222 111111...,,,.,.111111 a f_ 6 0 a o e 0 0 e < 0 a..22 22 Fig. 17 Path gap with norm ends Norm ends should be distinguished from standard ends symbolized by and -- respectively. Referring to the letters in Fig. 18, path C may out away the 2's under letter a, b, c, d, e f, g, h calling subroutine S9, S9, S4, S4, S9, S9, S5, S5 respectively, in the indicated order. d c-b a e f g h 22222222 22222222 111111 111111 2222,,on 2222 C1 C Fig 1'8 Generating norm ends

25 "NVote that this is the only time wNhore,5 and the second appliction c(,f';9 ire xeoeded, It is no problem to approach a norm end and to connect it with the corresponding path using the signal sequence x = (07-06) as indicated in Fig. 19. (This happens to be the same sequence as is required for the operation'extend'.) 212 212 212 1212 212 212 212 212 12212 212 212 212 212 212 norm I 1 1 1 1 212 end 1 1 1 1 212 2 2 1; 212 2 2112 272 212 212 212'x 212 122 202 212 1061' 212 C-S 212 212 12 12 212 Fig. 19 Connecting with a norm end The sheathing signal 06 proceeds to the top until it is annihilated by a gate or used for other purposes. 3.3 Removing Path Components Taking advantage of the assumptions made in 3.1, we can always find enough space to apply subroutine S. Because the destroying machine UCC1 knows the parameters of the network of UCC2, it can remove this network

- 26 - from the outside inwards step by step., Removinr a corner. aorn e r apply S connect 2 times with C ~ ________________ ____ ___ 22 22 0 —- 111 --- (a) (b) (o) retract C - 6 ~;~ 1 several times 0 (d) (e) Fig. 20, Removing a Corner Fig. 20 demonstrates how a oorner may be annihilated. The two arms of the corner are cut up and path C connects itself with one of these arms N o w the o o r n e r i s a p a r t o f p a t h C

- 27 - (Fij. 20.d). It can be retracted easily. 2- A d'a17; a T-sjunction. Iet us consider Fig, 21 22 22 22 22 1^T11- 11 211 1122 ^2212 i22 22 S 212 connect build cate C? ~ ~ ~ ~ ~ ~ C L 1 (a) (b) on 222222222222 t _ _~ ~2 j! 21111111111111 212222223222 212 2 212 212 retract 212 212 212 212 212 212 212 212 01Lo C C (o) (d) Fig. 21 Preparations for removing a T-junction

- 28 - In (a) subroutine S has cut up the three arms of the T-junctione ~1 cnrnects itself with one of them and converts the norm ends of the rerlmaiinin two arms into standard ends (b) o Approaching the right T-arm path C generates a gate and turns it on (c). Thus any signal sequence sent into path C1 affects only the left arm of the T-junction. We can forget about the copies proceeding to the right. In (d) the left arm has been retracted as far as possible sending retract sequences into, path C1,?lg. 22 shows how the signal sequence rt = (05-06-06) (retract T-junction) retracts the remaining stump. 22222 22222 32222 32222.2222 3.2222.2222.2222 215111 250511 211051 26o6i. 6..0111..6111 20611 20222 21222 21222 21222 21222 26222 20222 21222 T05 212 212 212 06 212 212 106 202 212 212 212_ 212 212 212 212 212_ 212 _ 212 (a) (b) (c) (d> (e) (f) (g) (h) Fig. 22 Retract a T-junction The result is a corner connected with ( <E-* being a part of) path C1i Path C turns the gate off and retracts so that C1 is able to remove the corner. We need only one additional transition: 1 02166 f (2/3)

a- 2)S connect test and turn off 1_____________ off 22 1 o?ff __ C2 C C03 (a) (b) (c) dS~ s~.-retract Ci i0r20 T!, C ( C2 C C 3 (d) (e) (f) Fig. 23 Removing a gate in unknown state Unfortunately, the destroying UCC1 does not know the state of a gate to be removed because we want to enable UCCt to start the destruction process at any time, regardless whioh program or which step within

- 3o this" program UCC2 is executing. This is the only case where all four cor:'t-r.;v" tZ.on p aths and the timin, path are required. Fig. 23 shows the main steps. Subroutine S produces (a). After C1, C, and C3 are connected as shown in (b), a test signal may be sent into C1. If the gate is off, it will return, otherwise the gate will annihilate it. However, we do not know how long to wait for a (perhaps never) returning test signal. Now the timing path T turns out to be very useful. It is not difficult to keep the length of C1 less than the length of C3 whenever a gate is to be removede Thus length(Cl) - length(C3) = length(T) + t + holds for some fixed positive number t. Assume the destroying machine UCC1 injects first the sequence'sense and wait' (sw) into T and then a single 07 into C1. Immediately afterwards UCC1 turns off gate T in Fig. 3 controlling T. There are two possibilities Case 1: The tested gate is turned off. The test signal 07 returns from the memory section. Furthermore a copy of it enters path T because gate T is in the off-state, and collides somewhere with the echo 06 generated at the end of path T. Providing the transition By convention, let length(C1) and length(C5) be constant while steps (b)/through (f) in Fig. 23 are executed.

- 31 - 1 2627 7 *pt:. s ar>~. *late each othere Case 2: The tested gate kills the test 07 because it is turned on. The echo 06 returns from the memory section thus indicating case 20 In both cases a cap after sense sequence (cs) should restore the standard end of To An analysis of the gate behavior yields the state diagram of a gate (Fig 24) 2222222 2222222 2222222 -off 06 off 111111 1 1111111 111111 2222222 2222222 2223222: \ 2. 2 / — 212 212 212 212 212 212 07 07/ 06 212 212 212 r 07 (F. ) S d on Fig. 24 State diagram of a gate Applying the sequence gO =~07-06-06) in case 1 (off) and g1 = (06-06') in the second case (on), we may be sure that the gate is in state ) (Fig. 23.o). Now it is easy to cut up the connection between C1 and C3 by use of C2 and C (Fig. 23.e). Finally we obtain Fig. 23.f ~

- 32 In this section and several times before we described the operation of the control section verbally. E.g. g The microprogram in the control section keeps the position tapes up to date..o " It should be clear that such cases require an extension of the control section, additional UCC cor.mands, an enlarged decoder, and many little alterations. We do not:a into -hese details because essentially they are treated in [1]. Removing tape and construction path..'Whenever UCC2 is paralysed it stops working after a sense and wait operation is executed. Therefore, UCC1 should send a cap after sense sequence into the memory section of TCC2 Step 1: Tape path PP of UCC2 is disconnected from the memory section of UCC2 and connected with path C1 of UCCi. (The control of arm PP is transferred to UCC1.) C reads the number n on tape PP approaching PP from the bottom, and C1 retracts n+1 times. (Note that path PP always scans the right neighbor cell of the n-th'1' of tape PP.) Step 2: Applying step 1 analogous paths PM, PK, PD, PC3, PC, PC2, and PC1 are removed. Step 3: Using the information on the position tapes again, UCC1 retracts P, M, K, D, T, C3, C, C2, and C1 o At this point we may recall the assumption of the theorem that UCC2 - the machine to be destroyed - is executing any computation or construction task, that it is not, however, for its part destroying

- 33 - a machine UCC3 From a practical point of view this seems to be an unimportant restriction. However, let us assume for a moment that UCC2 for its part is destroying a machine UCC3. In particular, UCC2 might just have connected its path C12 with the path PP3 of UCC3. At this moment, the information on the position tape PC12 which determines the position of C12 becomes completely false I We will only briefly sketch the method by which we can extricate ourselves from this mess. Assume UCC2 connects one of its construction paths X with a norm end of UCC3 at some point y such that during the next sense and wait operation executed by UCC2 the shape of X is undetermined by PX or X does not have a standard end. This case occurs if X is connected with a tape or construction path or participates in removing a gate. Then a break symbol is printed on PX. Now UCC1 is able to remove that part of X which belongs to UCC2: UCC1 reads the break symbol which is the rightmost information on PX. Using the information about the shape of X, UCC1 cuts up X at exactly the previous boundary position y and removes it. 5. Removing a signal transformer type 7 is no problem. 3.4 Justification of Transition Function Changes At the beginning of this section we list two tables. Table 1 sumrarsies signal sequences necessary for destruction.

- 34 x 07-06 1. extend to a path 2. connect with a norm end r 0405-O0-06 retract from a path c2 06-04-04 cut away first'2' of a sheath or on the right of a gap c21 06-04-04-06-06 cut away'2' of a sheath on the left of a gap e 06-07-04-05-06-06 cut away I1' of a path core c2o 07-04-05-06-06 cut away'2' of a 2-chain rt 05-06-06 retract T-junction gO 07-06-06 turn off if off gl 06-06 turn off if on Table 1 Signal sequences necessary for destruction Table 2 lists the additional transitions and those defined differently in l a] 2 0204 2 S2 3 0024 2 S5 2 0205 2 S2 4 1132 0 S5 0 0224 1 S5 0 02044 S3 124S3 1 S5 / 2 1242 0 S3 0 0243 0 S3 1 0124 1 S6 0 0242 0 S3 1 0421 1 S6 4 0203 4 S3 1 0042 0 S3 1 0214 0 S7 0 0024 3 S3 2 0023 0 S3 2 0232 0 S8 0 2433 1 S3! 2 0032 0 S9 2 0124 0 S4 0 0043 0 S4 1 0216 6 rt 2 0421 0 S5 1 2627 7 collision Table 2 Additional transitions and alterations

- - ~ We have to justify the four alterations marked by gi. This leads to the question: Which of the transitions defined in Cl 3 are really necessary? The following situations were simulated on a digital computer. a. Signals 04, 05, 06, and 07 proceeding straight ahead and passing a corner and a T-junction on every possible arm. b. Collisions of 06 with 60 and 07 with 70 on a straight path, at a corner, one and two units away from a corner, at a T-junction and one and two units away from a T-junction. c. 06 sheathing a network (including gates), analogous to a. and b. d. Sending 06 and 07 into all kinds of path ends. e. Sending 06 and 07 into the control path of a gate in state i,, and of Fig. 24 f, Os passing a turned on gate to the left and to the right and a signal transformer type 7 (s = 4,5,6,7). g. Executing x, xr, xl,, rrr, rl h. Executing sw, os, m, e (64 possibilities)'* In marking every transition actually needed, it was found that many transitions in fi were not used. This may be due to various reasons;

- 36 - 1i. Cnfigurations like paths running sheath adjacent to sheath, zigzagging in a path (produced by xr-xl or xl-xr), a gate close to a corner, turning on a gate while a signal is passing on the subordinate path etc. make the construction of a UCC easier, but they are not necessary. 2. Systematically generated transitions using (0s)s=4,5,6,7 create redundancy. For example, collisions of 06's and 07's are, collisions of 04's and 05's are not required. 3. The short table 4.8 in [1 lists all exceptions from the rule: Neighborhoods over 10,1,2,3) remain unchanged. This defines all transitions over {0,1,2,3} and thus, of course, more than necessarye 4. An injection receiver was needed before. In particular, the four alterations (/) in the transition table were not used. In a second computer simulation run the modified and extended transition table was loaded. Again, the situations (a),..,,(h) were simulated, but also the subroutines S1,..,,S9, and S and the removing of a path, a corner, a T-junctica and a gate were tested. All operations were executed correctly. Because this test included all neighborhood states occuring during the operation of a modified UCC as described in the previous chapters, the alterations of the transition table are justified.

1. Codd, aEFP, Cellular Automata, Academic Press, New York (1968). 2. Smith, A.R., ITI, FSimple Computation-Universal Cellular Spaces and ^eIf-.Reproduction" Proceedings of the I=E gNinth Annual Vwitchin and =automata Theory S m osium, pp. 269-277. 3. Thatcher, J,'I,, Universality in the von Neumann Cellular Model", Technical Report 03105-30-T, ORA, The University of Michigan, 1964. 4, von Neumann, J., "Theory of Automata: Construction, Reproduction, Homogeneity", Part II of The Theory of Self-Reproducing Automata, edited by A.W,. Burks, University of Illinois Press, Urbana, Illinois (1966).

UNIVERSITY OF MICHIGAN 3 9015 03127 2837