THE UNIVERS ITY OF MI C H I GAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Communication Sciences Program and Logic of Computers Group Technical Report CYCLES IN LOGICAL NETS John H. Holland UMRI Projects 2722. And 2794 under contract with: National Science Foundation U.S. Army Signal Supply Agency Washington, D. C. Laboratory Procurement Support Office NSF Grant - G-4790 Fort Monmouth, New Jersey Contract No. DA-36-039-sc-78057 administered by: THE UNIVERSITY OF MICHIGAN RESEARCH INSTITUTE ANN ARBOR August 1959

PREFACE My curiosity concerning systems having complex patterns of feedback was first aroused during an earlier study of the action of the central nervous system (Rochester, N., J. H. Holland, L. H. Haibt, and W. L. Duda, "Tests on a Cell Assembly Theory of the Action of the Brain, Using a Large Digital Computer", I R. E. Transactions on Information Theory, IT-2,3: 80-93 (1956)). The possibility of studying feedback by means of an abstract deductive system was first suggested by a remark occuring in a paper by Arthur Burks and Hao Wang (Burks-Wang [ll, p. 292; references are numbered in alphabetical order in Part 7 of this paper). The present paper indicates some effects of complex feedback patterns upon the behavior of an abstract class of discrete systems (logical nets). I hope that the study will suggest some properties and points for investigation of feedback in more general systems, I would like to thank the Logic of Computers Group at The University of Michigan for providing the opportunity to carry out this research and for discussions with its other members, especially Arthur Burks and Jesse Wright, on many topics related to this paper. I would also like to thank Arthur Burks for his help in reading the first draft of this paper. The possibility of presenting this thesis within an appropriate framework is one result of the efforts of the Committee on Communication. Sciences in establishing the Communication Sciences as a discipline in their own right. The steps in carrying the original manuscript to an approved final form were nicely handled by Ruth Lewis. ii

The funds for this study were supplied from grants to the Logic of Computers Group by the Signal Corps (DA 36-039 SC-78057) and the National Science Foundation (NSF-G4790). John H. Holland Ann Arbor March, 1959 iii

CONTENTS Preface.. * *. * * * e. ii 1. Introduction.. *. *. e. 1 2. Underlying Concepts.. *.. e - 3 5. Simple Cycles........12 4. Input-Independent Cycles. e. o 21 5. Cycles in General....... 48 6. Comments and Conjectures,,.... 55 References * e *. e.. o 58 Index of Definitions, Symbols (first appearance), and Theorems. 59 iv

FIGURES Fig. 1 Truth Table of a k-input Switch o c o 3 Fig. 2 A Logical Net with Cycles Marked. Fig. 3 A Cycle and its Normal Form o o. 7 Fig, 4 A Cycle and an Equivalent Normal Form with D1-1 ood n Dj nmod 8 Fig. 5 A Cycle and its Transition Graph.. 10 Fig. 6 Normal Form of Simple Cycle... e 12 Fig 7 An N.C-Net, 16 Fig. 8 A Locally-Balanced Cycle and the Truth Table of its Switch o 2 a. 22 Fig. 9 The Derived Transition Table of a LocallyBalanced Cycle o e 23 Fig.10 Effects of Inversions on the Transition Graph of a Locally-Balanced Cycle 29 Fig,1l A Switch Properly of Order 2 o o. 55 Fig,12 Derived Transition Table for a General Cycle with Input.. o o o o I o c 49 Fig.13 An Example of the Selection of GI(t) by the Input-State I(t). e.50 V

1. Introduction Feedback is a pron-,i.nent structural f"t.ature of most systems which exhibit complex behavior, In fact, some systems are actually defined in terms of the role feedback is to play. It is not simple, however, to see just what conditions a given feedback pattern imposes upon a system's behavior. The problem is an example par excellence of an important class of problems arising in the investigation of automata - the class of analysis problems. The object of the usual analysis problem for automata is to derive from selected structural features of a system - feedback patterns in the present case - conditions on the system's behavior. The customary way to begin the analysis is to make a suitable abstraction of the systems involved; that is, the analysis procedure is defined over some broad class of abstract systems. If this is done properly we achieve the important result that statements about the structure logically imply statements about system behavior, Deductions about behavior will then hold true of any system (concrete or abstract) for which the structural statements hold. It is the purpose of fhis paper to study feedback by using the riethods of logic in this way, The study will be carried out by using the theory of logical nets to abstract the structural and behavioral properties of interest (Burks - Wright [2], Burks - Wang [1]). Thus the study will apply mainly to systems for which (at least as an approximation) time can be considered discrete and the structure as well as the number of states fixed and finite. Within this formalism structure will be represented 1

2 by the logical net diagram or the corresponding set of recursive equations. Feedback loops will be represented by cycles in the net diagram. The behavior of the logical net will be associated with properties of the state transition graph or the corresponding transition matrix. The form of this graph can in general be deduced from the recursive equations describing the structure. Thus the theory of logical nets satisfies the criterion of being able to make deductions about behavior from structural statements. Two kinds of behavioral properties will play an important part in the development. Properties of the first kind depend upon the fact that the net-state sequence of a logical net is periodic if its input-state sequence is periodic (Burks - Wright [2], Theorem I). Properties of the second kind deal with various characteristics of state cycles in the state transition graph. Relating changes in these two kinds of properties to changes in the complexity of structural cycles will be one of the specific objectives of this paper. The overall purpose of the paper will be to produce an integrated series of definitions and operations useful for both formal and experimental investigations of the behavior of discrete systems with feedback.

2. Underying Concepts The theory of logical nets now has a fairly large literature and there etist several alternative formulations of its basic ideas (compare, for example, Burks - Wright [21, Kleene [4], Moore [6], Mealy [5], Burks -Wang [1], Copi- Elgot - Wright [3]). Thus most of the concepts underlying this particular study have several alternative forms. In this section, I will give a brief sketch of the form used here and then cite a paper containing the detailed development. In addition, whenever one of the underlying concepts is not in the literature, or when a new variant is required, the complete definition will be given. The logical nets considered in this paper will be constructed of two types of elements - switching elements and delay elements. Each switching element has a fixed number, k X 1i, of inputs and each delay element has exactly one input; each element has exactly one output. At any moment of time, t = 0,1,2,..., each input and each output has just one of two states associated with it: 1 ("active") or 0 ("inactive"). For a given k-input switch let the state of the output at time t be q(t). Let the state of the Ith input at t be Pi(t). Then each of the 2k ordered k-tuples (po(t), pl(t),...,Pk_2(t), Pk- (t))will be an argument for which q(t) is uniquely determined. Hence q(t) can be presented by means of a truth table with k argument columns and 2k rows: po(t) *.* pk-2(t) Pk_l(t) q(t) 0..e 0 co 0 e 0 1 C1 0... 0 ~2 1 *.. 1 1 E2kl Fig. 1 Truth Table of a k-input Switch 5

4 The output state of a delay element at time t is Just the state of the input at time t - 1. This infinite class of primitive elements is essentially that discussed by Burks and Wang in part 2.3 of their paper, "The Logic of Automata", [1]. Logical nets will be constructed from the elements by identifying (connecting) the outputs of some elements with inputs of others. Thus, if an input pj is identified with an output qj, the state of p. is identical at all times with the state of qj: pi(t) = qj(t). Element inputs not identified with element outputs in the constLr-ction process will be called net inputs. An element input which is not a net input will have its state determined at each moment by the element output with which it is identified. The state of a net input, on the other hand, is not determined by any of the net elements and must be assigned arbitrarily at each time t. The output state of each element is determined, of course, as indicated in the previous paragraph. This paper will be concerned only with well-formed nets as defined by Copi, Elgot and Wright in part 4 of their paper, "Realization of Events by Logical Nets", [] (or, essentially, as defined by Burks - Wright [2]). Well-formed nets. can be characterized briefly as nets satisfying the following two conditions: 1) the net contains no subcycle (definition to follow) consisting only of switching elements, 2) no two distinct elements of the net have their outputs identified. As indicated in the introduction, the purpose of this paper will be to investigate the role of cycles in logical nets, The exact definition of cycle proceeds from the concept of one element of a net

5 driving another. An element E1 directly drives an element E22 E lE29 if and only if the output of Eg is identified with one of the inputs of E2. A sequence of elements F,...,Fn is a drive sequence from F to Fn if and only if Fjd Fj+ for j = l,...,n-l. An element E1 drives an element E2, EiD E2, if and only if there is a drive sequence from E1 to E2. Now, an element E1 belongs to a cycle if and only if ElD E1. This cycle consists of the set of all elements, Ej, such that both Ej Ej and EjD E1. Or, more formally a set of elements, C, in a net is a cycle if and only if, for all Ei, Ej in C, (1) Ei Ej and EjD Ei and (2) no element of the net not in C satisfies condition (1). A set of elements, C', is a subcycle if and only if, for all Ei, E3 in C', (1) EiD Ej and EjD Ei and (2) for each relation EiD Ej of (1) all elements of the defining drive sequence are elements of C', It is an immediate consequence of these definitions that each element of a net belongs to at most one cycle, although it may belong to several subcycles, MLT INPUTS h. h, 1ht ht....I i1 -. — 7~,^ [. _ r~~~!- - - J - t _ 0 t j. -I - S-R NmS I I L_ _.... CLCE, RANK 0 ----—. I ~CYCL~E I r.. J- NCYCL.SE.-. ANHY O L..J SOUBCYCLFig. 2 A Logical Net with Cycles Marked

6 Note that the cycles in a well-formed net can be ranked as follows: A cycle is of rank 0 if none of its inputs is driven by an element of another cycle. A cycle is of rank r if at least one of its inputs is driven by an element of another cycle of rank r-1 and none of its inputs is driven by elements of other cycles of rank greater than r-l. Each cycle can be reduced to a normal form which has at most one switch'between" each delay and its "predecessors". We can arrive at this normal form in the following way: A drive sequence in which all elements, other than the first and last, are switches will be called a drive sequence of switches. If there is at least one drive sequence of switches from an element E1 to an element E2 it will be said that E1 drives E2 via switches, E1 s E2. The set of all switches belonging to drive sequences of switches from E1 to E2 will be called the set of switches from E1 to E2. Since we are dealing with well-formed nets and since the delay D2 has but one input, there must be one and only one switch output identified with the input of D2 when D1 s D2 (excluding the case D1 d D2). The set of switches from D1 to D2 will have a total number, k, of inputs, PO0..Pk-1l which are not identified with the output of any other switches in the set or with the output of D1. It can easily be seen that each assignment of states to these k switch inputs uniquely determines the input state of D2 when the output state of D1 is given. Thus we can replace the set of switches from D) to D2 by a single k + 1 input switch with k inputs identified in just the same way as the k switch inputs, pO,..<.Pkl~ and the other input.identified with the output of D]. The output of this

