THE UN I V E R S I T Y OF M I C H I G A N COLLEGE OF LITERATURE, SICNECE, AND THE ARTS Communication Sciences Program Technical Report VARIANTS OF THATCHER'S ALGORITHM FOR CONSTRUCTING PULSERS S. Hedetniemi ORA Project 03105 under contract with: DEPARTMENT OF THE NAVY OFFICE OF NAVAL RESEARCH CONTRACT NO. Nonr-1224(21) WASHINGTON, D.C. administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR August 1964

RESEARCH PROGRESS REPORT Title: "Variants of Thatcher's Algorithm for Constructing Pulsers," S. Hedetniemi, University of Michigan Technical Report 03105-29-T, 14 August 1964; Nonr-1234(21), NR 049-114. Background: The Logic of Computers Group of the Communication Sciences Program of the University of Michigan is investigating the application of logic and mathematics to the design of computing automata. The detailed working out of the von Neumann growing automata design forms a part of this investigation. Condensed Report Contents: The background material for this paper is John von Neumann's "Theory of Automata: Construction, Reproduction, Homogeneity" [Part II of The Theory of Self-Reproducing Automata, edited by Arthur W. Burks; to be published by the University of Illinois Press]. Within the framework of his cellular automata, von Neumann presents an algorithm for constructing a class of organs, called pulsers, which function as follows. When given an input pulse at time t, a pulser will, after a specified time delay, At, produce at time t + At, one arbitrarily specified output sequence. A pulser behaves in this manner like a one-input-one-output encoder. James Thatcher, in his paper "Universality in the von Neumann Cellular Model" [to be published as an IBM Research Report], presents another algorithm for constructing pulsers which is far simpler than von Neumann's to apply, but is less efficient in the sense that the pulsers produced are larger in size and have longer time delays than those produced by von Neumann's algorithm. This paper contains several algorithms which, while retaining much of the simplicity of Thatcher's algorithms, produce pulsers that are smaller in size and shorter in delay than those produced by either von Neumann's or Thatcher's algorithms. For Further Information: The complete report is available in the major Navy technical libraries and can be obtained from the Defense Documentation Center. A few copies are available for distribution by the author.

