ENGINEERING RESEARCH INSTITUTE UNIVERSITY OF MICHIGAN ANN ARBOR THEORY OF LOGICAL NETS`b JESSE. B.'WRIGHT -..:. F Project M828 BURROUGHS ADDING MACHINE COMPANY DETROIT, MICHIGAN Decembier,'.1952

UzdAZ $T1 142 rv - ~-Ir

TABLE OF CONTENTS Page Preface iii Informal Introduction iv 1. Introduction 1 2. Primitive Elements 2 3. Well-Behaved Nets 4 4. Deterministic Nets 7 5. Well-'ormed Nets 10 6. W.F.N. and Digital C"Qmputing Circuits 16 Appendix 21 Index of Terms 26 ii

PREFACE The present monograph aims to formalize the relation between two-valued logic and digital computing circuits. It will be followed by another in which a detailed application of the present theory will be given. An informal introduction is included for the benefit of those who are not specialists in the field of symbolic logic. The authors wish to thank Carl H., Pollmar for many helpful suggestions and Paul Henle for suggesting the basic idea of Theorem 5-5. Arthur W. Burks Jesse B. Wright Engineering Research Institute University of Michigan December 23, 1952 11i

INFORMAL INTRODUCTION The present monograph deals with some of the theoretical aspects of the application of two-valued symbolic logic to digital computing circuits. The basic entities of any formal theory are of two kinds: the concepts which constitute the subject matter of the theory, and the principles involving these concepts. We may illustrate this distinction with the example of a two-valued propositional logic, one of the logics studied in this report. The concepts of this logical theory are: propositions which are true (have the value 1 ) or false (have the value 0 ); variables ranging over these propositions ( p, q, r,... ); the logical connectives negation (not, symbolized by a), inclusive disjunction (either p or q or both, or p v q ), exclusive disjunction (either p or q but not both, or p q ), cornjiuction (and, or o ), implication (if p then q, or p D q ), and equivalence ( p if and only if q, or p - q-). The principles of the theory are such statements as, for all values of p, p v -p; for all values of p, q, r, s,,.p v q v r v s) - (sP o nq ~ r S) The application of a formal theory involves interpreting the basic concepts of the theory so that the principles of the theory become applicable. We will illustrate the application of a two-valued propositional logic to electronic digital computing circuits with reference to the static units of the Burroughs Pulse Control Equipment. Suppose we have a Type 1603A Mixer driving a Type 1901A Inverter. Assign to each signal wire of the circuit a distinct variable; e.g., assign a, b, c, d to the input wires of the Mixer, f to the output wire of the Mixer (which is also the input wire of the Inverter), and g to the output wire of the Inverter. Let the value 1 of a variable mean that the wire it represents is at ground potential and let the value 0 mean that the wire it represents is at -23 volts. Then the Mixer realizes (corresponds to) a four-variable inclusive disjunction, for its behavior is characterized by the equation f - (a v b v c v d). Similarly, the Inverter is a representation of negation, for its behavior is characterized by the equation g - -f. The relation between the inputs of the circuit and its output is then expressed by g - (a v b v c v d) o Since we have characterized the behavior of the Mixer and Inverter by means of the logical concepts'of and v we may apply the principles of our logic to the analysis of the circuit. Applying the principle that -(p v q v r v s) -(p *~ q ~ -r ~ -s) we find that g - (-a ~ ~b ~ sc ~ ~d), i.e., that the output is at ground potential if and only if all inputs are at -23 volts~ Sheffer showed that all the connectives of the two-valued propositional logic could be defined in terms of a single one, the stroke function (rup v q). In constructing our theory we found it simpler to work with one connective than with many, so we took as our basic logical element a stroke element, symbolized by ~Kj. r, where r - (-p v- q). Nets of stroke elements can be constructed to represent any expression composed of p, q,... etc., and the logical connectives of the two-valued propositional calculus. For example, r - (p v q) is represented by iv

P r q lb r - (I a v fb) and substituting for a and b we have r - -(,-p vap) v(-q v.q); by the principle of logic that.-(p v q) - (Ip ~,q) we have r -( (P'p *Lp) v (N'q ~ q). Using the principle of double negation, we have r - (p-p) v (q-q) and hence by the principle that p - (p.p) we have r -- (p v q). Nets like these are investigated in the present monograph under the name "stroke nets". A stroke net has no capacity to store or remember information. For this purpose we introduce another element, the delay element g H — f It represents a circuit which receives a standard pulse and gives out a standard pulse after a standard delay;'this is normally accomplished by means of delay lines and circuits synchronized by means of uniformly spaced standard pulses produced by a "clock". We may represent the behavior of a delay element by the equations, fo - 0, ft+L - gt, where t ranges over the discrete time points 0, 1, 2,...e and ft. gt, etc. take on the values 0 or 1 (e.g., if the wire f has a pulse at t, then ft - 1; otherwise ft 0 ) The logical theory of these functions is an extension of two-valued propositional logic, a form of what is called two-valued functional logic. In the present monograph we work mainly with the two-valued logic of these time functions ft, gt, etc., and treat the propositional logic as a subcase of this more general logic. This logic is applied to nets made of stroke and delay elements in much the same way the propositional logic is applied to stroke nets. Given a net N we label its junctions with ft, gt, etc. and write for each stroke element an equation of the form f = Sgh (abbreviating ft - Agt v ~ht ) and for each delay element an equation of the form f =- Dg (abbreviating fo - O, ft+l = gt ). We then study the net by studying the logical properties of its associated equations. One of the main questions investigated in this monograph by means of symbolic logic is: To what class of nets do digital computing circuits correspond? We shall summarize briefly our answer to this question. There are nets which are not even logically well-behaved, i.e., whose equations do not have logically consistent and unique solutions. Since no net whose logical behavior is inconsistent or nonunique can be physically realized, we define a class of well-behaved nets (Section 3) which excludes all such cases. However, not all well-behaved nets are physically realizable, so further narrowing of the class of nets is required before we reach a class which corresponds to physical circuits. There are well-behaved nets containing delay elements such that the input state of the delay element at t is determined by its output state at time t+l; hence we define a class of deterministic nets (Section 4) which excludes these cases. Finally, there are deterministic nets in which there is a backward passage of causal influence through stroke elements; a class of well-formed nets is defined (Section 5) so as to exclude these. We thus arrive at a class of nets which corresponds very closely to the class of digital computing circuits. The exact correspondence is discussed in Section 6; it is roughly as follows. There are some nets not well-formed which can be physically v

realized. But for any such net N1, there is a well-formed net N2 which can perform all the logical operations of N1 and which in many cases is at least as small as N1 A second major question investigated in the present monograph is: What kinds of logical operations can be performed by various kinds of nets? An answer for each kind of net is given in the corresponding section. vi

THEORY OF LOGICAL NETS 1. INTRODUCTION It has been shown by Shannont and McCulloch and Pitts~t how two-valued4 symbolic logic may be employed to characterize the behavior of digital computing circuits; e.g., relay circuits,**- digital electronic computing machines, neuron nets. The purpose of the present paper is to help place the application of twovalued logic to such circuits on a formal and rigorous basis,'We are concerned with two kinds of entities, logical nets and digital computing circuits. A net N usefully represents a circuit C (alternatively, C physically realizes N ) when the physical behavior of C is mirrored in an idealized but nevertheless useful way by the logical behavior of N. To realize the purpose mentioned in the preceding paragraph, we will define various kinds of nets, study their formal properties, and discu'ss the extent to which they can be physically realized. Claude E. Shannon, "A Symbolic Analysis of Relay and Switching Circuits," Transactions of the American Institute of Electrical Engineers 57, 713-723 (1938). $+Warren L. McCulloch and Walter Pitts, "A Logical Calculus of the Ideas Immanent in Neuron Activity,t' Bulletin of Mathematical Biophysics 5-6, 115-133 (1943-44). The diagrams we use are similar to John von Neumann's modification of the diagrams in the above article; cf. Douglas R. Eartree, Calculating Instruments and Machines, pp. 97-111. $ Though the present paper is concerned exclusively with two-valued logic, its results are to a certain extent applicable to circuits containing wires having more than two significant states. This application can be made by allowing several wires of a logical net to correspond to a single wire of a physical circuit. E.g., ten of the sixteen different states of four binary net wires can represent tn-discrete electricl-'states of a single'ori:;i;cuit wire. tThe theory developed here is directed mainly to electronic computer circuits, though it is to a degree applicable to relay circuits.

2. PRIMITIVE ELEMENTS Since the physical components used in digital computing circuits perform either a logical function or a memory4 function (or both), the logical analysis of these circuits is facilitated by employing distinct primitive elements for these two functions. Moreover, a single primitive is sufficient for each function, so only two primitive elements are required: the stroke element and the delay element. A stroke. element consists of a nucleus with two input wires and an output wire and is symbolized by j. Each (net) wire has one of two states (0, 1) at each discrete point of time 0, 1, 2, 3,.... -Moreover, for each time point t the output wire of a stroke element is' in the state 0 if and only if both input wires are in the state 1; cf. Sheffer's stroke function. A delay element consists of a nucleus, an input wire, and an output wire, and is symbolized by - ---. Each of its wires has one of two states (0, 1) at each discrete point of time, as in the case of the stroke element. The output wire of a delay element is in state 0 at t — O, and thereafter it possesses the state possessed by the input wire at the prior point of time. A net is a finite array of elements interconnected so that only the free ends of wires are connected. A junction (of a net) is a point common to one or more ends of wires. If there is no arrowhead at a junction it is an input junction; otherwise it is an output' junction. An output junction all of whose output wires are stroke element output wires is a stroke output junction; otherwise it is a delay output junction'. We have chosen these primitives because they possess all the following three properties: (1) nets of them are very useful in studying- the behavior of digital computing circuits, (2) they are sufficiently simple to permit convenient logical analysis, and (3) small nets of them correspond to the physical components of digital computers. There are, of course, logically equivalent sets of primitives. The stroke element may be replaced by a conjunctive element and a negative element or by a disjunctive element and a negative element. The stroke element may also be replaced by a material implication element, the equivalent of. L. Material implication is not by itself a sufficient basis for the propositional calculus, but it and the constant falsehood are;1t;the latter may be realized by f in our system, since f(t) - for all t t The British "storage" is better than the American "memory" here, since what we call memory components do not by themselves recall or associate information, but only store it. ttCf. Alonzo Church, Introduction to Mathematical Logic, Part I, p. 3.,....2

Finally, the delay element may be replaced (in the presence of the stroke element) by a binary counter with an input for counting and -an output in the state 0 or 1 according to the state of the counter, or by a flipflop with a set input, a reset input, and an output. It is not difficult to show that the equivalent of a delay element can be constructed from either of these and the stroke element.

3. WELL-BEHAVED NETS For a net N to usefully represent a circuit C there must be a correlation between some of the wires (or sets of wires) of N and some of the wires (or sets of wires) of C such that the states of the designated wires (or sets of wires) of C are represented by the states of the corresponding wires (or sets of wires) of N. Now in any well-behaved circuit the state of every wire at every time t is determinate, and, moreover, all wires joined to the same junction are in the same state. Consequently, we are interested only in nets in which (1) the state of every wire is uniquely determined by the defining properties of the primitive elements and (2) the states of all wires attached to a given junction are the same. We shall call such nets well-behaved (w.b.).t is not well-behaved because it does not'meet the first requirement, while is not wellbehaved because of the second requirement. Physical circuits composed-of components which in isolation realize stroke elements and which are connected according to these diagrams would, of course, have some definite behavior (e. g., the wires of such a circuit might oscillate between two states), but this behavior would be controlled by factors we have deliberately omitted from our idealization and would not mirror the logical behavior of the nets. In this section we shall define precisely the class of well-behaved nets. We begin by correlating to each net a set of logical equations descriptive (in a way to be made clear) of its behavior. -Any propositional function of one variable which ranges over the natural numbers and whose values are 0 (false) and 1 (true) will be called (simply) a function. We associate with each junction of a net a distinct function variable. (These variables will also be used to name the junction and each of its wires.) A variable is an input, output, stroke output, or delay output variable according as its junction is an input, output, stroke output, or delay output junction..Finally, we associate with each net N a set of equations E(N) obtained as follows..For each stroke element with input wires g and h and output wire f write the stroke equation f - Sgh, and for each delay element with input wire g and output wire f write the delay equation f Dg. In accord with the interpretation of our primitives, the first equation is equivalent to ft'gtv ht and the latter is equivalent to fo - O and ft+l - gt, where t ranges over the natural numbers. It is sometimes convenient to have an infinite sequence EO(N),..., Et(N),... of sets of equations derived from E(N) as follows: E0(N) is the result of replacing each stroke equation f- Sgh ~It is worth noting that a circuit might be well-behaved-for a certain combination of inputs and not for others. This suggests defining a concept of wellbehavedness for nets which is relative to a certain class of input: sequences. However, it is simpler to workwith an absolute sense of well-behavd net and this is what we will do here. 4

of E(N) by fo - Sg0ho and each delay equation f Dg of E(N) by fo - 0, while Et(N) (for each t > 0 ) is the result of replacing each f Sgh by ft Sgtht and each f Dg by ft gt1' Given any set of (delay and stroke) equations, a net with which this set is associated may be constructed as follows. Make a junction for each variable occurring in the given set of equations and label it with that variable. For each stroke equation f- Sgh place a stroke element from g and h to f and for each delay equation f- Dg place a delay element from g to f We shall make the correspondence between nets and sets of equations one-one by arbitrarily identifying all sets of equations differing -only with respect to the variables used and with respect to the order of the variables following a stroke operator. The concept of a well-behaved net introdluced informally in the first paragraph of this section may be precisely defined in terms of the uniqueness of the solution of the associated set of equations. A net N with input junctions a1,..,, aJ and output junctions bl,..., bK is well-behaved if and only if for each sequence of functions a1,..., aJ (J O) there exists a unique sequence of functions bl,..., bK (K > O) such that the aJ-s!-tand bk's satisfy E(N).. (Here and hereafter when T: =, fl,..., fI is to be interpreted as denoting the null sequence. ) Some auxiliary notions, of use later, will now be defined. Let T be any transformation or mapping from a sequence of functions fl,.. fJ (J - O) to a function g.t If g is the same for all sequences, T is a constant transformation. (Note that the values of the function g itself are not necessarily the same; e.g., there is a constant transformation to the sequence 010101.... ) A transformation may be regarded as an operation on zero or more denumerable sequences of binary digits ( O's and l's ), the values of the corresponding functions for t = 0, 1,..... Thus the delay transformation D shifts the sequence it operates on one position to the right and places a zero at its beginning. A junction g of a well-behaved net N realizes a transformation T of I arguments (I O0) if and only if among the input junctions aI, oo., aJ of N there are I of them (ahl,..., a h I) such that for each sequence of functions al,..., aJ the g which satisfies E(N) is equal to T(ahl,..., ahI). A junction which realizes a constant transformation is called a constant junction. A constant transformation to g is periodic if and only if there are integers x and y such that for every integer n, gt+nx+y- gt+y' The following theorem shows something concerning the logical power of well-behaved nets. SIf a transformation T1 of I arguments (I - O) and a transformation T2 of J arguments (J > I) are such that there exists a sequence of numbers i1 < i2 <... < iI such that for all fl,..., fJ Tl(fil,.,, fiI) T2(fl..., fJ), then we shall call T1 and T2 the same transformation.

Theorem 3-1: Every constant transformation realized by a wellbehaved net is periodic. Proof,: Consider a w..b.n.,:;N!with junctions gL *, gK where g is a constant junction. Form - from it (with each gk becoming,: gk ) by connecting to all input junctions of N. Since gl realizes a constant transformation,! realizes the same transformation. Since every junction of N is a constant junction, there is a single matrix M satisfying E(N), where the rows of the matrix give the solution for the gk's and the columns mo, mnl... give the state of N for times 0, 1,... respectively. N has at most 2K states, and hence for some x and y, mx = y. Form a new matrix M' such that for t < x, m - mt and for t r x M....t ty M We Mt t - t +y will prove that g' is periodic by showing that M M' Any matrix satisfies E(N) if and only if (1) the first column satisfies EO(N) and (2) for every t greater than 0 the t-lst and t'th columns satisfy Et(N). But if tl and t2 are both greater than zero, Etl(N) and Et2(N) differ only in their arguments. Hence, condition (2) is equivalent to all pairs of adjacent columns, relabelled for t = 0 and t = 1, satisfying E1(N). Now any pair mt 1 and m{ (t > O) satisfies El(N) in this way, for all pairs mt-l and mt satisfied E1(N) in this way, and mtxl, mx is the same pair as mx l, mx (since mx = mx+y )o Since gl is periodic, gl is also. Q.E.D. A transformation T from al,..., aJ to g (J t 0) is primitive recursive whenever g can be defined by the operations of primitive recursion and -substitution.from the successor function, the constant fun-ctions, the identity functions, al,..., aJ.t Something concerning the class of transformations realized by well-behaved nets is given by: Theorem 3-2: There are primitive recursive transformations not realized by well-behaved nets. For example, the constant transformation to ft -1 for t a per fect square, ft - 0 otherwise (i.e., 1100100001...) is clearly a primitive recursive transformation, yet it is a constant transformation which is not periodic and hence by Theorem 3-1 it cannot be realized by any well-behaved net. It is worth noting in this connection that because of its infinite tape a Turing machine44 is not a net in our sense. 1 See, e.g., S.C. Kleene, "Recursive Predicates and. Quantifiers," Transactions of the American -Mathematical Society 53., 42 (1943). Note that in this dAefinition "function'tris usedd in a sense broader than that defined earlier in this section, since it includes any sinrgle-valued function -of one or more natural numbers whose valuesare natural numbers. t+Cf. A. M. Turing, "On Computable Numbers, with anApplication to the Entscheidungs-Problem," Proceedings of the London Mathematical Society 42, 230-265 (193637). 6

4. DETERMINISTIC NETS Not all well-behaved nets are physically realizable. Consider N1: a It is well-behaved, with ct - 1 (for all t ) and hence b0 0, bt+l - at+l and finally dt - at+l. Thus, junction d "anticipates" the future state of input junction a, and the delay element db performs a kind of inc verse delay or predictive operation. Obviously no circuit can perform such a predictive function, for there is no circuit component which can mirror the behavior of the delay element db. More generally, delay elements are intended to represent mechanisms in which signals on input wires cause signals to appear, after a suitable delay, on output wires, and we are interested primarily in nets which allow this interpretation. In other words, we are interested in nets in which all delay elements perform a memory or storage, rather than anticipatory or predictive function. We will call nets of this kind deterministic nets. Consider next N2, formed from N1 by joining a and e. N2 is well-behaved, with eo - O, et+l - 1, bt = et, and dt 1. Though the (constant) transformation to d can, in this case, be realized by a well-formed net which can in turn be physically realized (cf. Theorem 5-7), it is nevertheless the case that the delay element db performs in N2 a predictive rather than a memory function, and that hence N2 is not deterministic. That db does behave in this way may be seen by examining Eo(N2), E1(N2), etc. EO(N2) does not determine a unique value of do; rather, both do E 1 and dO - O satisfy Eo(N2). It is only when E1(N2) is considered that the possibility of d 0 is excluded. This analysis leads directly to one definition of deterministic net. Let N have input junctions al,..., aJ (J - 0) and output junctions b1,.., bK First definition: N is deterministic if and only if for each sequence a,.., ao..; a;t,..., a. (t O) there exists a unique sequence b,... bK satisfying the union of Eo(N),.,, Et(N) Where a net with input junctions is involved, this definition means roughly that the states of the input junctions for the past and the present de termine the states of the output junctions for the present. An alternative conception of determinism is that of the state of the net at the immediate past (tel) and the state of the input junctions at the present (t) determining the state of the output junctions at the present. Since this conception is also useful, we will give a second definition of determinism and then prove that the two 7

definitions are equivalent. Second definition: N is deterministic if and only if both of the following hold: (1) for each a0,..., ad there exists a 1 J 1 b unique b a... bK satisfies Eo(N); unqu, 0such that 1 b' so 0, and (2) if t > 0 then for each a,.., a;.,, aJ and b...,bK bK...;, bK 1 satisfying the union of (N), Et ) I J 1 and each a,., aJ, there exists a unique.b. bt such that atl, J 1 J b1 1Kf Et(N). (bf..., tl;... att,.t; J = O various of the sequences involved are to be taken to be the null sequence as before.) Theorem 4-1: The two definitions of "determinism" are equivalent. Proof: That the second definition implies the first may.be shown by a simple induction. The proof that the first definition implies the second is as follows. Let N be deterministic by the first definition. Then ao1... J aJ,.. atl J K K... a. at..., aJ_ determines a unique b1.., b; btl..., K satisfying the union of EO(N),.., t_(N); and both of these sequences plus 1 J..., determine a unique btl,..., bK satisfying the union of Eo(N),..., Et.l(N) plus Et(N). But since Et(N) involves only the aJ's and bk's at t-l and t, it follows that the a..., aJ;..., aJ; bt1,... b_ determines a unique b,..., bK satisfying Et(N). Q.E.D. This last argument makes use of the fact that long-term memory (i.e., memory lasting more than one unit of time) in a net is the result of a succession of unit delays. This would not be the case, for example, if we had an additional two-wire:.prlimitive':;element capable of n units of delay, n > 1; if that were the case the two definitions would not be equivalent. The class of deterministic nets is a subclass of the class of wellbehaved nets: Theorem 4-2: Every deterministic net is well-behaved. The proof of this is obvious from the definitions. We shall next define some concepts which will be of use in characterizing nondeterministic as well as other kinds of w.b.n. Any junction to which two or more output wires are connected is a multiple junction. A junction f directly drives a junction g if and only if f is the input of a stroke element whose output is g. (Note that the input of a delay element does not directly drive its output.) f drives g if and only if there exists a sequence fl 2,..., fI such that fl is f fI is g, and fi directly drives fi+l for i < I. Note that the driving relation is transitive: if f drives g and g drives h then f drives h. A stroke cycle is a sequence of junctions f0,.., fI-l such that fi Mod I directly drives f(i+l) Mod I It will be observed that N1 and N2 contain multiple junctions, stroke cycles, and delay elements. Not every nondeterministic w.b.n. contains 8

a multiple junction, however, as the following net proves: b6 b5 b4 b3 where the circle with the equivalence sign in it represents a net (constructable from stroke elements) realizing b4 (b a). 1 and hence b2 1 and also bt 1. These two equations impl that bt+l, 6 turn implies that b+1 - at+l. Since bt -bt+l, it follows that b ~at+l, and so the net is nondeterministic. On the other hand, Theorem 4-3: Every nondeterministic w.b.n. contains a stroke cycle and a delay element. It will be simpler to give the proof of the first part in the next section (immediately following the proof of Theorem 5-4). The second half may be stated alternatively: every w.b. stroke net (a net constructed exclusively of stroke elements) is deterministic. The proof of it is as follows. Let N be a w.b. stroke net with input junctions al,..., aJ and output junctions bl,..., bK. Then E(N) contains no delay equations, all functions in Et(N) have t as an argument (never t-l ), and hence the state of the net at t cannot place any restrictions on the state of the net at t-l (and vice versa). Therefore, for each atl,..., there is a unique bt,..., bK satisfying Et(N) [since for each al,.. aJ there i a unique b,., bK satisfying E(N)]. Q.E.D. The basic idea of this proof can be employed to prove a stronger result concerning w.b. stroke nets, namely. Theorem 4-4: All transformations realized by w.b. stroke nets are truth-trans formations. The concept of truth-transformation is defined as follows. Some transformations T (from al,..., aJ ) to g are equivalent to a sequence of mappings TO, T1,..., each Tt being from a sequence of J truth-values to a single truth-value (0,1). If all Tt are identical, T is said to be a truth-transformation. The result that all transformations realized by w.b. stroke nets are truthtransformations is a justification of an earlier statement (Section 2) that the stroke element performs only a logical function; a w.b. stroke net has no memory, its state at a given time never depends on its state at a prior time and never influences its state at a later time. 9

. WELL-FORMED NETS We referred earlier (Section 2) to physical components which perform a logical rather than memory function and have represented these in our system by stroke nets. In actual fact, these components function much the same as the components realizing delay elements in that signals on their input wires cause signals to appear, after a certain delay, on output wires. The differences between the temporal lag inherent in a logical component and that in a memory component are that the former is generally smaller than the latter and generally serves no useful purpose. On this account, and in -the interest of logical siamplicity, our theory includes a temporal delay only in the delay element.. As a consequence, however, we should not expect the requirement of determinism to eliminate all nets in which there is a backward passage of causal influence through stroke elements. Thus in the w.b.n. a b c. information "flows" from the output to the inputs of the stroke element be yet this net is deterministic, with at -ct ct bt. Since no component can mirror the logical behavior of the. stroke element bc (though of course the transformation it realizes is easily realized physically), not all stroke elements in deterministic nets perform functions which can be duplicated by physical components. In the present section we will define a class of nets, called wellformed nets (w.f.n.), which excludes the example just discussed. For reasons given in the next section, this is the most useful class of nets for the study of the behavior of digital computing circuits. There are w.f.n. representing, with various degrees of utility and directness, systems of neurons (in which the time intervals are of the order of one millisecond), some systems of electromechanical relays (in which the time intervals are of the order of milliseconds), and many electronic computing machines composed of vacuum tubes, crystal rectifiers, acoustic delay lines, and electrostatic storage tubes. In particular, w.f.n. characterize very closely the behavior of that type of electronic digital computer whose action is governed by a "clock" which is the source of equally-wide equally-spaced standard pulses (with the time interval between pulses being of the order of one microsecond).t In fact, our theory is especially directed towards such computers. In this case, a 1 4Cf. Hartree, op. cit. 10

represents the occurrence of a pulse and a 0 the absence of a pulse, or vice ver sa. The class of well-formed nets is defined recursively as follows, with the understanding that no net is w.f. unless its being so follows from these rules. (1) (a) EStroke rule] A stroke element is w.f. (b) EDelay rule] A de lay element is w.f. (2) Assume N1 and N2 are disjoint w.f.n. with junctions fl,..., fJ and g1, o.., gK respectively. (a) EJuxtaposition rule] The juxtaposition of N1 and N2 is w.f. (b) [Cascade rule] The result of joining junctions fq. fqI of N1 to distinct input junctions g,.e, gPI of N2 respectively is w.f. (c) EInput connection rule] The result of joining input junctions fP and fq of N1 is w.f. (d) ECycle rule] If all the wires connected to fP of N1 are delay element input wires, then the result of joining any fq -of N1 to fP is w.f. A w.f.n. N may conveniently be studied by means of E(N). E(N) is unitary if and only if no variable has more than one left-hand occurrence (i.e., to the left of the equivalence sign in a stroke or delay equation) in E(N). E(N) is regular if and only if there is an ordering (called a regular ordering) of E(N) such that for all f if f has a right-hand stroke equation occurrence in E(N) then there is no left-hand occurrence of f in that or any later equation. The regular ordering of a regular set of equations can be obtained by using the concept of rank. Ranks may be assigned to certain of the junctions and corresponding equations of any net as follows. First, assign the rank 0 to all input junctions and all delay output junctions to which no stroke element output wires are connected. Then iterate as long as possible the general step: Assign the rank r to all junctions f such that some junction directly driving f has rank r-l and every junction directly driving f has a rank - r-l. Finally, to every equation f - which is such that the junction f has a rank assign the rank of f Theorem 5-1c N possesses no multiple junctions if and only if E(N) is unitary; and N contains no stroke cycle if and only if E(N) is regular. Proof: The first half is obvious. The "only if" part of the second half follows from the fact that the set of equations for a stroke cycle is not regular and hence any set of equations containing them is not regular. That E(N) is regular if N contains no stroke cycles may now be proved as follows. We 11

prove first that since N contains no stroke cycles every junction of N is assigned a rank. Assume some junction f of N has no rank. Then there must be a junction gl which directly drives it which has no rank. In turn, there must be a g2 directly driving gl and without rank, ad infinitum. But there are only a finite number of junctions in N, so some variable gi in the sequence gl, g2,... must occur twice in this sequence. Hence N contains a stroke cycle, contrary to our assumption. Since every junction of N is assigned a rank, every equation of E(N) is assigned a rank, and these equations may be arranged in order of ascending rank. We prove finally that this ordering is regular. Consider any equation of the form f - Sgh, where g is of rank r. Then f is of rank - r+l; any equation of the form g -- is of rSank r and hence must precede f- Sgh. Q.E.D. We next prove Theorem 5-2: N is w.f. if and only if E(N) is both unitary and regular. Proof: We prove first that if N is w.f. it contains no multiple junctions and no stroke cycles. A stroke element or delay element by itself (cf. the stroke and delay rules) contains no multiple junctions or stroke cycles. Moreover, if N1 and N2 contain no multiple junctions or stroke cycles, the result of combining them by any of the four rules of combination will not contain any multiple junctions or stroke cycles. It follows by Theorem 5-1 that if N is w.f., E(N) is both unitary and regular. We will prove the converse by giving a stepwise process for constructing N on the basis of S, a regular ordering of E(N). Let Si be that subsequence of S which consists of the first i equations of S. The net associated with S1 is w.f. (by rules 1, 2c, and 2d) since E(N) is regular. Assume now that Nj is formed from Si_l and is w.f. and consider the itth equation of S. The element associated with it may have two input wires which are paired or not; in the former case use the input connection rule to get N2; in the latter case take the element itself to be N2. N2 may have no input wire connected to a junction of N1 in N or one or more such; in the former case juxtapose N and N1; in the latter case cascade N~ onto N2. Finally, consider the output f of N. Since Si is regularly ordered and unitary, the only occurrences of f other than the left-hand occurrence in the last equation of Si are right-hand delay equation occurrences in the equations of Si. Hence the output of N2 can be connected into the net (if necessary) by the cycle rule. Q.E.D. Theorem 5-3: E(N) is regular if and only if every junction Off N has a rank. Proof: In Theorem 5-1 it was shown that if every junction of N has a rank then E(N) is regular; and also that if E(N) is regular, then N contains no stroke cycles and that if N contains no stroke cycles then every junction of N has a rank. Q.E.D. 12

Thus the following four properties of N are equivalent: (1) N is w.f., (2) N has no multiple junctions and no stroke cycles, (3) N has lo multiple junctions and every junction of N has a rank, and (4) E(N) is both unitary and regular, and any -one may be employed as a criterion of a w.f.n. The formation rules are naturally and simply applied when a net is being constructed. Given a complicated net, however, it may be difficult to determine whether or not it can be constructed by the rules. In this case a test procedure based on criterion (3) is useful. Label all junctions of rank 0, stopping if any are multiple junctions (since then N is not w.f. ). Then iterate the following step as long as possible: label all junctions of rank r, stopping if any are multiple junctions. If this procedure terminates without a multiple junction being discovered, the N is w.f. if and only if all junctions have been assigned ranks (by Theorem 5-3). Theorem 5-4: Every w.f.n. is deterministic, and hence well-behaved. (Note that the example given at the beginning of this section shows that the converse does not hold.) Proof: The determinism of a w.f.n. follows from the fact that (in the presence of unitariness) regularity is stronger than determinism, allowing not only sequential computation with respect to time but also sequential computation at a given time. For each t the state of a w.f. N may be computed by proceeding through a regular ordering S of E(N) as follows. If the equation at hand is a delay equation f - Dg, then for t = 0, fo 0 and for t > 0, ft - gt-l, where gt-l is known from the state of the net at t-l If the equation at hand is a stroke equation f - Sgh, then, since S is in regular order, g and h have no left-hand occurrences in that or any later equations of S. Hence g (h) either has a left-hand occurrence in an earlier equation of S, in which case gt (ht) is already known from the preceding computation; or g (h) has no left-hand occurrence in any equation, in which case it is an input variable and gt (ht) is given. Since E(N) is unitary, this procedure gives a unique value for each ft. Hence N is deterministic and by Theorem 4-2 it is also w.b. Q.E.D. An alternative way of looking at the computation is in terms of rank: the states of all junc.tions of rank 0 may be determined, then those for rank 1, etc. By a procedure similar to that just used, we will now prove the first half of Theorem 4-3, namely that every nondeterministic w.b.:n. contains a stroke cycle. This may be stated alternatively as: Every w.b.n. containing no stroke cycles is deterministic. The proof is as follows. Let N be a w.b.n. with no stroke cycles. By Theorem 5-1 E(N) is regular. Hence the behavior of N can be computed in the manner indicated in the last paragraph, and since N is w.b. the result will be unique. We prove next a theorem concerning the nature of the subnets of a w.f.n. N1 is a subnet of N if and only if N1 may be formed from N by 13

a succession (perhaps null) of the following operations~ (1) separating a wire from a junction, and (2) deleting an element. Theorem 5-5: N is w.f. if and only if all the subnets of N are w.b. Proof: If N is w.f., it contains no multiple junctions or stroke cycles, and hence neither do any of its subnets. Therefore each of its subnets is w.f. and hence w.b. We prove next that if N is not w.f. it contains a subnet which is not w.b. There are two cases to consider, according to whether N contains a multiple junction or not. (1) Suppose N contains a multiple junction f such that f and f -... are in E(N). Separate the input wires of the elements associated with each of the equations from their junctions. The result is not w.b. (2) Suppose N contains no multiple junctions but does contain a stroke cycle fO,..., fI-1 We may assume without loss of generality that the associated sequence of equations is fI-1 = SfI-2 gI-2, -SfI-1 gTI1 If any of these equations is of the form p - Sqq, separate one of the input wires of the corresponding stroke element from its junction, making it a net input. Then if any gi input wire of an element corresponding to one of these equations is connected to an output junction, separate it from that junction so that it is a net input. The result is not w.-b., as may be shown by applying l's to all input junctions. Q.E.D. We next state some theorems concerning the transformations —realized lby w.f.n. Theorem 5-6: A transformation is realizable-by a w.f. Usttoke net if:and only if it is a truth-transformation. Proof: We have already proved (Theorem 4-4) that all transformations realized by w.b. (and hence by w.f. ) stroke nets are truth-transformations, so it need only be proved that all truth-transformations can be realized by w.f. stroke nets. Since Sheffer's stroke function is a sufficient primitive for defining all truth-functions (in the logical sense), it is a sufficient primitive for defining all truth-transformations. The process of definition involves su-bstitution and the use of the same variable in more than one argument place; these are mirrored by the cascade rule and the input connection rule, respectively. Q.E.D. The last half of the theorem shows that (in the presence of the formation rules) a stroke element is a sufficient primitive for our purposes. It follows from the definition of truth-transformation that there are only two constant truth-transformations: gt - 1 and its negation ht -. The former is realized by the w.f.in. - g which is df Priteest because it is a realization iin dur system of a Tiick". (Note the fact-mentioned earlier in this section-that our theory is especially applicable to circuits synchronized by pulses from a standard clock. ) Theorem 5-7~ A constant transformation is realized by a w.f.n. if and only if it is periodic. 14f

Proof: The "only if" part of this theorem follows from Theorems 3-1 and 5-4. We prove the converse by showing how to construct a net realizing any g such that gt+nx+y gt+ The net c~ c1 cY-1 Cy d c0 dX-2 from certain c's dX-l -v | from certain dJ's Cog is a schematic construction of the desired net, where fj represents a J-input disjunctive net, readily constructed from stroke elements. Note that O - 1, t+l-, and in general ct - if and only if t = i, while dt 1 if and only if t = + nx+ y. For a particular constant transformation to g this schema may be converted into a net realizing this transformation as follows. If gt a 1 for any t less than y, connect ct to one of the inputs of the disjunctive net whose output is g; if gt - 1 for any t as large as y and less than x+y, connect dt to one of the- inputs of the disjunctive net whose output is g. g is the desired junction. Q.E.D. Theorem 5-8: Every transformation realized by a w.f.n. is primitive recursive. The proof is too long to be included here (it is given in the appendix), but the essential idea is as follows. Let N be w.f. with input junctions al,., aJ and output junctions b bK Since the behavior of N can be computed in the manner indicated in the proof of Theorem 5-4, it is possible to define a mathematical function F (from natural numbers to natural numbers) which is primitive recursive with respect to the aJ's and is such that 1 2 K-l K K-l K 15K-1 15

6. W.F.N. AND DIGITAL COMPUTING CIRCUITS In this section we will discuss the realization of w.f.n. by digital computing circuits. Consider first the fact that both the delay element and the stroke element (or small nets of it) are realized by physical components in which the input wire state(s) causally determine the output wire state. The output of the physical realization of a delay or stroke element in isolation has the property that its state can be causally determined by the state(s) of its input wire(s) and the formation rules for w.f.n. are such that every output wire of a circuit realizing a w.f.n. has this property. Thus the backward passage of causal influence through stroke elements (cf. the first net discussed in the preceding section) never occurs in a w.f.n. Hence, as far as these considerations are concerned every w.f.n. is physically realizable. There are, however, certain aspects of our idealization of a stroke element which require this conclusion to be restricted. In particular, though the delay of a component realizing a simple stroke net is generally small compared to the basic unit of time of the system, the same does not hold for circuits composed of such components. A practical way of dealing with this point is to construct circuits which perform fairly simple logical transformations and then feed the result into a delay line (as well as into power amplifying and retiming circuits), the temporal lag of the line being such that the total delay is one or a few units of time. This involves placing an upper limit on the allowable rank of a junction and on the number of junctions which drive a given junction. These restrictions could be removed from the net theory by taking as a primitive element, e.g., astroke element driving a delay element, but the additional complications would not be worth the gain. In any event, there is an overall size limitation on the realizability of w.f.n. The discussion of Section 4 showed that if a circuit is represented by a well-behaved net that net is deterministic. Consider now the question: Are there any circuits represented by deterministic nets which could not be adequately represented by w.f. nets? To keep the range of application of the logic of nets as broad as possible, we have left the concept of representation (and its converse, realization) somewhat indefinite. It is sufficiently broad that some so-called "static" circuits and some mixed static and pulse circuits, as well as some pulse ("dynamic") circuits can under suitable limitations be represented by w.f..n. The answer to the above question depends on the particular interpretation made and hence we will not attempt to give a general answer here; we will, however, make a few relevant comments. Engineers sometimes connect the outputs.of two or more physical components together; this is a way of realizing logical disjunction and is better represented in our system by stroke nets realizing logical disjunction than by nets containing multiple junctions. Also, feedback loops are sometimes employed for memory purposes (as in the "flipflop"), but these are better represented in our system by means of delay 16

elements rather than by stroke cycles.: On the other hand, consider the following example of a deterministic net not w.f. -which may be physically realized in one sense of physical' realizationo Start with a single physical component realizing f - (g. ah) and connect its inputs together so that f - (g. ~-g) 0. Its physical behavior would probably be unaffected by connecting its output back to its input. Note, however, that this connection, which introduces a stroke cycle in the corresponding net, is pointless, since it neither increases the number of transformations realized nor decreases the number of elements in the net. Thus this example gives rise to the following two theoretical questions which are worth investigating: (I) Can deterministic nets not w.f. realize transformations not realized by w.f.n.? and (II) Can they realize some transformations more efficiently? The answer with regard to (I) is given by: Theorem 6-1: Every transformation realized by a deterministic net is realized by a w.f.n. Proof: Let N be deterministic with input junctions al,..., aI, delay output junctions bl,..., bJ, and stroke output junctions cl,..., cK; and let N be the desired w.f.n. whose junctions include the corresponding junctions l a; b..I., bJ; and 1,. We define a sequence of truth-values (0,1) xl,..., xj to be admissible trelative to E(N) ] if and only if it satisfies either of the following two conditions (cf. the second definition of determinism): (1) it consists of all O's, and (2) there is some t > 0 and some sequence a... a b. b 1 K 1 I 1 J 1 K co,... c0;;.; at,., at; btl..., b; clt,..., ct satisfying the union of Eo(N),..., Et(N) and such that for each j, bi = xj. Let Et(N) consist of all equations of Et(N) of the form ck- (i.e., of the form ck - S... ). Since N is deterministic it then follows that for each at,...at and each admissible bt..., b there is a unique 1t, K 1 I 1 Ja 1 K c,. K. such that a1, a; bt,..., ct satisfies Et(N)... ck t t ~ t k b1 I Now define for each c a mapping Tt as follows: for each at,... a' J) and each admissible bt,..., b T(a,..., b) is that value of ct which satisfies Et(N); for each at,.., a and each nonadmissible bi,..., b= Tk(a,...a. bJ). Since each bt,...tt - Et(N) is of the same form (i.e., a difference in t involves only a difference in the arguments), we may define for every ck a truth-transformation Tk equivalent to the sequence of mappings To, T,. The net N may now be constructed as follows. For each bJ pick an equation of E(N) of the form bJ - Df and connect a delay element from f to bj in By altering the defining equations of a stroke-element we can obtain a "stroke net" which performs a memory function. For example, a net with inputs s (set) and r (reset) and junctions f and g such that f - ('- se g) and g - [E f'(~or v s) is a representation of a flip-flop under the stipulation that if st E rt 0 O then (1) if t = 0, then ft O and (2) if t > 0, then ft-1 17

N For each ck of N construct a w.f. stroke net (cf. Theorem 5-6) from the ai's and bJ's realizing Tk. The transformations realized by the bj's and ckts in N are the transformations realized by the bj's and ck's of N respectively, and since no stroke cycles and no multiple junctions were created in the formation of N, I is w.f. Q.E.D. Consider now question (II). This involves the concept of simplicity. For nets composed of stroke and delay elements a rough measure of simplicity is given by the number of each. Some results concerning this rough measure will now be stated. Let us arbitrarily define N1 to be as simple as N2 whenever Nj. has no more stroke elements and no more delay elements than does N2. It should be remembered that logically equivalent primitives are not necessarily equivalent where simplicity is involved, so our subsequent theorems on simplicity do not necessarily hold for alternative sets of primitive elements logically equivalent to the set consisting of the stroke and delay elements (see Section 2). Question (II) can now be more precisely stated: Given a deterministic net N not w.f., is there a w.f.n. as simple as N which realizes the same transformations as N? The answer is in the negative, for. Theorem 6-2: There is a deterministic net N such that no w.f.n. realizing all the transformations realized by N is as simple as N. Proof: Let N be: a k 511 /a2 a5 b ab b5 N contains the stroke cycle b1 b2, b3, b4 and hence is not w.f., but by Theorem 4-2 it is deterministic. It is easily verified that N realizes the distinct transformations 1 (a1 v a3) b3 - al v a2 b4 a3 v Ha! a b5 - 1al 18

Consider now a w.f.n. N1 with (at least) junctions bl, b2, b4, and b5, -realizing the corresponding transformations. For each b, 1 k ~ 5 there must be exactly one equation in E(N1) of the form bk -. Replace b5 -S _ by b5 Saa1; this modification of N1 does not change the total number of stroke elements in N1 nor the number of transformations realized by N1. Let the minimal rank of b b2 b 4 of N be R and let bx be one of the junctions b1 b2, b, b4 of N1 of this minimal rank. None of rthe transformations bl, b2, b5, b4 is equivalent to Sfg where f and g are a1, a2, a3 or b5, and hence bx cannot be realized from al, a2, a5, b5 by less than two stroke elements. Consequently, there is a junction b6 directly driving bx which is different from al, a2, a5, and b5. b6 is of rank less than R and hence realizes a transformation different from those realized by bl, b2, b3, and b4. But N1 contains five other junctions realizing b, b2, b b4 and b5, and so N1 contains at least six stroke elements. Q.E.D. The set got from E(N) by replacing b1 = Salb4 by b1 Salb6 and b6 Sa3a3 is associated with a six-stroke-element w.f.n. that realizes all the transformations realized by N Because Theorem 6-2 holds it is of interest to find necessary and sufficient conditions for a deterministic net to have the property that there exists as simple a w.f.n. realizing the same transformations. We have obtained a sufficient condition for this property involving the concept of a properly driven net. Any junction of a net N is defined to be a properly driven junction of N if and only if it belongs to the smallest class satisfying the following rules: (1) *each input junction and each delay output junction is properly driven, and (2) if g and h are properly driven and f = Sgh, then f is properly driven. A properly driven net (p.d.n.) is then defined to be a w.b.n. in which every junction is properly driven. The key theorem concerning p.dqn. is formulated in terms of the following concept. A set of equations E' (N) is a complete subset of E(N) if and only if for each output junction f of N E'(N) contains at least one equation of E(N) of the form f. This key theorem is: Theorem 6-3: If N is p.d. E(N) contains a complete subset E'(N) which is unitary and regular. Proof: E'(N) may be constructed as follows. For each delay output junction f of N select one equation of the form f - D-. Then iterate the following step: Add to E'(N) any equation f - Sgh of E(N) satisfying the following conditions: (1) there is no equation of the form f -E already in 19

E'(N); (2) both g and h satisfy the condition of having a left-hand occurrence in an equation of E'(N) or being an input variable. It is obvious from its mode of construction that E'(N) is unitary and regular, and it follows from the definition of a properly driven junction (since the above procedure will catch every properly driven junction and hence every junction of the net) that E'(N) is a complete subset of E(N). Q.E.D. We can now prove: Theorem 6-4: If N is p.d., there is a w.f.n. as simple as N realizing all the transformations realized by N Proof: The required w.f.n. is any subnet of N to which is associated a complete subset of E(N) which is both unitary and regular. Q.E.D. Theorem 6-3 also leads directly to: Theorem 6-5: Every p.d.n. is deterministic. A characteristic distinguishing p.d.n. from deterministic nets is given by: Theorem 6-6: Every stroke cycle of a p.d.n. contains at least one multiple junction. Proof: For if N is p.d. and contains a stroke cycle which has no multiple junctions, any complete subset of E(N) must contain the equations of this stroke cycle and hence cannot be regular. Q.E.D. 20

APPENDIX In this appendix Theorem 5-8 concerning primitive'irecursive functions will be proved. This will be done in two steps; first a lemma concerning primitive recursive functions+ will be established and then the lemma will be used to prove the theorem. A function A is said to be primitive recursive with respect to the functions B1,..., BI whenever A can be defined by the operations of primitive recursion and by substitution from the successor function, the constant functions, the identity functions, and Bl,..., BI. If B1,..., BI is the null sequence, A is simply said to be primitive recursive.ei The lemma we will first establish is: Lemma A-1: If A is definable by the schema: A(O) = yO,..., A(M) = yM, where yO,''', YM are natural numbers; A(n+M+l) = C rA(n),..., A(n+M)], where C is primitive recursive with respect to B1,.o., BI; then A is primitive recursive with respect to B1,..o, BI Proof: Let py denote the y'th prime number in order of magnitude (po = 0, p = 2,... ) [p. 13]. An integer x N 2 is said to be in Godel form whenever it is in the form Pi P2.. PN, where each z is a natural number and PN is the largest prime factor of x; e.g., 2 3O 51 is the Godel form of 20. L(x) is the number of exponents (counting the zero exponents, if any) of the Godel form of x and nGlx is the n'th exponent In this appendix "function" is used in a broader sense than that defined in Section 3, since it here covers functions with any finite number of arguments and with any natural number as value. 14 See Kleene, op. cit., p. 42 and "On Undecidable Propositions of Formal Mathematical Systems," notes on lectures by Kurt Godel, Institute for Advanced Study, Princeton, New Jersey, 1934, p. 2ff. We will assume the contents of the latter work throughout this appendix and will give page references to it in brackets. Alternative references are: Kurt Godel, "'TUer formal unentscheidbare Satze der Principia Mathematica und Verwandter Systeme I," Monatshefte fur Mathematik und Physik 38 (1931), 173-198. S.C. EKleene, "General Recursive Functions of Natural Numbers," Mathematische Annalen 112 (1936), 727-742. 21

(counting from the left) of the G8del form of x (if x < 2 then L(x) = nGlx = 0 and if n > L(x) then nGlx = 0 ) Ep. 13]. We next define a shifting function Sh(x) which, if L(x) > 1 denotes the result of deleting the leftmost exponent and the rightmost prime of the Godel form of x and shifting all exponents one place to the left: Sh(x) - 22Glx. 3Glx. L. pL(x)Glx -Shx) PL(x)-l if L(x): 1 then Sh(x) 1. E.g., Sh(24 -9 50 7) = 29 5 58 and Sh(22) = 1. The functions p, L, G1, multiplication, and exponentiation are primitive recursive [pp. 3, 13], and hence Sh is. We next define a function U by primitive recursion as follows~ u(O) = 2.0' 3Yl.'.. pYM M+l C[lGlU(n),..., (M+l)GIU(n)] U(n+l) = Sh[U(n)] PM+1 Since C is primitive recursive with respect to the B i's and since Sh, multiplication, and exponentiation are primitive recursivei, it follows that U is primitive recursive with respect to the Bi. Now the first exponent of the G~del form of U(n) is A(n); i.e., A(n) = 1 G1 U(n) We shall prove this by showing that A(n+m) (m+l) G1 U(n) 0! m -1 M This obviously holds for U(O). We shall assume it for U(n) and prove it for U(n+l) o By the definitions of U and Sh u2GlU(n) (M+i)GlU(n) C[lGIU(n),..., (M+l)GlU(n)] U(n+l) = 2 PM PMtl and hence by the inductive assumption U(n+l) = 2A(n+) A(n+M) pA(n) A(n+M). But by the definition of A in the lemma, the exponent of PM+i equals A(n+M+l), and hence A(n+l+m) - (m+l) G1 U(n+l) O - m M. SActually it is required that these functions be primitive recursive with respect to the Bi's, but this is also the case. 22

Since A(n) = 1 G1 U(n), G1 is primitive recursive, and U is primitive re-. cursive with respect to the Bi's, A is primitive recursive with respect to the Bi's, and the lemma is proven. Q.E.D. Consider now: Theorem 5-8: Every transformation realized by a w.f.n. is primitive recursive. Proof: Let N be w.f. with input junctions a1,.., aJ (J - 0) and output junctions bl,..,1 bK (K > O) in regular order. If J = 0 every transformation realized by N is constant and periodic and the theorem is trivial, so we will assume J > 0 The concept of a transformation beiig primitive recursive was defined as follows in Section 3: A transformation T from al,..., aJ to T(a19.o, aJ) (J' O) is primitive recursive whenever T(al,..., aJ) can be defined by the operations of primitive recursion and substitution from the successor function, the constant functions, the identity functions, and al,..., aJ. In the terminology that has been introduced this is equivalent to requiring that T(a1,..., aJ) be primitive recursive with respect to al,..., aJ. The proof of the theorem will consist in showing that each bk is primitive recursive with respect to a, aJ A function W, which will correspond to the function A of Lemma A-I, which will have values b... b... b and which is primitive 0' 1' Y ** *.., d. which is primitive recursive with respect to the aJ's, will be defined next. Let x = y Mod z be a propositional function having the value 1 when the relation holds and 0 otherwise, let -x have the value 1 when x = 0 and 0 otherwise, let x v y = Maximum (x,y), let x' y denote x - y if x =- y and otherwise O, and let x*y denote the integral part of the quotient x/y; all of these functions are primitive recursive [cf. pp. 3, 4, 14]. W is now defined: 1 K 1 K W(O) = b,..., W(K-1) = b0; W(K) = bl,...,W(2K-1) b W(n+2K) = (n = 0 Mod K)wl +... + (n = K-1] Mod K)wK, where the wk are defined in the cases considered below. Note that for a given value of n all the coefficients on the right-hand side of the previous equation are 0 except one. Case 1: b is a stroke output variable. Suppose that bk = Sbklaj, where k1 < k since the bk are in regular order. Then wk abbreviates — W(n+L2K'kI +k1) v atn+2K)K. If the rightmost two variables of bk StbklaJ are commuted, or they are both input variables or both output variables, the definition of wk is similar. 23

Case 2: bk is a delay output variable. If bk - Dbkl, wk abbreviates W(nfK'j-kkl); while if bk - DaJ, wk abbreviates a(n+K)*K We will prove that W is primitive recursive with respect to the aJ's by showing that it satisfies the hypothesis of Lemma A-1. Since the bk are in regular order, each of the values W(O),..., W(M), where M = 2K-1, can be determined from E(N). Hence W(O),..., W(M) satisfy the conditions imposed by Lemma A-1 on Y0,.., YM. Since x = y Mod z,., *, +,, v, and ~ are all primitive recursive functions, the second line of the definition of W accords with the schema of Lemma A-1 provided that all occurrences of W on the right-hand side have arguments in the range n,..., n+2K-1. As before, there are two cases to consider. Case 1: If bk Sbklf or bk -Sfbkl, then we have 1 5 k, kl K, and kl < k, and hence O [E2K'k]+ kl _ 2K-1. If bk - SaJa2, then wk does not contain W Case 2: If bk - Dbkl, then we have 1 ~ k, k K, and hence O L [Kk]+-kl L 2K-1. If bk - DaJ, wk does not contain W Hence W is primitive recursive with respect to the aJ's. 1 K 1 KWe prove finally that the values of W are bo,... b; b... K 0, 0' 1, bl;... by showing that k bt = W(tK+ Ck 1]) That this holds for tK + [k'l] = 0,..., 2K-1 is readily verified. We assume that it holds for tK + [kil] = 0, 1,..., z where z' 2K-1 and prove that it holds for tK + Ck:l] = z+l where (since z+l - 2K ) t - 2. Since t' 2 W(tK + [k:l]) = wE(t:2)K + (k:l) + 2K] and hence by the schema defining W W(tK + [k:l]) = (n = 0 Mod K)wl +... + (n = [K 1] Mod K)wK, where n = (t:2)K + (k'l). But then n = (k'l) Mod K and W(tK+ k'lj)= wk The result may now be established by proving that wk = bk. Two cases are cons idered. Case I: Suppose bk Sbklaj. Then wk = ~W(n+[2K-k]+kl) v ~aln+2K)K. But since n = (t':2)K+ (k'l) and 1 d k L K, wk = ~W(tK+[kl:l]) v,at. Since kl < k, the inductive 24

kl assumption guarantees that W(tK+ [kl:l]) = bt, and hence that wk = Abkl vHa1 t = b. If the rightmost two variables of bk - Sbkla are commuted or they are both input variables or both output variables the proof is similar. Case 2~ Suppose bk Dbkl. Then wk = W(n+[K'k+k). But since n = (t:2)K+ (k'l), wk = W([t- l + [kil']). Since t - 2 and 1 - k, kl - K, (t-l)K+ (kl1l) < tK+ (k1l), and so by the inductive assumption we have wk = bkl = btk k Da Bk t-l t. Suppose bk = DaJ. Then wk = an+K)K But since n = (t2)K+ (k;l) and k K, wk=a l" = bt. Since bk = W(tK+Ckzl]), W is primitive recursive with respect to the aJ's, and., +, are primitive recursive, it follows that bk is primitive recursive with respect to the aJ's. This fact, in the light of the definition of a primitive recursive transformation, implies that the transformation realized at bk is primitive recursive and Theorem 5-8 is proved. Q.E.D. We conclude with a remark relating the two-stage proof given here to the function F, introduced in the text for the purpose of suggesting a method of proof. If the function A of Lemma A-1 is taken to be W, then the function U defined in the proof of the lemma has the form: U() b2 bK-1 bK u(o) 2.P2K-1' l 2K b b b () = 2 0,3b. bK b2 u.l). 2 3P2K-1 P2K and in fact may be shown to be the function F 25

INDEX OF TERMS The page numbers refer to occurrences-of the terms where they are defined or explained. Term Page Circuit........................ 1 Drive..000...............O.......8 Drive, directly......a.... 8 Element.............. 0 2 Element, delay........................2 Element, stroke -..-...-.........-......2 Equation, delay.ala.....4 Equation stroke..O............4 Equations set of EE(N)J]......................... o. 4 Func t i on...................40 4 Godel form... 0 21 Junction..................... o..... 2 Junction, constant.................. 0..5 Junction, input................. 2 Junction, multiple.....................8 Junction, output...................... 2 Junction, delay output...................... 2 Junction, stroke output...........................2 Junction, properly driven..... o. 19 Net..1....., 1 2 Net, deterministic........................ 7, 8 Net, properly driven............ I19 Net, stroke...9 Net, wellbehaved (w.b.n. ).................... 5 Net, well-formed (w.f.n)................ 11 Periodic....................................5 Primitive recursive.....................6, 21 Primitive recursive with respect to.................. 21 Rank............... 11 Realize a transformation. 0.......... 0. 5 Realize, physically............................ 1 Regular..11 Represent..............................1 Simple................................ 18 Subnet.............................. 13 Subset, complete................ o 19 Transformat ion................................ 5 Transformation, constant........ 5 Transformation, periodic......,.. 1.o n..5 Transformation, primitive recursive....................6 0 Transformation, truth a...........9 Unitary................. 11 Variable....................4 Variable, input............... ~..4 Variable, output..............4 Variable, delay output...........................4 Variable, stroke output.......................,.. o 4 Wire...............2 Wire, input......2.......................2 Wire, output.................................2

UNIVERSITY OF MICHIGAN 111111113 90 15 02947 479111111 3 9015 02947 4791