7 swlitch is then identified with the input of D2. Consider now the complete set of delays belonging to a given cycle. Let the delays be ordered and labelled, Do, Dl**,.,Dnl (preferably with the relation Dj.1 s Dj holding for as many delays as possible). For each given 3, consider all Di in the cycle such that Di s D.. (There must be at -J least one such Di, otherwise D; would not be a member of the cycle.) Among all the switches belonging to one or more of the sets of switches from Dil to Dj, from Di2 to Dj,..., or from Dji to Dj, there will be a total of k switch inputs not identified with the output of any other element of these sets or with the outputs of Dil, Di2'.*,Dime Now, in just the same way as before, a single k + m input switch can be constructed to replace the given switches. Of the inputs to this new switch, k will be identified just as the k selected inputs of the given switches, and the other m will be identified with the outputs of Dil...,Di. The output of the new switch will be identified with the input of Dj. Once this is done for each Dj, the normal form of the cycle results, - I. -- 0. DM A De, A C ~ CYCLE NORMAL FORM r - ~- E&NCLOSES SWITCHES L -J FROM D, TO O, Fig. 5 A Cycle and its Normal Form

8 It is an immediate consequence of the construction method that the normal form of any cycle with n delays will have no more than n switches. Furthermore, each cycle input (the net inputs of a cycle when it is taken as the whole net) of the original cycle will drive via a switch exactly the same delays in the normal form as in the original form. Finally, at any time t, the input and output state of each delay in the normal form will be that of the same delay in the original form. Note that we can always, at least formally, obtain a normal form of a cycle in which Djlnodn s Dj mod n for all J.'bdo this, when Dj_1 mod n L Dj mod n in the given cycle, simply add an additional input to the switch constructed by the earlier method. The action of the switch is to be independent of this new input, i.e., the output of the switch is still uniquely determined by the k + m inputs initially obtained. However, formally we have a k + m + 1 input switch and can identify the output of Dj_l od n with the newly added input. This modified normal form will simplify some of the proofs to follow. d. cl~ 2^ O d it 4 o 90 X0 O ( OG 0 o0. 0 0 $. S 1 0 t I 1i 5 q (t) a f( (t) q (t) f(dt)) Fig. 4 A Cycle and an Equivalent Normal Form with Dj_l mod n s Dj mod n

9 The definitions and discussion up to tllis point have been concerned with the structure of logical nets. The remainder of this section will concern the state-transition graph and behavioral properties of logical nets. At a given time, by knowing the output state of each delay element in a net together with the state of each net input, one can determine the state of every element input and output of the net. That is, a complete description of the state of the net at any time can be obtained from knowledge of the net structure and the current states of the net inputs and delay outputs. Now, let us assume the net has k > 0 net inputs. To each of these net inputs, one of two states can be assigned at each time t; thus there are 2k possible distinct assignments, of which one is to be chosen at each time. Any such assignment will be called an input state. If the net inputs are ordered and labelled, say hoA,..,hkl - and throughout the paper this will always be assumed the case - we can represent each input state by a k-tuple of ones and zeros. The delay outputs, ordered and labelled, can be treated in a similar way, the result in this case being called a net state. (See Burks - Wang [1] or Copi - Elgot - Wright [3] for detailed versions.) The state-transition graph, as a means of picturing the behavior of a logical net, is made possible by the following fact: The net state succeeding the net state present at a time t is determined by the input state at time t. (If there are no net inputs each net state has a single invariant successor.) This transition from net state to net state under the influence of successive input states is the basic behavior of the logical net. The state-transition

10 graph exhibits the possible transitions and the input states (or input state successions) which accomplish them, Assuming the net has n delay outputs, there will be 2n vertices to the graph, labelled to correspond to the 2n net states. An edge connects vertex g to vertex Sj just in case one or more input states, lIhl, cause a transition from Si at tine t to Sj at time t + 1; the edge is labelled with the set [Ih) (cf. I'Soore [6]). ho -o o o 1,. vZ-i5 IV (l.-o) 0! 0 1 ~ 0! I I 0 Fig. 5 A Cycle and its Transition Graph Let a sequence {S(t)) be said to have a period p if and only if, for all t greater than some positive integer a, S(t) = S(t') if t 5 t' mod p. If there is no p' < p for which the precedirg statement holds then the state sequence will be said to have a proper period p. A property of logical net behavior which plays a considerable role in parts of this paper can now be stated: If a net's input state sequence is periodic, then the net state sequence will also be periodic (cf. Burks - Wright [2] Theorem I). The result follows from the observation that, if the input states recur with period m and there are 2n net states, the net state/input state comibination occuring at

11 any time t m.2n must repeat at t + cm, for some c < 2n. Therefore the net state at time t + c.m+l must repeat the net state at t+1 (since each is uniquely determined by the same preceding net state/input state combination); and the input state at t+c-m+l must repeat the input state at t+l (since both occupy the same relative position in the periodic input sequence, i.e., t+l = t+c-m+-l mod m); etc. for t+cm+2, t+cm+3,,e.. Thus the net state sequence has a period cm. Often when studying the behavior of logical nets it will prove useful to relate the spectrum of input state proper periods to a resultant spectrum of net state periods (not necessarily proper).

3. Simple Cycles A hint of the role of cycles in logical nets comes from the following observation: For a net with n delays and no cycles, the net state at time t is totally determined by the sequence of input states from t-n to t-l - the net state at time t is completely independent of any net state preceding time t-n+l, Thus a net without cycles can only record the detection of an input event for at most n time-steps. In other words, if a logical net is to have 1"memory" or storage it must include cycles. Upon noting the function of cycles as memory elements, one of the first questions which presents itself is: Can the full range of logical net behavior be? obtained from nets using cycles of limited complexity? More precisely, in the class of well formed nets, is there a proper subset, defined in terms of some limitation on the cycles allowed, which can exhibit the full range of logical net behavior? It is fairly obvious that the number of cycles cannot be limited; this would contradict the existence of nets with arbitrarily large numbers of memory units, A possible first step would be to consider nets using only cycles with minimal feedbacks ie,, cycles with no proper subcycles. A cycle of this type. which I will call a sple cyl cljan be directly defined as a cycle in which each delay drives via switches exactly one other delay in the cycle. The normal form of such cycles is particularly s iplep d90 4 0 Fig. 6 Normal Form of Simple Cycle 12

13 The conjecture, then, with respect to simple cycles would be that for each logical-net there is a net with, at most, simple cycles which behaves the same. The conjecture is plausible on the view that the simple cycles provide "delay line" or "reverbratory" storage of various periods while the rest of the net provides encoding, switching, decoding, and other logical operations. Theorem 1. If the sequence of input states of a simple cycle has a proper period m and the simple cycle has n delay elements, then the sequence of net states of the cycle has a proper period 2 l.c.m.(m,n) or a divisor thereof. Proof: 1) Let I(t) be the input state to the simple cycle at time t. Let Ij = I(j) be the input state at time t = j, j = 0,l,..,m-l. Then, since the input states repeat with proper period m, I(t) = I. if and only if t - j mod m. 2) Now reduce the simple cycle to normal form and label the delay and switch outputs as in Figure 6. Let Ntitm 3() be the state of the switch output labelled qi od n when its input from the cycle (delay output di mod n) is in state 5 and the net inputs are in state It mod m- If di(n)(t) is the state of delay output di mod n at time t, then for any i t(m) di+l(n)(t) = i(n)(t) Ni(n)(di(n)(t)) by the delay equation and definition of Ni. More generally, t+h-1 ra) t+h-2 m di+h(n)(t+h) = Ni+:h-1 nNi+h2 ha. Nti (di(n)(t))Letting b0 = l.c.m(m,n) we have di+b(n)(ttho) = di(n)(t+ho) = Nbl i3 * **iNtE(di(n)(t))

14 t-l(m) t-2(m) t(m) = Ni-l(n)Ni-(n)*Ni(n (di(n) (t))) since bo mod n = bo mod m 0, Letting T = Ntltn —- eNttmn it follows that di(n)(t+kbo) = T(di(n)(t+(k-l)bo)) = T T(di(n)(t+(k-2)bo)) = Tk(di(n)(t)) Note that successive applications of the operator T give the states of delay output di mod n at times t, tt+boj t+2bo etc. Furthermore, if T(di(n)(to)) = di(n)(to), for some to, then by definition we must have T(di(n)(tO+bO)) = T(di(n)(to)) = di(n)(tO) since di(n)(to+bo) = T(di(n)(to)) n)( t)) )(to). In other words, T2(di(n)(to)) = di(n)(t) and, in general, Tk(di(n)(to)) = di(n)(to), once T(di(n)(tO)) = di(n)(to) for some too 3) For any given i and t the form of the T operator is fixed and can be given by a table of the following form: 8 T 0 1 T(O) 0"^ T()where T(8) = 0 1 T(1) "1 4) If T(O) = 0, T(1) = 1 then we must have T(di(n(t)) = di(n(t) whatever the state of delay output diod at time t. Hence, Tk(di(n)(t)) = d (n(t) and the state of di mod n at time t must repeat at least every b0 time-steps thereafter. 5) If T(O) = 0, T(1) = 0 then T(di(n)(t)) = O, although for t0 < b0 di (n)(to) may equal 1. However, T2(di(n)(to)) = T(O) = 0. Hence, T(8i(n)(to+bo)) = bi(n)(to+bo) and, again, the state of di mod n) after at most b0 time-steps repeats with period bO. 6) A similar argument holds for T(O) = 1, T(1) = 1.

15 7) Finally, if T(O) = 1, T(1) = O, we have T2(din)(t)) = di(n)(t) and in general T2k(I,(n)(t)) = di(n)(t). Hence, the state di(n)(t) repeats with period 2b0 in this case. 8) The full argument obviously holds for any t and any i. Thus the state sequence of each delay output in the cycle and hence the net state sequence repeats every 2b0 unite of time. If 2b0 is divisible by b, it is possible that di(n)(t) = di(n)(t+jb) for all J such that jb * bo and for all i. In such case, the proper period of the net state sequence would be b, a division of 2bo. Thus 2b0 = 21.c.m.(m,n) or a divisor thereof is the net state period of the cycle, irrespective of the switching elements used. 9) Since in T we find for each pair (i,j), i = Ol,.. n-l exactly one occurence of NJ, it is easy to show (by giving the rule for constructing the corresponding truth tables) that there in fact exist switching elements which will yield proper net state period 2bo. In nets constructed with more than one simple cycle there can be subnets having no cycles'between" the simple cycles., The following definitions are intended to give a precise interpretation of this statement. A drive sequence from an element F1 to an element F2 will be called an n.c.-drive sequence if none of the elements in the sequence other than the first and last, belongs to a cycle, A set of elements, A, n.c.-drives a set of elements, B, if there is at least one n.c.-drive sequence from some element of A to some element of B. The net consisting of all elements, other than elements of A and B, belonging to n.c.-drive sequences from A to B is the n.c,-ret from A to B.