1. THE PROBLEM Design a simple and efficient algorithm for constructing pulsers for arbitrary (output) sequences of the form (x ='cx 1. 2 ( = 0 ), (1) and in particular for those sequences of the form = lk 1...lk 1 (k = 0, 1 2 (2) where the k. denote strings of k. consecutive zeros. The algorithm will be 1 1 simple if it is easy to understand and easy to apply. It will be more efficient than another algorithm if the pulsers it constructs are smaller in area and have shorter delays, between input stimuli and output sequences, than the pulsers constructed by the other. 2. THATCHER'S ALGORITHM FOR CONSTRUCTING PULSERS An algorithm for constructing pulsers far simpler than the one given by von Neumann [1] is proposed by James Thatcher [2]; the details of Thatcher's algorithm are presented in this section. For a sequence CX having the form (1) construct, or iterate, p - 1 copies of the block of Fig. 1, followed by one copy of the column of Fig. 2. * U * 1 U * U *. U 1 2 ~. C C a C + C +., C C Fig. 1 Fig. 2 Fig. 3 The pulser so produced will have the form of Fig. 3, with input a and output b, and will contain p confluent cells ( C I ) above each of which is an, as yet, unspecified cell marked with an asterisk and a number ( *. ). The construction -1

th of the pulser for OC is then completed by changing the i cell marked with an asterisk to either an unexcited cell ( U ) or an ordinary transmission-up cell ( + ), depending on whether the ith symbol of o(, cJi. is a 0 or a 1, respectively. 3. VARIANT I OF THATCHER'S CONSTRUCTION With Thatcher's construction the pulser for an arbitrary sequence of length p has at least p - 1 unexcited, and therefore'unused', squares ( U ). It is, therefore, natural to ask whether an iterative scheme could be developed, along similar lines, which would make more efficient use of the cells within (the bounds of) the pulser, thereby producing a pulser with a smaller area and, perhaps, with a shorter delay. One such scheme is presented in this section. Initial Step For sequences having the form 1 = lki 1 (k = 0 1,2,... where k. denotes a string of k. consecutive zeros, construct for the following values of k. the corresponding pulsers with input a and output b: + I b k. = 0 U a | C _ C'" + +' + b k. =1 U U U + a C C - C -2

4. + - -* + + lb k. =,3 + U U a C t + C -1 C +.e. +. + | b k. = 2m. m m > 1 ~. ~ a C C m blocks, each having the form = 4. 4. + 4. 4. O 4.+ I 4 b k. = 2m + 1 a U: m >2 C C m blocks, having the same form as above, the last two of which are separated by the column marked with the asterisk. General Step For sequences having the form d' = klk lk 1 all one has to do is merge, or identify, the last column of the pulser P(lkl 1) with the first column of the pulser P(lk2 l)o Notice that since all the pulsers -3

constructed in the initial step have identical first and last columns, the last column of P(lkl 1) is the same as the first column of P(lk2 I), and thus the merging of these two pulsers can be accomplished quite naturally. For sequences having the form (2) above, = l1 lk2 1.. lk 1 the process of merging generalizes very simply, ioe. P(lkl k2 1... lk 1) is I 2 n the result of merging serially, or in sequence, P(lkl 1), P(lk2 1),.0., P(lk n- 1) and P(lkn 1). For sequences having the form = k0, i.e. those having initial zeros, all one has to do is construct a path of delay k before (to the left of) the first confluent square of P( (). This can be done easily and in any of a number of ways. 4. END PULSERS - TYPE I This section contains an algorithm for constructing a class of pulsers, called end pulsers. The algorithm, however, is not iterative. That is, it is not possible to merge the end pulser for a sequence 1k 1 with the end pulser for a sequence lk2 1 to obtain an end pulser for the merged sequence lk 1k2 1. The construction of end pulsers only applies to sequences of the form 1k. l. However, this construction can be applied to the end subsequences, 1k 1, of sequences of the form (2). That is, if the end pulser for the sequence 1k 1 is merged with the Variant I pulser for the sequence lkl k 1. o lk 1 the 1 2 n-l' resulting pulser for the merged sequence lk 1k 1.lk2 o 1k lk 1 will have a smaller area and a shorter delay than the corresponding Variant I pulser for the merged sequenceo The algorithm for constructing Type I end pulsers follows. -4

For sequences of the form lk 1 construct for each value of k the n n corresponding pulser: I__~> [ b k = 0 (as in Sec. 3), + U; a C + C +-+ l b - T b k =, 1+; k 2, n n a | C + a C C C- -* +... [ b t - 4-. 4- 4 - k 2m + 1 a n a m 1 aI _+ _+ ___ m columns, each having the form indicated; _ -+ * ~ ~.. b k = 2m n a m 2a C m - 1 columns, as above. Notice (Table 1) that for k ~ 2 the width of Pe (lkl 1) is exactly n - half the width of P(lk 1). -5

Sequence Thatcher Variant I Type- I lk 1 Pulser Pulser End Pulser n k + 2 k even 2k + 3 k + 2 n n n n k + 3 k odd 2k + 3 k + 3 n n n 2 Table 1 Widths of the various pulsers. 5o EXAMPLES The following diagrams of a von Neumann, a Thatcher, a Variant I pulser and a Type I end pulser, for the sequence OX = 10010001, illustrate some of the differences between the various algorithms. von Neumann Pulser + + | + + b t U + U C t U T -- - - - -, ~~~delay 15 ~ U t+ + area 355 t a t C - C al C + C ^ C Thatcher Pulser U~ 1 ~U~ ~U U 1 ur UU U ~ delay 19 -- -- -- -- -- -- -- -- -- -- -- -- -- —'.area 45 a |C | C | C | C C C | C i C | C -6

Variant I Pulser i| b + -+ + + + -+ + + b ~ + + + U U + delay 13.-. —--—.-.. —. —-- area 27 aI C i+ C + C - C Variant I Pulser with Type I End Pulser -+ -_ _ _ _ | b a 4| C =delay 10 area 18 a |C C C - t 6. VARIANT II OF THATCHER'S CONSTRUCTION We can modify the Variant I algorithm slightly and in so doing obtain, in a uniform manner, pulsers with shorter delays and sometimes (depending on the sequences) smaller areas. Figures 4 and 5 illustrate, for the sequence OC = 100001, the basic differences between Variant I and Variant II pulsers (to be constructed). - 4 + -- [+ b1 + L- + + I + |[ b t 4, t a c 4, C + - + + |+ a2 I C + + + -| C a1 C t + C U - + + t U Fig 4 Variant I Fig. 5 Variant II Notice (Fig. 5) that, by moving the input a2 to the middle row, the delay of the Variant II pulser is decreased by one time unit. In addition it -7

is possible to modify this pulser to produce the Variant II pulser for the sequence O0' = 1000001 simply by changing the cell marked with an asterisk to a confluent cell. The modified pulser has the same area and same delay as the original Variant II pulser. Yet it is not possible to modify the Variant I pulser to produce a pulser for the sequence OX5 without increasing both the area and the delay. Thus for the sequence oi? the Variant II pulser will have a smaller area and a shorter delay than the corresponding Variant I pulser, The details of the construction of arbitrary Variant II pulsers follows. Initial Ste For sequences having the form 3 = lk. 1 construct for the following values of k. the corresponding pulsers with input a and output b: -" +* - b k. = 0 a |C | C U U U k. =1 a IC + U C i U + + + U L-+'+I b k. =2 a | C C U + + U -8

-6OA oq' se UIOJ GUres a9q% DuTA'q'S'sDoTq u - u D 1 l, I tD =; n2 - + O ftl i U c' + 16 J t'I ~ 9 = 1 <-J~~~ t qj ____ _ _ _ _j G. ~=~= =~ _' 3 _ ~ 3 + + + + + 9 ='| 4- c l At | } f -t 1 T =, - fLT'L I D l - I C I D I | 4- - 4- 4- 40 I + 0 + 0 H T m

General Step The general step, very much like that of the Variant I algorithm, involves a process of merging pulserso Notice again that all the pulsers constructed in the initial step have identical first and last columns so that the merging of two pulsers can be accomplished very easilyo 7. END PULSERS - TYPE II In the same way that Variant I pulsers were modified to obtain Variant II pulsers, Type I end pulsers can be modified to obtain Type II end pulsers, That is, when constructing the Variant II pulser for the sequence \< = lk 1lk2 1... lk lk 1 1 2 n-1 n merge P(lk1 lk2 1... lk 1) with one of the following class of pulsers, Pg (lkn 1), depending on the value of k: El —' n n k = O (as in Sec. 6), a C C k = 1, a | C | k l t k = 2, C n C -10

+ -- + lb k = 4, a C n C +- | | ->.. ~ >'> I b k =~2m+l a [ C + + + + + l kn 2m +1, a C | 4 T |- *n 4' m > 2 + + -+, m - 1 columns having the form indicated |y -> | > >... ->* ** - I b k = 2m a C + < +... - - n m > 5 + +.- o. + C m -1 columns, as above For Variant II pulsers the width of P(lk 1) is almost twice the width of P, (lk 1), for k > 5. The construction of Type II end pulsers is also not iterative. -11

80 END RJLSERS WITH ADJACENT CONFLUENT CELLS By taking advantage of the fact that two confluent cells may be adjacent to each other, neither of which may feed or receive stimulations from the other, we can construct an even better class of end pulsers which can be merged with the ends of Variant II pulsers. For an end sequence 1k 1 construct for the values of k the corresponding pulsers: -> -> | b -> b k = 0 a C C k = 1, a| C t n n U U U t |- | b -+ -+ -+ | b k =2, a C k =5 a| C t -; n n - C - -+ t k = 4, a C t+ - 3 C For kn ) 5 we present the construction somewhat differently. Let us letter n the following six blocks: - -4 - -+ C -L 4 C C C C,C - 4 C - -. C C a b c d e f For the following values of k construct the corresponding sequences of blocks: -12

k = 5 + 6m a(cd)me 6 + 6m: (dc)mcf 7 + 6m b(dc)mde 8 + 6m ac(dc)mf 9 + 6m b(dc) e 10 + 6m b(dc) +lf For example, the pulser for 1k 1, where k = 11, is _ C C + b a | CC < C a C > C + a c d e And as another example, the pulser for 1k 1, for k = 15, is n' n -^ ^ C -^ C a a b + + C + C + + b -a + C + C -+ + b d c d c e 9. SUMMARY The following two tables provide comparisons of all of the algorithms for constructing pulsers, for the class of sequences of the form 1k 1. [Notation: Pe (CC) - End Pulser with Adjacent Confluent Cells; P (II) - Type II End Pulser; P (I) - Type I End Pulser; P(II) - Variant II Pulser; P(I) - Variant I Pulser.] -13

AREA k 0 1 2 53 4 5 6 7 8 9 10 11 12 15 14 Pulsers P, (CC) 9 6 6 9 9 9 121121215 15 1518 1818 P~ (II) 9 6 6 9 9 12 1215515 1818 21212424 P (I) 9 6 9 9 912 1215 15 18 18 21 212424 P(II) 9 15 12 12 18 181824 245050566 4242 P(I) 9 15 12 18 18 21 24 270 33 36 39 42 45 48 von Neumann 6 12 12 15 18 21 24 27350 33 36 39 424548 Thatcher 9 15 21 27 33 394551 57 65 69 7581 87 9 DELAY k 0 1 2 3 4 5 6 7 8 91011 121314 Pulsers P (cc) 6 5 5 6 6 6 7 8 7 9 9 1011 10 Pa (II) 6 5 5 6 6 7 7 8 8 9 91010 1111 PI (I) 7 6 7 7 7 8 8 9 9 1010o 11 112 12 P(II) 6 9 7 7 9 9 9 11 13115 15 11717 P(I) 7 9 7 8 10 10 1112 13 14 1516 17 18 19 20 von Neumann 6 8 8 9 10 11 12 13 14 15 16 17 18 19 20 Thatcher 7 9 113 15 117 19 21 25 25 27 29 31 5 55 Notice that, oddly enough, although different in appearance (for kn 4) the von Neumann and Variant I pulsers, for the sequences 1k i^ have identical areas -14

and identical delays. Figures 6 and 7 indicate the similarity of these two classes of pulsers for the case k = 5.' - I 1 I b - ~+ |b t U C t + t t + 4 + U. + al C + C al C + r C + C Fig. 6 von Neumann Pulser Fig. 7 Variant I Pulser -15

References [1] von Neumann, John, "Theory of Automata: Construction, Reproduction, Homogeneity." Part II of The Theory of Self-Reproducing Automata, edited by Arthur W. Burks. To be published by the University of Illinois Press. [2] Thatcher, James W., "Universality in the von Neumann Cellular Model," to be published as an IBM Research Report, September 1964, -16

DISTRIBUTION LIST (One copy unless otherwise noted) Technical Library Naval Electronics Laboratory Director Defense Res. & Eng. San Diego 52, California Room 3C-128, The Pentagon Attn: Technical Library Washington, D.C. 20301 Dr. Daniel Alpert, Director Defense Documentation Center 20 Coordinated Science Laboratory Cameron Station University of Illinois Alexandria, Virginia 22314 Urbana, Illinois Chief of Naval Research 2 Air Force Cambridge Research Labs Department of the Navy Laurence C. Hanscom Field Washington 25, D.C. Bedford, Massachusetts Attn: Code 437, Information Attn: Research Library, CRMXL R Systems Branch U. S. Naval Weapons Laboratory Director, Naval Research Laboratory 6 Dahlgren, Virginia 22448 Technical Information Officer Attn: G. H. Gleissner, Code K4 Washington 25, D.C. Asst. Dir. for Computation Attention: Code 2000 National Bureau of Standards Commanding Officer 10 Data Processing Systems Division Office of Naval Research Room 239, Building 10 Navy 100, Fleet Post Office Box 39 Washington 25, D.C. New York, New York 09599 Attn: A. K. Smilow Commanding Officer George C. Francis ONR Branch Office Computing Laboratory, BRL 207 West 24th Street Aberdeen Proving Ground Maryland New York 11, New York Office of Naval Research Office of Naval Research Branch Branch Office Chicago Office 230 N. Michigan Avenue 495 Summer Street Chicago, Illinois 60601 Boston, Massachusetts 02110 Commanding Officer Naval Ordnance Laboratory ONR Branch Office White Oaks, Silver Spring 19 1030 E. Green Street Maryland Pasadena, California Attn: Technical Library Commanding Officer David Taylor Model Basin ONR Branch Office Washington,D.C. 20007 1000 Geary Street Attn: Code 042, Technical Library San Francisco 9, California

DISTRIBUTION LIST (Concluded) The University of Michigan Lincoln Laboratory Department of Philosophy Massachusetts Institute of Technology Attn: Professor A. W. Burks Lexington 73, Massachusetts Attn: Library National Physical Laboratory Teddington, Middlesex, England Office of Naval Research Attn: Dr. A. M. Uttley, Supt. Washington 25, D.C. Autonomies Division Attn: Code 432 Commanding Officer Kenneth Krohn Harry Diamond Laboratories 6001 Dunham Springs Road Washington, D.C. 20438 Nashville, Tennessee Attn: Library Mr. Laurence J. Fogel Commanding Officer and Director General Dynamics/Astronautics U. S. Naval Training Device Center Division of General Dynamics Corp. Port Washington San Diego, California Long Island, New York Attn: Technical Library Department of the Army Office of the Chief of Research and Development Pentagon, Room 3D442 Washington 25, D.C. Attn: Mr. L. H. Geiger National Security Agency Fort George G. Meade, Maryland Attn: Librarian, C-332

UNIVERSITY OF MICHIGAN I 01 11115 03026 8026 3 9015 03026 8026