I f —- - -- h L —-r 1 —--- i A.....J A TO L -...... A B Fig. 7 An N.C.-Net Theorem 2. If the sequence of input states to a net without cycles (e.g., an n.c.-net) has a proper period m, then the net state sequence of the n.c.-net has a proper period m or a divisor thereof. Proof: 1) In order to simplify the proof let each element in the net without cycles by given a rank as follows: (1.1) if all the inputs of the element are net inputs of the given net, its rank is zero, (1.2) if an input of the element is identified with the output of an element of rank r-l, and no input is identified with the output of an element of rank higher than r-1. then the element is of rank r. Since an n.c.-net contains no cycles each element has a unique rank. 2) Now, the states of the inputs of each element of rank zero must repeat with period m since these states are merely components of the net input state. Therefore, since the output state of a switch is each switch of rank zero repeats every m units of time. The switch may, of course, repeat its output state more m re quently; e.g., the switch output state may be 1 for any input argument, in which case. its output state would repeat with period p = 1. Thus the output state

sequence of a switch of rank zero has a period m or a divisor thereof. It follows directly from the delay equation that the output state of a delay of rank zero repeats every m units of time. 3) If the output state of each element of rank r' C r repeats with period m, then, by the same observations as in the case of rank zero, the output state of an element of rank r repeats with period m, Thums by induction, the output state of any element of a net without cycles repeats every m units of time. Hence, the net state sequence of a net without cycles has a proper period m or a divisor thereof. We can now proceed to the general case with respect to the conjecture mentioned at the outset of this section; that is, the case of nets in which all the cycles are simple cycles. Theorem 3. A net in which all of the cycles are simple, having nl,...,nk delay elements, respectively, with a sequence of input states of proper period m, will have a net state sequence of period 2ro+l l.c.m. (mnP,...,nk), where ro is the maximum of the cycle ranks. Proof: 1) To begin with,note that every element of a net, N, is driven by one or more of the net inputs of N, except those elements belonging to a cycle having no cycle inputs (i.e., the cycle, considered as a net, has no net inputs), 2) Let AO be the set of elements satisfying the following two conditions: (2.1) at least one input of the element is a net input of N, (2.2) the element does not belong to a cycle. Let C be the set of elements belonging to a given cycle of rank 0 (see Part 2). Any element driving an element of C must be driven by an element of A0 because C is of rank 0 and hence no element belonging to a cycle can

18 drive an element of C. Let P be the net consisting of the n.c.-net from AO to C together with the elements of AO. The net includes all elements of N which drive elements of C. Since the net inputs of P are just the net inputs of N, the net state sequence of P must be of period m by Theorem 2. Thus the input state sequence of the cycle inputs to C must be of period m. Since C is a simple cycle the results of Theorem 1 apply - the net state sequence of C has a proper period 2 l.c.m.(mn), or a divisor thereof, where n is the number of delays belonging to C. 3) Now, define inductively a set of nets Nj, for j =-l,0,l,...,ro, where ro is the maximal rank of the cycles in the net N. The net Nj consists of the following elements with their inputs identified as in N: 3.1)1all elements of Nj_1 (where N_1 is the set AO)P 3.2) all elements belonging to n.c.-nets from Nj.1 to cycles of rank j, 3.3) all elements belonging to cycles of rank j. 4) Consider the net N0. If the k0 simple cycles in No have no,...,nkOl delays, respectively, then as shown above the ith cycle will have a net state sequence of period 2 l.c.m.(m,ni), i = O,,,,koEach associated P net will have a net state period m. It follows directly that the proper net state period of No will be a divisor of l.c.m.(m, 2 l.c.m.(m,no),..., 2 l.c.m.(mnko_l)) =2 l.c.m.(m,no,...,nko-l) 5) Let nO,...,nko l.nko,.. n kl-l..,- nkj-. be the number of delays belonging, in order, to each of the simple cycles from rank 0 through rank j.

19 6) Assume the net N j_ has a net state sequence of period p = 2J l.c.m. (mnO...nnk _..l). By substituting Njl for AO and p for m in step (2) we see that a cycle Ci of rank j must have a net state sequence of period 2 l.c.m.(p,ni) = 2 l.c.m.(2Jl.c.m. (mno,...,nkj-l). ni) = 2j+ll.c.m. (mnO,... nkj_l..1,ni) Applying the reasoning of step ~(4) we see then that the proper net state period of N. will be a divisor of J 1. c.m. (, 2j+l. c.m. (mnO0...,nkjl ) 7) Thus by induction on j, the net N, when the input states repeat with period m, will have a proper net state period which is a divisor of r0+1 P = 2 l.c.m.(m,n,...nk). Again, for reasons similar to those noted at the end of Theorem 1, there exist combinations of switching elements and cycles giving N a net state sequence of proper period p. Corollary Let it be required that a net be in a chosen net state SO if and only if the number of occurences, p, of a distinguished input state Io satisfies the equation p E 0 mod j. (Simply, the net is required to "count", modulo j, the occurences of input state Io.) For nets in which all cycles are simple, j must equal 2b for some positive integer b. (Such nets can only "count" modulo a power of 2.) Proof: Let the distinguished input state repeat with a proper period m. Then, since the net is to be in a unique net state SO for each j occurences of the distinguished input state, it must have a net state which repeats with proper period p = jm for all m. Or, by Theorem 3, p == jm = 2 O+ll.c.m.(m,no,...,nk).

20 This equation can only hold for all m if j 2= 2+l1 since if m is chosen equal to k(l.c.m.(nO,...,nk)) the above equation reduces to jm = 2rm+l. If this result is not surprising, it at least shows the oversimplification present in the idea that the main function of cycles in a system is to provide "memory" or storage of information. Here we have systems with any number of cycles of arbitrary lengths (arbitrary recycling times) which have a very limited range of behavior, not because we restrict the complexity of the switching elements used, but because the cycles are limited in the complexity of their feedback patterns.

4. Input-Independent Cycles The results of Part 3 show the behavior of a logical net to be severely restricted if the complexity of the net cycles is sufficiently limited. Moreover, the limitation on complexity need not concern the number of cycles or the number of delays in a cycle, but only the number of feedback loops (subcycles) per cycle. The effect of increasing the number of feedback loops in a cycle thus becomes a salient point of the study of cycles in logical nets. In the present section, I will start out by relating properties of the state-transition graph to changes in feedback in a class of input-independent cycles called locally-balanced cycles. Just as cycles are important features of net structure, so cycles in the transition graph are important to net behavior. To distinguish the two kinds of cycles, I will speak of net cycles and state cycles, respectively. The relation between locally-balanced cycles and the resulting state cycles will be a key to the behavior of more general net cycles. Locally-balanced cycles can be defined in the following way: In the truth table corresponding to a switching element let rows 2j and 2j+l, for j = 0,1,...,2n-1-2, be called simply the jth pair. Let the function values determined by the two arguments of the jth pair be c2j and e2j+l respectively. A switching element will be called locally-balanced if e2j = 2j+l for all pairs, j = 0,1,..., 2n1-2. A locally balanced cycle satisfies the following conditions: 1) One switching element occurs in the cycle and that element is locally-balanced. 2) There are n > O delay elements in the cycle. The output of 21

22 the switch is identified with the input of delay d0. The output of delay dj is identified with the input of delay dj+l, j = =0,,o,n-2. 3) The switch has n inputs. The jth input of the switch (the th column of the associated truth table) is identified with the output of delay dj, j = 0,..., n-l. q~ dO dl.dn_2 d,-_l'o. {ft~do )C d, O... 00 0 ~o 0 o... o 1. 0 0.. 1 0 ~2 0 0... 1 1 E2 1... 1 0 62n-2 1 1... 1 1 EC2nl 2 = 2j+l Fig. 8 A Locally-Balanced Cycle and the Truth Table of Its Switch Theorem 4. The state-transition graph of any locally-balanced cycle consists only of disjoint cycles of states. Proof: 1) Consider, at any given time t, the ordered n-tuple (PO(t)...e Pn-l(t)) of the states of the n inputs to the switch in a locally-balanced cycle. By definition of a locally-balanced cycle, this n-tuple is identified with the ordered n-tuple of delay output states at time t, (do(t),...dn_l(t)). Thus each of the 2n net states of the cycle is represented by the argument part of a line of the switching element truth table. 2) If the net state of the cycle at t is given by the jth line of the truth table, then the net state of the cycle at t+l is simply given by the ordered n-tuple with ej as its first digit and the value

23 of Pi(t) as its i+lth digit. That is: (do(t+l),...,dnl(t+l)) =(~jPo(t),,,p^.2(tn)) where the argument of line j has in effect been "shifted one to the right", ej being "shifted in", Pnl(t) being'hifted out". The truth table, thus extended, becomes derived transition table for the locally-balanced cycle: __s(t) __ s (t + ) do(t)=. d-2 )= n-l(t)= do(t+l) dl(t+l)='s dn-l(t+l)= PO(t) Pn-2(t P-l ) (t) PO(t) pn2(t) O.'-O o D co o..o 0.. 0 0 *0 0 0 *.. 0 1 0 0 O * * 1 1 5 0 *Q1 01 1 0 *.. 1 1 * | 1 2n- 1 | 1 where s(t) is the net state of the cycle at time t. Fig. 9 The Derived Transition Table of a Locally-Balanced Cycle 3) Now, the jth pair of the locally-balanced switch gives rise to a pair of successor n-tuples, s2j(t+l) = (e2jPo(t),. e.Pn-2(t)) and S2j+l(t+l) =(E2 j+lPo(t)-,-l Pn_2 (t)) s2j and 52j+l have identical digits in the last n-l places by step (2); furthermore no other pair of successors has the same ordered set of digits in the last n-1 places. The first digit of s2j is the binary complement of the first digit of 52j+l since E2j = Z2j+l by definition of a locally-balanced switch. Therefore the argument states of the jth pair map into distinct n-tuples, s2j and S2j+l, which occur nowhere else on the right of the derived transition table. In other words, the derived

24 transition table is a 1 - 1 mapping of the 2n net states onto themselves. Such a mapping is a permutation on the net states and, by elementary group theory, pernuations can always be reduced to a product of disjoint permutation cycles. These permutation cycles correspond directly to disjoint state cycles of the transition graph. Note that the state-transition graph of an input-independent cycle consists only of disjoint state cycles just in case the cycle is backwards deterministic in the sense of Burks - Wang [1; p.286]. Using this fact, and noting that ~2j = 2+l imlie we can restate Theorem 4 in a stronger form: Theorem 4'. Let C be an n-delay cycle with one (arbitrarily chosen) n-input switch which is connected just like the switch in a locallybalanced cycle. C will be backwards deterministic if and only if the switch is locally-balanced. In what follows, a pair will be said to be normally oriented if 2j = 0, c2j+l = 1. A pair will be said to be inversely oriented if E2j = 1, e2j+l = 0. The simplest locally-balanced cycles result when the pairs associated with the switch are either all normally oriented or all inversely oriented. When this is the case the output of the switch, q(t), is independent of all argument columns except the last, Pnl(t). Thus in effect the cycle is an input-independent simple cycle. The next theorem gives some properties of the state-transition graphs of these simplest locally-balanced cycles. Theorem 5. Let L be a locally-balanced cycle with n delays. If all the pairs of the switch are normally oriented, a state-cycle with exactly p states occurs if and only if p = 1 or, for p > 1, g.c.d,(p,n)=pt There will be two state-cycles with p = 1 and, for p > 1, there will be

25 2P -2p np = p state-cycles, where p' is the next number smaller than p which is the length of a state-cycle. If all the pairs of the switch are inversely oriented, a state-cycle with exactly p states occurs if and only if g.c.d.(p,2n) = p and p does not divide n. The number of state-cycles having p elements is again given by np. Proof: 1) The sequence of states in a state-cycle C of an n delay locallybalanced cycle can be represented by a binary sequence of the following form: 1.1) the sequence is doubly infinite, 1.2) any set of n consecutive digits from the sequence 5jj+l... *j+nl represents a state sj of the state-cycle C, 1.3) given a set of n consecutive digits, 5j-,j+l6bj+n-_l which represent state s, the set of digits 6j+l, j+2,...S j+n represents the successor, sj', of s. in the state-cycle C. That such a sequence exists follows from the form of the transition table as derived in Theorem 4 (the right-hand entry of a line in the table being related to the left-hand entry just as in condition (1.3) above, but with order reversed). 2) Consider first the case where the switching element in the locally-balanced cycle has all of its pairs normally-oriented. Then in the binary sequence associated with any one of the disjoint statecycles we have 5j =. j+ because, in the derived transition table for the normally oriented case, Pnl(t) = q(t) (see Theorem 4, step (2)). Furthermore, if u is a multiple of the number of elements in the state-cycle then 6j = 6j^u. Finally, if u is the length of a statecycle (and not a multiple thereof) then 65jo 5Jo+uO for each uo0 u and in each case, a Jo < u-uo.

26 3) Combining the three requirements of step (2) we have 3.1) 50 J+u jO+U+uo+Ju = 01... 5.2) 6J = 8jo+n= %Jo+j'n 3 j' 0,1,... These equations can be satisfied if and only if, 3.3) u0+ju /'n, for any uo)u and any J, J' or g.c.d.(U ) / f1or any uou 4) Consider the alternatives (4.1) g.c.d.(n,u) = u and (4.2) g.c.d.(n,u) = u' < u: 4.1) g.c.d.(n,u) = u = n = bu for some integer b,whence g.c.d.(. n = g.c.d. ( P =. for ay ulu; Zuo U1 luo UO U 0o therefore g.c.d.(n,u) = u 4= u is a state-cycle length (and not a multiple thereof), 4.2) g.c.d.(n,u) = u' < u = u'J u 4 for u I u', g.c.d. _, - ) = 1 and therefore the equations (3.1) and 3.2) are satisfied by u' | u, whence u is a multiple of the state-cycle length. 5) Thus, for a locally-balanced cycle with n delay elements and a normally-oriented switch, p is the length of a state-cycle if and only if g.c.d.(n,p) = p. That is p must be a factor of n. 6) In order to determine the number, np, of state-cycles,of length p we note that there are 2P binary sequences of length p. However, 2P of these sequences will have been assigned to cycles of length p' or divisors thereof, where p' is the number next smaller than p such that g.c.d,(p',n) = p' or, in other words, p' is the next smaller statecycle length. Therefore there are 2P - 2P binary'sequences which correspond to state-cycles of length p. However, for each state-cycle of length p there are p binary sequences which represent the cycle

27 (obtained by shifting any one representative j places to the right, for 0 4 j < p). Thus n = -2P P P 7) For the case with all the pairs of the switching element inversely oriented the proof procedure is much the same except that 5j = Fj+n in this case. Thus equation (3.3) becomes UO +ju / n + j'2n, for any uO u and any j,J'. This equation is satisfied if, and only if g.c.d.(u,2n) = u and up nl+l 21. or u = 2 n' where n = 2 nf, n' nf, and n1 is the highest power of 2 in the prime factorization of n. The number of state-cycles of length p is again given by n = 2P-2P (the same reasoning as before p applying in this case - p' being the next smaller state-cycle length w.r.t.p). The state-cycles of the locally-balanced cycle with a normallyoriented switch, which I will call normal state-cycles, figure basically in the present study. Part of the reason for this lies in the following operation: an inversion consists in changing a given pair of a locally-balanced switch from normally-oriented to inverselyoriented or vice versa. The result of an inversion is a new locallybalanced switch produced from the given one. It follows directly from the definition of a locally-balanced switch that any locally-balanced switch can be transformed into any other by a succession of inversions. Thus, for example, any locally-balanced switch can be produced by using a succession of inversions on a normally-oriented switch. The next.five theorems will explore the relations between normal statecycles, inversions, and the transition graphs of locally-balanced cycles. In the proofs and at other points from here on the state represented by a given binary n-tuple will, where convenient, be labelled by the

decimal equivalent of the corresponding binary number. Thus (0,0,...,0) becomes 0, (0,...,0,1,0) becomes 2, and (1,1,...,1) becomes 2n-l. Theorem 6. Let E1 be the switching element of a locally-balanced cycle; let E2 be the switching element derived from E1 by an inversion on the jth pair, i.e. on (E2JE2j+1); and let s2j and s2j+l be the arguments of the jth pair. If s2j and s2j+1 belong to different state-cycles, C1 and C2, in the transition graph w.r.t. E1, then the transition graph w.r.t. E will be the same as that for E1 except that C1 and C2 will be united into a single state-cycle consisting exactly of all of the states belonging to C1 and C2. If s2j and s2j+l belong to the same state-cycle, C, in the transition graph w.r.t. E1, then the transition graph w.r.t. E2 will be the same as that for E1 except that C will be separated into two disjoint state-cycles which together include all of the states belonging to C. Proof: The transition table for a locally-balanced cycle, as derived from the switching element's truth table, is unchanged by an inversion except for the lines corresponding to the inverted pair. Let s2j and s2j+l be the left-hand entries of these two lines and s'2j,'2j+l their respective successors (right-hand entries) before the inversion. After the inversion the successor of s2j will be s'2j+l and the successor of s2j+l will be s 2j. From Theorem 4 one of two cases must hold for s2j and s2j+l, either they belong to different state-cycles or else they belong to the same state-cycle. Case 1) s2j, s2j+l belong to different state-cycles C1, C2. After the inversion the succession from s'2j to s2, within C1 is unchanged, thus each element of C1 appears in turn (since there were

29 no elements of C1 between s2j and s 2j all are present in this succession). However, the successor of sj is sj+l which belongs 2 2j+l to C2. The succession from s'j+l to s2j+l is undisturbed and every element of C2 appears in this succession. Finally the successor of s2j+l is s'2j which completes the new cycle (since we began the succession with s'2j). All elements of C1 and C2 belong to the resulting state-cycle. INVERSIONS DERIVED TRANSITION TABLE TRANSITION GRAPH do d! d2 q0 dl d2 NONE - 03 PAIR 0 0 3 0 e o 0 0 0 0 1 | =1 01 1 PAIR 1 1 0 20 _ 1 3 Q O 1 1 E3=1 0 1 1 0 0 ~4=0 1 0o PAIR 2 1 o 1 E5= 1 0 1 0 6=01 1 PAIR 0 PAIR 1 =1 1 1 PAIR 1 AFTER INVERSION OF PAIR 4 < INVERTED 1 DERIVED TRANSITION TABLE 3 IS THE SAMTE EXCEPT c2 = 1 AND ~3 = 0. PAIRS 1 AND AFTER IIVERSION OF PAIRS 4 6 2 INVERTED 1 AND 2 TRANSITION TABLE IS -- THE SAMY EXCEPT ~2 1, E3 = 0, =4 = 1, AID c5 = 0. 5 7 Fig. 10 Effects of Inversions on the Transition Graph of a Locally-Balanced Cycle Case 2) s2j, s2Jnl1 belong to the same state-cycle C. Let the segment of C from s2j through s2j+l be D1 and the other segment from s2j+I through s2j be D2. The first element of D1 is

50 s' and the last s2j+l. After inversion the succession in D1 is 2j 1 unchanged but s' 2 becomes the successor of s2j+1. Thus D1 becomes a state-cycle. Similarly D2 becomes another, disjoint, state-cycle. The effect of the inversion has been to "pinch" the original cycle in two at s2j, s2j+l* Theorem 7. In any transition graph containing normal cycles, there are at most two inversions which can, individually, connect a given pair of normal cycles (C1, C2). There are no inversions which can separate a given normal cycle into two state-cycles. Proof: 1) Let.. 6,p 5j+l''...' +n-l' %j+n'"' be the binary sequence associated with the state-cycle C1 of the hypothesis and... &'n' P'j+i.. 6'j+n-l-* the sequence associated with C2 (see step (1) of Theorem 5). Since C1 and C2 are normal cycles they will each be of length n or a divisor thereof by Theorem 5. Consequently in the above sequences 6j = j mod n and' = jmod n 2) If there is an inversion connecting C1 and C2 then there is a mapping V(6j) = V(j mod n) ='(j+h1)od n such that 5 = V(), except for some one kl < n and jl such that jl mod n - kl for which bJl = k = V(k ='k+ That is, for an inversion to connect 1 kl I kl+b~ C1 and C2 we must have the state (5k, 6k-1 —.80' 6n.. —.Sk+l) of C1 belonging to the same pair as the state (V(Sk),..., V(6k+l)) of C2 (see case (1) of Theorem 6). This means that V(6j) = b6 except V(bk) = k (see the last sentence of step (1) of Theorem 5). 3) If there is a second inversion connecting the two state-cycles then there is a second mapping V'(6j) = 5'(j,+b), with J IJ^b2) mod n

31 b2 b1 and V'(6j) = 6j except V'(6k2) =k2 for some one k2 n and k / kl. 4) Let g = g.c.d. (Ib2-bll,n) and form equivalence classes { (jP + u) nod n) for 0 1 u < P and j = 0,1,2,....For u such that neither k1 nor k2 belongs to the equivalence class selected by u we must have all elements of the class equal. This can be seen by noting that 5u =' (u+bl) mod n'(u+b2) mod n' under V and V', and that b(u+b2-bl) nod n = (u+b2) mod n under V'; whence it follows 6 = 5(u+b2-bl) nod nand, by repeating the procedure, = 6(u+ r(b2-bl)) mod n for any r, which can be reduced to the form = 6(u+j) nod n Now consider the equivalence class which includes Skli By the reasoning of the preceding line and the fact that = kl+bI vwe have = 5 and k'klbl we he kl+(b2-bl)) nod n 5(kl+r(b2-b1)) mod n = 5(kl+(r+l)(b2-bl)) mod n' for all r such that r(b2-bl) f 0 mod n, unless (kl+r(b2-bl)) mod n = k2 for some r. That is, unless ki and k2 belong to the same equivalence class, we obtain 6 (k b2b)) nod n kl mod n which is a contradiction. Thus kl and k2 belong to the same equivalence class. The above relations can be used directly to construct binary sequences satisfying them. Therefore, some state-cycles satisfying the conditions of the hypothesis can be connected by either of two inversions. 5) If there were a third inversion connecting the two state-cycles, then V"(j) ='(j+b) od n' b3 / bl, b3 / b2 and V"(Sj) = j except V"(k ) k3 for some k3 kl, k2. Now k3 must belong to one of the equivalence classes above. We can assume, without loss of generality, that kI < k2 < kG < n. If k3 beiongs to { 5(j+u) nod n} which does not contain k1 and k2 we obtain u =: u, a contradiction.

32 But if k3 belongs to the class containing k1 and k2 we have (k1 + rl(b2-bl)) mod n = k2 (k2 + r2(b2-bl)) mod n = k3 (k3 + r3(b2-bl)) mod n = kl whence kl =Bk2 = k k = kl which is again a contradiction. Therefore a third inversion connecting the two cycles is impossible, and hence, there can be at most two inversions able to connect the two cycles. 6) The second part of the theorem follows immediately from the observation that all the states of a given normal cycle have exactly the same number of digits equal to 1 in their binary representations. Since the second argument of any pair must, by definition, always have one more digit equal to 1 than the first argument, the two arguments of a pair can never belong to the same normal cycle. Therefore, because the conditions of case (2) of Theorem 6 are not satisfied, no single inversion can separate a normal cycle into two state-cycles. Theorem 8. There is a locally-balanced cycle having a transition graph in which all 2n net states belong to a single state-cycle; i.e., the net will have a net state sequence of period 2n. Proof: I) By Theorem 4 we know that the transition graph of any locallybalanced cycle consists only of disjoint cycles of states. For the purposes of this proof, a state-cycle C will be said to be composed only of pairs of states if one argument of a pair of the switch occurs as a state in C just in case both arguments of the pair occur in C. In order to prove the present theorem we shall first show that any statecycle composed only of pairs of states must include the states (0 and p4

33 Assume there is at least one state-cycle composed only of pairs. Let (2j, 2j+l) be one of the pairs occuring in this state-cycle. By the definition of a locally-balanced cycle (see the derived transition table of Figure 9) either (2j) or (2j+1l) must have an element of the pair (2[ ], 2[ ] + 1) as a successor state, where [ is the integral part of J. Since the state-cycle is supposed to be composed only of pairs, both arguments of the pair (2[1], 2[j] + 1) must belong to the state-cycle. Continuing this line of reasoning we see the states ([I]), ([I),..^,(1)) (0) must be elements of the state-cycle. 2) From the preceding paragraph it follows that the transition graph of any given locally-balanced cycle contains at most one statecycle composed only of pairs of states. That is, any state-cycle composed of pairs must contain(O)and(l), but this pair can belong to at most one state-cycle. 3) Consider now the n delay locally-balanced cycle, L0, having a switching element with all of its pairs normally oriented. Invert the pair having arguments (0,1). By Theorem 5 the elements of the first pair belong to two different state-cycles. Thus by Theorem 4 the result of the inversion will be to join these two state-cycles to form a single new state-cycle, C1. The transition graph of the locally-balanced cycle,Ll, obtained by the inversion will thus have one less state-cycle. 4) If the new state-cycle, C1, is not composed entirely of pairs, then there must be a smallest pair (2j, 2j+l) such that one of its elements belongs to a state-cycle disjoint from C1 in the transition graph for L1. But then an inversion on this pair will yield a new state-cycle C2 and a locally-balanced cycle, L2, which has one less

34 state-cycle than L1. The process can be continued until one first reaches a state-cycle, Cj, formed for Lj, which is composed only of pairs. 5) But Cj will be composed only of pairs just when Cj contains all 2n states of Lj. Otherwise there would be state-cycles of L. disjoint from C,. These state-cycles would not be composed wholly of pairs (see step (2)). Therefore, we could apply the same process of successive inversion that was originally applied to C1, to pairs belonging to these state-cycles (pairs not belonging to Cj). Cj will be undisturbed since none of these pairs contains any of its elements. Furthermore the process cannot terminate at any stage in another state-cycle composed only of pairs, since this would give a locally-balanced cycle with two state-cycles composed only of pairs. But then the process must continue until all elements of the cycles disjoint from Cj are joined in a cycle C'k But in that case C' must consist only of pairs - the pairs not belonging to Cj. This again contradicts step (2); hence there can be no state-cycles disjoint from Cj. Cj, as constructed, contains all 2n states of the locally-balanced cycle Lj. The next theorem begins a direct investigation of the effect of increasing the number of feedback loops in a cycle. The theorem basically concerns input-independent locally-balanced cycles in which some of the feedback loops to the switch have been omitted, i.e., cycles in which the switch receives k < n inputs from the cycle. Just before Theorem 5 I mentioned that, in a locally-balanced cycle, use of a switch with all pairs normally oriented or all pairs inversely oriented, in effect, converts the cycle to a simple cycle. This observation can now be generalized: A switching element will

35 be said to be of order k if and only if there are k numbers, 0 C io*.... <ik 1 n-l. such that all arguments with the same values for Pio.-.'Pi*kl determine the same output value, q(t), for the switch. If this is true for k and for no kl k the switch will be said to be properly of order k. The output state, q(t) of a switch properly of order k depends only on the state of inputs Pi...l thus in a cycle the switch could be replaced by a switch with k * n inputs identified with delay outputs di...dik1 TRUTH TABLE OF A LOGICAL NET WITH GIVE.N SWITCH SWITCH OF PROPER ORDER Z q PIPIo S r. — 0 0 0 0 0 1 0 I ENCLOSES I I I q I! i; 1 ~ Fig. 11 A Switch Properly of Order 2 For a locally-balanced switch,ikl = n-1. This is the case because, in each pair determined by giving values to PO' -— ^Pn-2 q(t) = E2j when Pn-l = 0 and q(t) = E2j+l = 2j when Pn-l = 1. That is, different values of Pn-l give rise to different values of q(t). Using these facts the definition of order can be recast for locallybalanced switches in terms of orientation of pairs: A locally-balanced switch is of order k if and only if there are k-1 numbers,

56 0 4 lO <... < ik2 < n-l, such that all pairs with the same values for Pio0... Pik_2 have the same orientation. The proof of Theorem 9 will describe some of the changes occuring in the transition graph of a locally-balanced cycle as the order of its switch is increased (i.e., as the number of feedback in the cycle is increased). The statement of this theorem as well as that of some succeeding theorems can be considerably shortened by making the following definition: The state-cycle partition of a net N with n delays is a partition of the set of 2n net-states satisfying the following conditions: 1) one subset of the partition consists just of those states which do not belong to a state-cycle in the transition graph of N. 2) the remaining net-states are separated into subsets such that two states belong to the same subset if and only if they belong to the same state-cycle in the transition graph of N. Theorem 9. The set of state-cycle partitions associated with the set of locally-balanced cycles having n delays and a switching element of order k properly includes the set of state-cycle partitions associated with any collection of locally-balanced cycles having n delays and switching elements properly of order k' < k. Proof: 1) We begin by noticing again that all of the states in a given normal state-cycle have the same number of ones in their binary representation. Thus the set of norrrmal state-cycles associated with a locally-balanced cycle can be classified according to the number of ones in the binary representations of their states.

37 2) For a locally-balanced switching element to be properly of order 1 ~< j i n there must be at least one set of inversely oriented pairs among the sets of pairs specified by the definition of a jth order switching element (i.e., among the sets of pairs defined by the sets of 2n-j+l binary n-tuples, (PO,..,'Pn-2)' which can be formed for each fixed assignment of values to the J-1 components Pio;'...Pij_2). 3) Consider a switching element properly of order j which has exactly one set of inverted pairs and let the set be the one obtained by setting p0 = pi.. Pi_2 = 0. As we range over the arguments of these inverted pairs, the number of digits equal to 1 in any given argument will range from zero to n-j+l. For this switch no inverted pair will have an argument with more than n-j+l components equal to 1. Thus a locally-balanced cycle, L, using the given switch, will have a transition graph in which each state-cycle having a state with more than n-j+l ones in its binary representation will be a normal state-cycle. Furthermore, for the given switch, there will be one and only one inverted pair whose 2nd argument has n-j+l components equal to 1. For this reason the state-graph of L will have one statecycle consisting of a normal cycle of n-j+1 ones connected to a normal cycle of n-J ones (which in general will be connected with other normal cycles). Thus one of the normal state-cycles with n-j+l ones in the binary representation of its states will not be present as a state-cycle among the set of disjoint state-cycles of L (rather it will be part of a larger state-cycle). ) If we consider an assignment of values to pio... i other than pi0 =. = Pij_2 = 0, then some normal state-cycles of more than n-j+l ones will be connected to another normal cycle. Hence the switch

58 specified in step(5) is the only switch properly of order j which will yield a locally-balanced cycle for which all state-cycles having states with more than n-J+l ones in their binary representation are normal while some of the other state-cycles are not normal. 5) For switches of order 0 < j' < j some normal cycle of n-j'+l n-j+l ones will be connected to another normal cycle. For switches of order 0 all state-cycles are either normal or else all are non-normal. Therefore there is a switch or order J which, in a locally-balanced cycle, produces transition graph different from any produced by switches of order j' < j. (Actually this can be generalized: Let Tn represent the subset of the partition of normal state-cycles which contains all normal state-cycles of h ones. Then only switches of order j or greater will yield state-graphs, for any choice of C4j, where all cycles other than those in Tc, Tc+l,..,Tec+n-_j+ are normal while some cycles in Tc, T+l,...,Tc+n-j+l are connected by inversions.) 6) Since the set of switching elements of order j includes all switches of order j' < j, the set of state-graphs produced by switches of order j in a locally-balanced cycle properly includes the set of state-graphs produced by switches of order J' ( j. Let a pair be called unbalanced if c2j = c2j+l. Starting from the normally-oriented n-input switch any n-input switch can be produced by unbalancing selected pairs after carrying out a properly chosen set of inversions. Using this fact Theorem 10 and its corollary extend the results of Theorem 9 to every input-independent cycle with one switch. Theorem 10. The set of state-cycles for a given input-independent cycle with one switch, E1, of order k is a subset of the set of state-cycles of an associated locally-balanced cycle with a switch,E2, of order k' D k.

39 No locally-balanced cycle with a switch of order less than k' includes, as a subset, the set of state-cycles of the cycle with switch E1. Proof: 1) Consider the derived transition table (cf. Theorem 4, step(l)) of a net cycle with a single switch. Just as in the case of a locallybalanced cycle, all digits of the successor state in each row, excepting the first digit ej, are determined independently of the switch used. Only cj is determined by the switch output. 2) Now consider the unbalanced pairs, if any, of the switch E1. In an unbalanced pair both arguments, sO and sl, have the same successor state, s', in the derived transition table. Thus one of the two arguments, say s0, cannot belong to a state-cycle; otherwise some other state in the state-cycle would have to have two successors in the derived transition table, an impossibility for input-independent cycles. Tne other of the two arguments, sl, may or may not belong to a statecycle. If sl belongs to a state-cycle orient the corresponding pair in the locally-balanced switch, E2, so that'sl has the same successor s'. (E.g., if s1 is the first argument of the pair and the first digit of s' is E2j = 1, then the pair in the locally-balanced switch E2 should be inversely oriented.) If sl does not belong to a cycle, the corresponding pair in E2 can have either orientation and still satisfy the first part of the theorem; however, in step (5) we will see that sometimes one of the two orientations will have to be specified in order to satisfy the second part of the theorem. 3) For each balanced pair in E1 the corresponding pair in E should be balanced with the same orientation. 4) The switch EZ, is fully specified once the instruction of step (2) or step (3), whichever applies, has been carried out with respect to

40 each pair of E1. Each argument of E1 which belongs to a state-cycle also belongs to a state-cycle of the locally-balanced cycle with switch E2 and in both cases the successor state is the same. Thus the set of state-cycles with respect to E must be a subset of the set of state-cycles with respect to E2. 5) Consider the jth pair of E1. Let PiO,...,pib be the smallest set of digits in the first argument of the jth pair such that all other pairs with the same values for these digits in their first argument also have the same values for (e2j, e2j+l). If this jth pair is balanced then so must be the other pairs with the same values for Pi 0.~Pi and they must have the same orientation. All corresponding pairs in E2 by definition will have the same orientation. In this case the values of 2j-, 2j+1) for E2 will also be determined by the digits Pio0..- Pi. If the jth pair of E1 is unbalanced then so must be the other pairs specified by Pi,.. P. If all of these pairs either have the same argument, e.g., the first, belonging to a cycle or else neither argument belonging to a cycle then all of the corresponding pairs in E2 can be given one orientation. Then,as before, all pairs in E2 with same values for digits p will have the same orientation and hence the same values for (2j, c2j+l). Finally, some of the given unbalanced pairs in E1 may have their first argument belonging to a cycle and some the second. Then the corresponding pairs in E2 will not have the sane orientation (see step (2)). Thus for E2 additional digits Pib+l-...P+b will be necessary in this last case to specify just those pairs with the same orientation. Thus we see that E2 will in general have a proper order k' > k. Furthermore it follows directly from the preceding argument that no locally-balanced switch can have proper order less than that of E2 and still satisfy

41 step (4). Corollary The set of state-cycle partitions associated with the set of input-independent net-cycles each having n delays and one switch of order k properly includes the set of state-cycle partitions associated with any collection of input-independent net-cycles each having n delays and one switch properly of order k' < k. Proof: 1) Consider a switch properly of order k, with at least one unbalanced pair, inserted in an input-independent cycle with one switch. By the first two lines of step (2) in Theorem 10, the transition graph of such a cycle will contain at least one state which does not belong to a state-cycle. Thus the transition graph of step (2) of Theorem 9, since it consists just of state-cycles, cannot occur for any switch, balanced or unbalanced, of proper order k' < k. 2) Since the set of switching elements of order k includes all switches of order k' ( k, the corollary follows. Let a net-cycle of order k be defined as a net-cycle whose normal form contains at least one switch of order k and contains no switch properly of order k' > k. Using this definition Theorem 11 extends the results of the last two theorems to all input-independent cycles. Theorem 11. The set of state-cycle partitions of the set of all n-delay net cycles of order k properly includes the set of state-cycle partitions of any collection of n'-delay, n' - n, net-cycles of order k' < k. Proof: 1) Note first that, with respect to net-cycles having n delays, there is only one normal state-cycle containing a state with n ones in its

142 binary representation. Furthermore this normal state-cycle has but one element, namely (ll,l.. e,l). 2) Consider a switch EL which, when used in an input independent net-cycle with one switch, causes the state (1,1,1..,l) to have a successor state with fewer than n digits equal to 1. (Since the net-cycle has but one switch, the successor will clearly have to be (0O,1...,).)Q Thus in the transition graph of the net-cycle using E1 no normal state-cycle with n ones will appear. 3) Now consider the set of all n-delay net-cycles, in normal form (see Part 2), which have E1 as one of the switches. The normal statecycle with n ones will not be present in the transition graph of any of.these net-cycles - this can be deduced as follows: The state (1,1,...,) is' the only element of the normal state-cycle with n ones; therefore the successor of (1l,l,...,) will have to be (li,,,l o, ) if the normal state-cycle with n ones is to be present in a transition graph. When the net-state, s(t), is (1,1,...,1) the output state of each delay in the net-cycle is dj(t) = 1, j = 0,...,n-1, If the output of E is connected to the input of delay d, then dl(t+l).= 0 since the output state of E1 is qO(t) = 0 when the argument is (ll,..,,l). The output state of a switch whose output is identified with the input of delay dj, j = 0,2,3,...,n-l, canbe either qjl(t)= 0 or qj_l(t) = 1. If qj_(t)= 0 then dj(t+l) = 0; if qj.l(t) = 1 then dj(t+l) = 1. The net-state s(t+l) = (do(t+l), di(t+l) = 0,,o, dn.l(t+l),) can at best have one less 1 than the net-state (do(t) = 1, d(t) = l,...,dnl(t) = 1). Therefore no n-delay net-cycle including in its normal form a switch such as E1 will have the normal state-cycle with n ones present in its transition graph,

453 4) Let Ek be the switch of proper order k which gives the transition graph described in step (3) of Theorem 9. All state-cycles having states with more than n-k+l ones in their binary representation will be present in this transition graph as normal state-cycles. However, at least one of the normal state-cycles with n-k+l ones, Ck, will not be present in the transition graph. That is, one state s2h+l normally belonging to Ck will have as a successor s'2h+1 a state not belonging to Ck. By the construction of step (3) in Theorem 9, s'2h+l will.have n-k ones, positions dldio+l.,... dik 2+ being equal to zero, ik_2 < n-1. For convenience I will assume i =, iI = 2,o..,ik_2 = k-le The proof can be generalized by inserting dio for dl, etc, throughout steps (5) -W. 5) Now consider the set of all n-delay net-cycles, in normal form, with Ek as one of the switches and in which no switch is of order greater than k. The next six steps of this proof will show that no net-cycle in this set has a transition graph with the following property: The transition graph consists only of state-cycles and each state-cycle having an element with more than n-k ones in its binary representation is a permutation of a normal state-cycle, 6) Assume that a transition graph with the property of step (5) is possible. Let the output, qo of Ek be identified with the input of delay dl. Then, in particular, the state S2h+l of step (4) must have a successor state with n-k+l ones. At time t, for the net-state to be s2h+l(t), we have dj(t) = 0,...,dkl(t) = 0 and do(t) = 1 along with dk(t) = l,...,dnl(t) = 1. Since qO(t) = 0 we know that dl(t+l) = 0. Thus s'h+(t+l) can contain n-k+l digits equal to 1 only if djo+l(t+l) = 1 for some 2 * J0 Q k. But this means that switch qj0 must produce an output state qjo(t) = 1; furthermore this switch mnust be of proper order f k by step (5). Two possibilities present themselves:

6.1) The switch qjo has an output state qjO(t) = dJo(t) for all arguments with more than n-k+l digits equal to 1 in the associated truth table, 6.2) The switch qjO has an output state qjo(t) = dJo(t) for some argument with more than n-k+l digits equal to 1 in the associated truth table. 7) Consider first a switch of type (6.1). The next three steps of the proof will show that a switch of type (6.1) requires the presence, in the net cycle, of an additional switch qr0 which is of type (6.2). That is, qr0 is required if the net-cycle is to have a transition graph with the property given in step (5): 8) For the argument S2h+l(t) = (do(t) = 1,dl(t) O=,d2(t) = O,...,dk.l(t) = 0,dk(t) = l,...,d nl(t) =1) the switch qjO must have an output state qjo(t) = djo(t) = 1 by the first part of step (6). Note, however, that the switch qJO must be of proper order k0 o k by step (5). That is, the output state qJo(t) must be the same for all arguments having the same values for a given set, Ok0, of ko components of the argument (see the discussion of proper order preceding Theorem 9). There are now two alternatives for Oko: 8.1) The components dl,.,.,dk_l are all included in ko. 8.2) At least one of the components dl,...,dkl is not included in. ko 0 9) If (8.1) is the case then we look at a net-state s(t) chosen so that dl(t) = O,...,dk_l(t) = 0 and all other components are 1 except, say, do(t) = O. s(t) has a binary representation with n-k digits equal to 1. The successor state s'(t) will have at least n-k+l digits equal to 1 because of the action of qjO unless there is a third switch qjl

45 in the normal form of the net-cycle. In other words,.unless there is a third switch qjl one of the normal state-cycles with n-k+l ones will not be present in the transition graph. But if there is a switch qJl we must start again from step (6) and determine whether qj is of type (8.1), type (8.2) or type (6.2). If qjl is in turn of type (8.1) we will require a switch qj2 and so on until: 9.1) the allowed number of switches, n, is exceeded, in which case the contention of step (5) is proved, or 9.2) a switch qj is of type (6.2) or type (8.2); if type (6.2) the statement of step (7) is proved; if type (8.2) we apply step (10). 10) If (8.2) is the case, let du, 1 S u % k-l, be the component not belonging to 0k. Since du does not belong to Ok0 we can set d^(t) = 1 and still have q0(t) = 1. But then, unless u = jo, qJo(t) = 1 = do(t) for an argument with n-k+2 digits equal to 1, contradicting (6.1). However, if u = Jo the two arguments 2h+l(t) = (do(t) = 1, dl(t) =...,djo(t) = O,...,dk_l(t), dk(t) = l,...,dn_l(t) = 1) and s+ (t) = (do(t) = 1, dl(t) = O,...,d (t). (t)= O, dk(t) = 1,...,d_(t) ) have the same successor state s' +l(t) = (do(t) = 1, dl(t) = O,..., do+l(t) =,..., d 2h+1 0 k-1 d (t) O Pk dk(t) 1,...,dn_l(t) = 1), Thus a third switch qr0 is required if the transition graph is to be composed just of state-cycles. If q is chosen to change the successor state of s2h+l the problem returns to step (6) and, as in step (9), either the allowed number of switches is eventually exceeded or else we must at some point introduce a switch of type (6.2). If q"r is chosen

46 to change the successor state of s2v then qr0 is automatically a switch of type (6.2), 2v+l having n-k+2 digite equal to 1. 11) From steps (7) - (10) we see that, if we are to satisfy the hypothesis of step (6), a switch of type (6.2) must occur in the netcycle. However, a switch of type (6.2) requires that a state s2w+l with n-k > n-k+l digits equal to 1 have a successor with a different number of digits equal to 1. Thus yet another switch, qJl, will be required if the normal state-cycle containing s2w+l is to be present in the state-transition graph. But now we can apply to qjl the reasoning from step (6) onward. Ultimately a set of switches qj,' qjlj...,qj will result. The last, qjm will perforce affect an argument with n digits equal to 1. But there is only one argument with n ones, (1,1,...,l),and by step (3) no additional switches can correct for the case in which (1,1,...,1) has a successor state with fewer digits equal to 1. Thus we see that all cases lead to a contradiction of the assumption of step (6). Hence the assertion of step (5) follows. 12) The theorem for n' = n and k' < k follows from the assertion of step (5) by virtue of steps (4) and (5) of Theorem 9 and step (1) of the Corollary to Theorem 10. To extend the theorem to n' $ n we note that in an n-delay cycle, Nc, the switches qit, for i' = n'-l, n',..,n-2, can be chosen so that qi,(t) = 0 for all arguments. Then by choosing qn-.lqo0 q * * *4nt'-2 so that they are independent of argument columns Pn', Pn'+l** -,Pn-1 we have, in effect, a cycle N'c with n' delays (together with a string of n-n' delays whose output states are always zero). The first n' digits of any net-state of Nc will be exactly the digits of the corresponding net-state of N'c Thus there is a state-cycle partition of an n-delay net-cycle of order k which can be mapped directly on the state-cycle partition of an arbitrary n'.-delayt

47 n' 4 n, net-cycle of order k' < k. The theorem for n' * n and k' < k follows. Theorem 11 provides a basis for several comments on the effect of increasing the number of feedback loops in a logical net. Here I will make just one comment, reserving others for the more general context of Part 5: Consider the case of an experimenter presented with a black box (cf. Moore's gedanken experiments [6]) about which he is given the following information: 1) all elements in the box belong to a single input-independent net-cycle, 2) the box has one output for each delay element inside, 3) at any time the box can be set to an arbitrary "initial" net-state and observed. for as long as desired. Theorem 11 tells us that there is a net with at most k feedback loops through each switch which will make the black box behave in a fashion impossible for any net with n' I n delays and k' < k feedback loops through each switch. Moreover, the set of behaviors possible for such black boxes when each switch receives at most k feedbacks properly includes the set of behaviors possible for boxes having n' i n delays and k' < k feedbacks to each switch.

Cycles in General The object of this section will be to relate the behavior of netcycles in general to the behavior of input-independent net-cycles, The basis of this relation is the nature of the truth table of a switching element in an arbitrary net-cycle: Let Nc be an n-delay net-cycle in normal form having a total of k distinct switch inputs identified with elements not belonging to Nc, i.e., net cycle inputs. The truth table of each switching element in NC can be regarded as having a normal form with k argument columns h0o...,hk.l corresponding to the k net-cycle inputs and n argument columns PO,. *ePn-1 corresponding to the n net-cycle delay outputs. If a given switch in Nc has j < n inputs identified with delay outputs di,..dij_l of Nc then the truth table output q(t) will of course depend only upon the j columns Pio...,pij of the n colamns Pl,.. -LPnO That is, with respect to the n columns Pl ^..,Pijl the normal form of the truth table will be of order j. Similarly if the given switch has b < k net-cycle inputs then q(t) will depend only upon b columns hvO...hvb-l of the k columns h0o...,hk-1 Each switch in the netcycle, regardless of the number of its inputs, can thus be given a standard truth table with ki-n argument columns and one output column. Note that the k+n argument columns of the truth table of each switch in Nc are identical when they are given the order ho.,* *hk-l, PO. -*. Pn_-1 In the normal form of the net-cycle Nc, each delay in the cycle, di, has its input identified with the output of one of the switches, qi, in the cycle so that di(t+l) = qi(t). Furthermore Pi(t) = di(t). If the n switch output columns are arranged in the order qn-lqOql: *- — qn-2 at the left of the k-in argument columns the 48

49 result is a transition table where the transition from (do(t),...Pdnl(t) to (do(t+l),...dnl(t+l)) depends upon the value of the net-cycle input state (ho(t),..,hk_l(t)) I(t) s(t) s(t+l) ho(t) *. hk-l(t) do(t) =. dnl(t)= d(t) d t+l) Po(t) Pn-_l(t) qn-l(t) qn-2(t) o... I o... * -2,0 0 0 ~ 0 ** 12 n.n-2n-l,l *..*.* * - -* -* * - * *- eo e * - - *0 *ow 0 1 *.. 1 En1,2nl *e 2 0... 1 0... 0 II n,2n1 2, *O. *. 1* ** O * n * * * ~* al~, a n -2,2n 1 * I 0...... 0.S.. 0. 1... 2.1 | O... ||~In-1,2k+n-1... n-2,2k+n-1 * * * ** - a * * a * *.* ** * *l* * 6* * * 1... 1 1 e... 1 en-12k+nl en-2,2kn.-1 Fig. 12 Derived Transition Table for a General Cycle with Input Now fix a value, I, for I(t) = (ho(t),...,hkl(t)) and consider, in the derived transition table for Nc^ the 2n rows having the given values for the arguments hO(t),...,hkl(t). The 2n rows so selected constitute the transition table of an n-delay net-cycle NI which has n switches in normal form, each with n inputs. Of necessity, NIO is an input-independent cycle in which the switch at position qi has, for arguments po(t)... (t)- an output qi(t) = i,x.2+ where x t decimal equivalent of the binary number ho(t)2kl+-1,..+hkl(t)e2~ and y = the decimal equivalent of p0(t)'2-1'+...+pn-l(t)e2i. That is, at each position in NI we have a switch whose output for an argument

50 (Po(t),L..Pnl(t))) is simply the value qi(t) given for the corresponding n argument values of Pl,.-.,Pn in one of the selected 2n rows. We see that the effect on Nc of a given net-cycle input state Io is to select an n-input switch at each position in Nc, the result being an n-delay input-independent cycle NIO. If I(t) = Io then the behavior of the cycle Nc for that one moment of time will be exactly that of Ni0. The importance of the preceding observation lies in the relation between the transition graphs of the various NI(t) and the transition graph of the cycle Nc. Let G be the transition graph of Nc and let the 2k possible net-cycle input states of Nc, (h0,..,hk-l), be labelled Io, I1...,I 2k l Let GIj be the subgraph of G obtained by retaining all of the vertices of G and only the edges of G labeled Ij (see Part 2). Then GIj is exactly the transition graph of the net-cycle NIj, the input-independent net-cycle selected when I(t) = Ij. Conversely, if the 2k graphs GIj, j = 0,...,2k-1 are given, then the graph G can be constructed. This is done by simply superposing all the graphs GI so that vertices with the same label are identified and each edge for each GIj appears in the result, G, connecting the same vertices. In the process of forming G from the G many of the properties common to j all the G. will reappear as properties of G. J LOGICAL NET Nc TRANSITION GRAPH G G OF Se It0. (. MO) ho -,odo d I q, d,-o/0 0 o 1' o 0 0 0 < X001o,, t 00 1 07 I, (h I) Fig. 13 An Example of the Selection of GI(t) By the Input-State I(t)

51 In the special case that a subgraph GIj of the transition graph G consists just of state-cycles, it can be conveniently represented by an element of the group of permutations on 2n elements. To do this we make use of the fact that any permutation can be given by the product of a set of disjoint circular permutations: Let Ci be the ith statecycle of Gij (under some arbitrary ordering). Let Si,O si, lSi,8n be the net-states belonging to Ci ordered so that Si,y+l succeeds Siy (and si, succeeds sini) in Gj.. The circular permutation (si,0 si,l... Si,ni) represents the state-cycle Ci and, thus, the group element gj = (so,0 SOI **. SOo)(SlO *.. Sinl) —(SvO * 0 vn) represents GIj. Note that, if the state cycles Ci are normal statecycles, the operation of inversion on the pair of states s2h and S2h+l can be represented by multiplying gj on the left by the transposition (s2h S2h+l). Thus, if the switch in a locally-balanced cycle is obtained by inversions on pairs ho,h,...,h1. of a normally oriented switch, the resulting transition graph GIj will be represented by the group element. g'j = (S2ho S2ho+l)(s2hl S2hl+l) — (S2hr S2hril) o gj where gj represents a transition graph consisting just of normal statecycles. If G is the transition graph of a net-cycle Nc with input and if each subgraph GI of G consists just of state-cycles, then given an input state sequence of period m the resulting net-state period of Nc can be determined by means of the group representation. This is accomplished by using the graphs GI(O) GI(1). **GI(m-l) specified by input states I(O), I(1),...,I(m-l), where I(t) = I(j) if and only if t - j mod m, j = O,...,m-l. If gi(t) is the group element corresponding

52 to GI(t., then the net-state period will be a divisor of the product m * rg, where rg is the order of the group element g = gI(O) ~ gI(1)'. gI(m-l1) As a more general example of the way properties of the GIj reappear in G, I will show how Theorem 11 can be appliedto net-cycles in general after the definition of a cycle of order r (given in Part 4) is extended appropriately, Let E1 be an arbitrary switching element with b = n+k inputs. Let n of these inputs, pO,,opn_1 be identified with the outputs of elements belonging to a cycle Nc. Let k of the inputs hoo,. ohkl be identified with the outputs of elements not belonging to Nc. E1 will be said to be of order r w.r.t a cycle Nc if, ignoring the argument columns ho,...,hk._l, it is of order r when just columns P*O,.-Pn-l are considered. A net-cycle Nc, with or without net-cycle inputs, will be an (nr)-cycle just in case the normal form of the cycle contains exactly n delays, at least one switch.of order r w.r.t. the cycle Nc, and no switches of proper order re > r w.r.t. the cycle. An (n.r)-Cycle will, in effect, have no switch which receives more than r distinct feedbacks from delays in the cycle Theorem 12. The set of state-cycle partitions of the set of all (n,r)-cycles properly includes the set of state-cycle partitions of any collection of (n" r )-cycles with n's n, re < r. Proof: 1) In order to apply Theorem 11 to an arbitrary net-cycle, Nc, of order r, consider first the transition graph GIj of Nc. Each GIj will be the transition graph of an input-independent cycle Nij of order r (since the switches of NIj cannot have any cycle feedbacks not present in Nc)o Thus each GI. will be subject to Theorem 11 as applied to input-independent

53 net-cycles of order r. The result will be that each Gi can satisfy the following three conditions: 1.1) GIj consists just of disjoint state-cycles. I) 1.2) All normal.state-cycles with more than n-r+l ones are present in GIj. 1.5) One normal state-cycle with n-r+l ones is not present in G. 2) It follows from step (1) and the discussion preceding this theorem that there is a cycle Nc of order r with the following properties for its transition graph G: 2.1) All subgraphs GIj of G consist only of disjoint J state-cycles. 2.2) For each state s with i > n-r+l digits equal to 1 there is a unique state s' with i digits equal to 1 which succeeds s no matter what the input state I(t) is. The cycle of states so determined has n states, or a divisor thereof, as elements. 2.3) There is a state sO with i0 = n-r+l digits equal to 1 which, for some input state Io, has a successor state s' with io-l digits equal to 1. The statecycle to which so belongs has nO > n elements. 3) Using the state-cycle partition (see the definition preceding Theorem 9 - noting that a state-cycle in the transition graph is defined analogously to a net-cycle in a logical net) properties (2.1)-(2.3) can be restated: 3.1) The state-cycle partition of G contains no subset of elements not belonging to a state-cycle.

54 3.2) Each net-state with more than n-r+l digits equal to 1 belongs to a subset of the partition which contains exactly n states or a divisor thereof. 3.3) Some net-state with n-r+l digits equal to 1 belongs to a subset with more than n states. 4) For an n-delay cycle N' of order r' ( r no derived transition graph G1Ij can satisfy all three conditions (1.1)-(l.3) that each GIj satisfies. Hence no n-delay net-cycle of order r' < r can have a transition graph satisfying the conditions (2.l)-(2.3). Thus, in turn, no n-delay net-cycle of order r' < r can exhibit the state-cycle partition of step (3). 5) The remainder of the proof follows the argument of step (12) of Theorem 11. Theorem 12 can be interpreted in Moore's framework in much the same way Theorem 11 was. Let Bj(n,k) be a black box having the following properties: 1) n observable outputs each of which is a delay element output, 2) k inputs (net inputs) whose states at t = 0,1,2,.., are specified by the observer, 3) an arbitrary number of elements in the box all belonging to one and the same (n,r)-cycle. The set of behaviors possible for the set of all Bj(n,k) which contain an (nO,ro)-cycle properly includes the set of behaviors possible for any collection of Bj(n,k) which contain an (nl,rl)-cycle such that nl; nO and rl ( rO. In other words, no cycle with at most n delays or k' inputs and less than r feedbacks to each switch can imitate the behavior of particular cycles with n delays, k inputs and r feedbacks to one or more switches.

6. Comments and Conjectures The central purpose of this paper has been to present a set of operations and methods particularly suited to the investigation of cycles in logical nets. The outcome has been an interlocking sequence of definitions and operations leading from the simplest cycles to cycles of arbitrary complexity: Type of net-cycle Definitions providing Operations generating for extension to next level extension to next level 1) simple cycle with- locally-balanced switch; inversion out input derived transition table; normal state-cycle 2) locally-balanced order of switch unbalancing cycle 3) input-independent normal form of net-cycle; finite induction on net-cycle with one derived transition table number of switches in switch for normal form normal form of net cycle (listing possible effects of added switches on derived transition table) 4) general input- constant input subgraphs, selection operation independent net- GIj, of transition graph G of input-state I(t) cycle (selects GI(t) from G). 5) general net-cycle with input Because of the way in which a net-cycle is defined each element in a net can belong to at most one net-cycle, It follows from this that the. 55

56 cycles in a logical net can be ranked and therefore that the cascading operation is sufficient to generate any logical net (cf, BurksWang [1] and Part 2 of the present paper). Hence an additional row can be added to the table although the present paper does not specifically consider the case (except for simple cycles in Part 53): 5) general net-cycle rank of net-cycle cascading of netwith input cycles and n.-c. nets 6) logical nets in general In this table the class of all net-cycles of a given type properly includes preceding types of net-cycle. Generally, the operations presented in the table and discussed throughout the paper are useful in computing the behavior of particular net-cycles as well as in proving theorems about the various types of net-cycle. Using periodic input as a tool one can often prove theorems concerning a given class of nets which would be difficult to prove in any other way. For example, in Part 3 periodic input was used to show that cycles in logical nets provide more than just storage. Incidentally results there show that a particular case of a conjecture of Burks-Wang [l;p.292] is true. The conjecture is: For any degree d, there is some transformation not realized by any net of degree d - a net is of degree d if it contains at least one cycle of degree d and none of higher degree; a cycle is of degree d if it contains d delays. We see thus, by Part 5, that there are transformations on periodic input-state sequences not accomplished by any net of degree 1. The results of Parts 4 and 5 lend strong support to the following stronger conjecture:

57 For any (n,r) there is some transformation not realized by any net containing only (n,r)-cycles. In fact it should be possible to construct a lattice of behavioral transformations defined as follows: Let N(n,r) be the set of all logical nets containing only (n r) cycles. With each logical net in N(n r) will be associated a transformation which gives the net state sequence produced by each input state sequence. Let B(n,r) be the set of transformations associated with the set N(n,r). The lattice should satisfy the following conditions: 1) B(n,r) properly includes B(nl, r) if n' n and r' d r or if n' I n and r' r; 2) g.l.b. [B(nll)B n2,r)] = B(nro) where n =min(nl,n2) and ro = min (r1,r2); 3) l.u.b. [B(nlrl)B(n 2r2)] = B(nr5) where n =max(n1,n2) and r3 = max(rl,r2). It seems that the interrelations between periodic input and net state sequences, net cycles. state cycles, and permutation cycles, as sketched in Parts 3,4, and 5, will provide most of the operations and methods needed for the proof of this conjecture.

REFERENCES 1. Burks, Arthur W., and Hao Wang, "The Logic of Automata", J. Assn. Computin Machinery 193-218 and 279-297 (1957). 2e Burks, Arthur We and Jesse Be Wright, "Theory of Logical Nets", Proc. IRE, 41: 1557-1565 (1953). 3. Copi, Irving M., Calvin C. Elgot, and Jesse B. Wright, "Realization of Events by Logical Nets", J. Assn. Computing Machinery,: 181-196 (1958). 4. Kleene, Stephen C., "Representation of Events in Nerve Nets and Finite Automata", pp. 3-41 in Automata Studies, edited by C. E. Shannon and Jo McCarthy, Princeton Univ. Press, 1956. 5. Mealy, George, "A Method for Synthesizing Sequential Circuits", Bell System Tech.. J, 34: 1045-1079 (1955). 6. Moore, Edward F., "Gedanken-Experiments on Sequential MIachines", pp. 129-155 in Automata Studies, edited by C. E. Shannon and J. McCarthy, Princeton Univ. Press, 1956. 58

IDEX OF DEFINITIONS, SYMBOLS (FIRST APPEARANCE), AND THEOREM C, a state cycle........25 Corollaries Corollary to Theorem 5...... 19 Corollary to Theorem 10...... 41 cycle e.. O o e e 5 cycle input......... 8 d, directly drives..... D, drives...,.. 5 derived transition table..... 23 derived transition table for general cycle.. 49 directly drives, d...... 5 di(t), state of ith delay output..... 1 drives,. D....... 5 drive sequence.......... 5 drive sequence of switches......0 drives via switches, s.... 0 bj, entry in doubly infinite binary sequence.. 25 Cj, value of q(t) for jth argument..... 5 G, transition graph of Nc....., 50 GIj, transition graph of Ni..,... 50 gj, element of permutation group....... 51 59

60 hj, net input label. 9 Ih, net input state o...., 10 input state....... 8 inversely oriented...24 inversion *........ 27 jth pair.... 21 L, a locally-balanced cycle...24 locally-balanced cycle..... 21 locally-balanced switching element... 21 N_, name of net-cycle.... 46 n.c.-drives.... 15 n.c. -drive sequence..15 n.c.-net from A to B... 15 net-cycle of order k l... *.. 41 net input... 4..... net state......... 9 NIj, name of a net-cycle selected from Nc by input state Ij.. 50 normal form of a cycle.. 6 e normally oriented....... 24 normal state-cycle..... 27 (n,r)-cycle.......52 Pi(t), state of ith input to switch. ~. 3

61 q(t), switch output state O.... rank........,.. 6, drives via switches.... o set of switches from E1 to E2... 6 simple cycle.. 12 state-cycle partition..... state transition graph o ~... 9 subcycle.... 5 switch of order r w.r.t. a cycle.... 52 switching element of ox'der k.. 55 switching element properly of order k.. e, 35 theorems Theorem 1....... 15 Theorem 2...... 16 Theorem5......3 17 Theorem 4....... 22 Theorem 4'....... 24 Theorem 5.. 24 Theorem 6...... 28 Theorem 7......... 30 Theorem 8.......52 Theorem 9........ 6. 6 Theorem 10.. 38 Theorem 11....41 Theorem 12........ 52 unbalanced....