ENGINEERING RESEARCH INSTITUTE UNIVERSITY OF MICHIGAN ANN ARBOR THE LOGICAL DESIGN OF AN IDEALIZED GENERAL-PURPOSE COMPUTER ARTHUYR W.. BU.R IRVING M. COPI Project 1828 BURROUGHS CORPORATION RESEARCH CENTER PAOLI, PENNSYLVANIA 30 October 1954

,i" "

ii Table of Contents Section Page Preface iii 1. Introduction 1 2. The Computer and its Parts 2 3. Logical Symbolism and Diagrams 5 4. STORAGE g 4.1. Information 9 4.2. Cells and Storage Bins 10 4.3. Address Decoder 14 4.4. Serial Storage 17 5. ARITHMETIC UNIT 20 5.1. Machine Arithmetic 20 5.2. Operation of the CONTROL 25 5.3. The Functions of the ARITHMETIC UNIT 27 5.4. Execution of the Arithmetic Instructions 29 6. CONTROL 53 6.1. ADDRESS COUNTER 33 6.2. CONTROL CLOCK 37 6.3. OPERAND DECODER 39 6.4. Operation of the CONTROL 40 Footnotes 44 Bibliography 46 Figures 47 Appendices 56 A. Some Operations of the ARITHMETIC UNIT 56 B. Machine Solution of a Simple Problem 59 C. Multiplication 62 D. Arithmetic Operations on Instruction Words 66 E. Logical Design of the ARITHMETIC UNIT 68

iii Preface This is the second (and last) report of a series of which "Theory of Logical Nets" C2] was the first. We shall make some comments about the relations of the two reportso "tTheory of Logical Netst' gives a foundational analysis of logical nets (diagrams of digital computing circuits) in general0 This second report presents a particular logical net, which represents the structure of an idealized general-purpose digital computer0 Thus the first report contains the foundations for this second one, which prep sents an application of the nets analyzed in the first reporto The logical design of the general-purpose computer presented here was worked out by the first author independently of Project 1828, It was this work that stimulated the research already embodied in the first report, Since this design shows how the nets of the first report may be used, it seemed desirable to present the logical design of the computer as a second report in the series0 In doing so we found it necessary to work out a set of logical formulas describing the behavior of the computer, and, since this material is of interest as an application of symbolic logic to computers, we have embodied it in the present reporto

THE LOGICAL DESIGN OF AN IDEALIZED GENERAL-PURPOSE COMPUTER1 1 o Introduction There are many known complete logical designs for general purpose digital computers, but all of them are in terms of specific systems of equipment and most of them are very complex. That complexity is enforced not entirely by logical but also by engineering considerations pertaining to the physical problems involved in the actual construction of a machine. It seems desirable, therefore, to present a design for a complete generalpurpose digital computer which shows its basic logical structure in abstraction from the engineering problem of realizing that structure physicallyo We give such a design in the present paper, patterned in a general way after the machine described in [l] o Since we use some of the techniques of symbolic logic in its exposition, our logical design is much more atlogical~' than is usually implied by the use of that term0 The present paper is intended to serve two important purposes. First, as has been said, it is intended to show what is logically required for a general-purpose computer as distinguished from what is required physically, the latter being relative to the present state of the computer

art. Second, it is intended by abstraction from the requirements of equipment to show how a design can be obtained which is much simpler, though admittedly idealized. and hence much easier to understand. Our presentation should have pedagogical value for communicating the basic structure of a general-purpose machine to those acquainted with the rudiments of symbolic logic but lacking in engineering background0 The present paper is a continuation of [2], which gives a foundational analysis of logical nets (diagrams of digital computing circuits) in general0 The structure of our idealized general-purpose computer is here represented by a particular kind of net studied in [21, the well-formed net0 2o The Computer and its Parts0 Our automatic computing machine contains three main parts with communication channels between them (Fig0 l)o The first part is the ARITHMETIC UNIT, which performs the arithmetic operations of instructions 4, 5, 6, 7, 8, and 9 of Fig. 2, and which "senses" the end digits of a number when that is required for the execution of instructions 13 or 14o The second part of the computer is its STORAGE, whose

bins contain both numbers to be operated on and instructions to perform specified operations. The STORAGE contains two parts, a serial storage and a parallel storage0 The parallel storage contains 49096 storage bins- bin 0, bin 1, bin 2, o o0o bin 4095, whose numbers constitute the addresses of the binso The machine must provide a path along which numbers can be transferred between the STORAGE and the ARITHMETIC UNIT when instruction 4, 5, 6, 79 10, or 11 is executedo In our computer this path is the trunk line t, whose sixteen components t, t1, o o9 t15 are represented by horizontal lines connecting the ARITHMETIC UNIT and the STORAGE in the lower part of Fig0 lo For the machine to solve a problem it must be given a list of specific instructions, whose execution will result in the solution to the problem. The execution of these instructions is under the direction of the CONTROL, the third main part of the computer, which consists of all the equipment of Fig0 1 not yet describedo Instructions for the machine are stored in order in bins of the parallel storage, and, except when it is instructed to t'jumps (see 12, 13, and 14 of Figo 2), the computer executes these instructions seriatim, To this end count must be kept of the instructions as they are executed; this function is

performed by that part of the CONTROL called the ADDRESS COUNTER, which at any given time will contain the address of the bin storing the next instruction to be executed. A set of instructions for the machine to execute in solving a problem is a routine, and every routine, however complex, is constructed out of a small number of primitive or basic instructions (the fourteen listed in Fig. 2)o As each instruction emerges from the STORAGE it goes to the CONTROL, and that part of the CONTROL called the OPERAND DECODER then stimulates the appropriate control wires to make the other parts of the computer perform whatever functions are required for the execution of that instruction, Eleven control wires lead from the CONTROL to the other parts of the machine: six, bearing the general label A, from the OPERAND DECODER to the ARITHMETIC UNIT; and five, labeled S, from the OPERAND DECODER to the STORAGE. There are also two control wires, labeled C, which connect different parts of the CONTROL, both Cr and Ct lead from the OPERAND DECODER and CONTROL CLOCK to the ADDRESS COUNTER, and Ct leads also to the equipment in the center of Fig. 1 labeled ti. Different basic instructions cause the CONTROL to stimulate different sets of control wires, as indicated in Fig. 20 How these various parts perform their functions will be explained in detail: the STORAGE in Section 4, the ARITHMETIC UNIT in Section 5, and the CONTROL in Section 6o

3l 3_ Logical Symbolism and Diagrams~ Since our diagrams are logical nets in the sense of [2, the lines in them represent wireso Each net wire in our diagrams is in one of two states (0,1) at each discrete moment of time 0 1, 2,9 oo o (Whenever we use -T as a time variable, it ranges over discrete moments O, 1, 2,... unless otherwise stipulated0) The two states 0 and 1 are complementary; they correspond to the truth values false and true, respectively0 In our diagrams control wires are labeled with capital letters, other wires (information wires) are labeled with small letters from the Latin or Greek alphabets0 To assert that the wire labeled f is activated or stimulated at time -T we write either f, f(T) f = 1, or f(T) 1; and to assert that it is inactive or not stimulated we write either f - O or f(T) - Oo Thus the symbols used to label wires are systematically ambiguous: any such symbol f is on the one hand a label for the wire beside which it appears, and on the other hand it is a function symbol f(7T) whose argument rY' ranges over successive discrete moments of time and whose values are the wire states 0 and lo Our primitive logical symbol, the stroke function f g, means not both f and g, and the corresponding diagrammatic stroke element appears in Figo 3a as a square

nucleus with two input wires (f and g) and one output wire f |g (as in L2] ) Other logical symbols we shall use are: negation, f (or alternatively — f), meaning not f; (inclusive) disjunction, f vg, meaning f andjor g; conjunction fg (or alternatively fog), meaning f and &; material implication, f o g, meaning not f or ~; equivalence, f g, meaning f and g or not f and not g; and inequivalence, f t g, meaning f and not g or g and not f. Just as these six functions can be constructed out of the stroke function (see ppo 255-256 of [4] ), so the six corresponding diagram elements can be constructed out of stroke elements, as shown in Figs, 3b, c, d, e, f, and go2 Each right-hand diagram in Figs. 3b, c, d, f, and g is a definitional abbreviation of the diagram to its left, Having introduced the symbol for negation, we have additional ways to assert that wire f is inactive at time'T o, f (T), f = and f(T() = lo Similarly we could assert that it is active by writing f 0 or f(7T) = 0o The inequivalence element has many properties which make it very useful in computer worko It can be used as a complementer, for if either input is in state 1, the state of the output wire will be the complement of the state of the other input (this application was first pointed out in [7])0 We shall later (in Section 5) make use of the following properties of inequivalence: it is both associative

70 and commutative, and fl f2 0 ~~~ $ fN is true Just in case an odd number of its arguments are true. That it has these properties is readily proved by induction on the number of arguments, Hence we can have an inequivalence element with any number of inputs (see Fig0 7 for a 3-input inequivalence) o It is convenient also to introduce a generalized threshold element having I positive input wires fls f2 ~~~ fI and J negative input wires (a negative input wire to an element is one which attaches to that element through a negation element) gls R29 ~ oo Egj and a positive integer threshold To Such an element is diagrammed in Fig. 3h, and its behavior is characterized by the equation h- E fi+ L-io) - where and - have their usual mathematical significance03 For any I, J, and T 0' O the threshold element is easily constructed out of elements already available0 Where T > I+ J, h- 0 and the construction is trivial. The equation for the non-trivial case is an inclusive disjunction whose disjuncts are all possible conjunctions of T arguments from the set of It -J arguments {fl - f 2' 00~' fI' Rl E29 ~~~ Ej}, and hence may be realized by a net containing only negation, conjunction, and disjunction elements (see Theorem 12 of E2J )o It

8o should be clear that disjunction and conjunction elements with any number of input wires are special cases of our generalized threshold element. A second primitive element used in representing digital computing circuits is the delay element, which appears in Figo 3i as an oblong nucleus with one input wire f and one output wire go As in the case of the other elements, each of its wires possesses one of the two states (0.1) at each discrete moment of timeo the output wire $ is in state 0 at - = 0, and thereafter it possesses the state possessed by the input wire at the prior moment of time. The equations which describe its behavior areg(0) - O and (Q-f- 1) f(T) for every time'To We use two additional primitive elementsg an input key whose activation puts the wire attached to it into state 1, and an output light which emits a visible signal if and only if the wire attached to it is in state 1, These are diagrammed as circles with the letters K or L in their interiors, as in Fig0 4o They represent relatively slow ways in which the operator can insert or receive information from the computer0 We use only nets that are well-formed in the sense of L2], but to simplify our diagrams we sometimes omit arrowheads and wires, as between the small and large circles in Figso 3e and 3g, and we sometimes show arrowheads going both

90 ways to avoid duplication of wireso We also allow a multiple Junction, that is, a confluence of n' 2 output wires, to abbreviate an n-input disjunction element in the manner of Fig, 3J, whose behavior is governed by the equations (fv$vh) i -i ko And we place a dot at the intersection of two lines to indicate that the wires represented by those lines are connected, as at the left of each right-hand key in Figo 4o Our final convention is that (except for Fig0 3) wires having the same label are understood to be connected, whether they occur in the same diagram (as the tijs in Fig0 7) or in different diagrams (as the tivs in Figso 1, 4, 5, and 7) Ao STORAGEo 4olo Information o At any one time a single wire can carry one bit of information, 0 in its off state, 1 in its on stateo The two digits 0 and 1 suffice for the expression of all real numbers in binary notation, and the term "bits" is a contraction of "binary digito" The machineos vocabulary consists of words, each of which is a sequence of sixteen bitso4 At any moment exactly one word will be on the trunk line, each of whose sixteen components ti (i = 0,9 1 2, oooy 15) carries one of the word's sixteen bitso (Whenever we use

10 the variable i as subscript of a letter which labels a wire, it ranges over 0, l, 2, ooo, 15 unless otherwise stipulatedo) In the machine each word is an ordered set of wire states, and every word is expressed by a number in binary notationO These words can be used to express either numbers or instructionso Their use to express numbers will be explained in Section 5; in the present section we exa plain their use to express instructionso A typical instruction, such as ADD X (4 of Fig. 2), is expressed by an instruction word whose first four digits d d d d constitute its operand and whose rightmost twelve digits constitute its address (X x4X5 0 Xls5) which specifies the location of the storage bin containing the number to be operated ono (In the case of instructions 1, 2, 3, 8, and 9, the address part is unused0) _o20 Cells and Storae Bins. A cell, which is a circuit capable of receiving and storing one bit of information, is easily constructed out of the elements described in Section 3o To see how the cell at the top of Fig0 4 stores information, we first observe that _ (Rt Rbon)o Now consider what occurs at any time'T when all of the control wires are in state 00 If n(rT) - 1, its signal will pass through the conjunction element below i up to make hn(T) - i, whence n(-+ l) 1,

ll o and if all control wires remain inactive, then bn(h-r+ l) 1 will entail (fTr 1) - 1 also, whence bn(r+ 2) lo On the other hands if 0(,T) = O no signal will reach hn and n (T) O, whence bn(7 l) O, and, if all control wires remain inactive, then bn(T4 1) will entail hn( T4l) 0 also, whence bn(F — 2) 00 Thus, if no control wires are activated during the interval in question, whatever state a cell possesses at time r-T will continue to be possessed by it at times'T7 —- n for n 19, 2, 3,9 0oo Note that each symbol b i of Figo 4 has a three=fold significance it labels the output wire of the delay element to its left, it is a function symbol bn(r) as explained at the beginning of Section 3, and it also labels the cell within which it appearso This three-fold significance attaches to the labels of all cells within the machine 4 Il and /~i in Fig0 6, in Figo 7, and c'~i in Figo 8o Sixteen such cells are combined as in Fig0o 4 to make one storage bin, which can receive and store a word, one bit in each cello The parallel storage consists of 4,096 such bins bo b1 b4095 connected in parallel as indicated in Fig, 50 When the machine is idle all components of the trunk are in state 0, and all cells of the bin can be cleared to state 0 manually by activating the key at the upper left corner of Fig0 4o That keyes activation at such a time T

120 prevents any signal that may be at bni(q) from reaching hs whence hi(T) = 0 and b(T7i- 1) 0 regardless of the value of bn()o Having thus cleared all cells to 0, a 1 may be inserted in any cell by activating the key at that cellos right. For if all control wires are in state 0 and the key at the left is not activated, then activating the right-hand key at time "T will cause a signal to pass through the conjunction element below hi up to make hn('r) - i whence tn('rt 1) 1, and the cell will continue to store the 1 until caused to change by the activation of the left-hand key or of some control wire. Thus the keys can be used to load each cell with its initial bit of information, and the lights provide a crude way of getting information out of the bin, since each one is visibly on or off according as its cell contains a 1 or a 00 We assume that the keys are inactive in the following discussi on0 Three control wires lead to each bin, a distinct set to every bino Figo 4 shows the nth bin and its control wires Rn9 Rs and Tno Its ith cell bn is connected to the ith component ti of the trunko The control wire Tn is the transmit wire for bin no When it is activated, the bit in each cell enters the appropriate component of the trunk, passing from b_ through

130 the lower conjunction element onto ti, whence ti - Tnb It is convenient to be able to alter an instruction by changing its address without modifying the operand, Hence the wiring of the first four cells of each bin is different from that of the last twelve cells, as shown in Figo 4o The control wire Rn is the partial reception control for bin no It connects, by way of the disjunction element, to the last twelve cells bn bs ooo, bn50 If it is activated at time -" (by instruction 11 of Figo 2), and Rn is not acti-t vated, then whatever bit is on trunk component ti (i 4.9 5, oo09 15) at time'T will flow through the upper left conjunction element of cell bn onto hij from which it will emerge at 1T+-l to occupy b, in which case bn(T -l) for I 4, 59., 15, and bQ(4l) b ) for i 50, 1 and bn( 2, 3 The control wire R is the total reception control for bin no It connects directly to the first four cells and by way of the disjunction element to the last twelve cells alsoo If it is activated at time rF (by instruction 10)., then whatever bit is on trunk component ti at time'T will occupy cell bn at time rT- 1; in this case bn(T 1) - ti(-T)o The storage binsvs behavior is described more coma pendiously by the equations b(T+l) () i ( for i 0 O ~ 3, and k(T)A v o(T) t(T)T o for 1 4 0009 15o

140 4o30 Address Decodero For the computer to use the information in its parallel storage, it must have some method of switching to or selecting a specified location there0 Twelve binary digits suffice to specify any storage bin uniquely, The Address Decoder is a switching mechanism which activates the proper storage bin when it receives the twelve digit number which is the address of that bino The Address Decoder has 4,096 distinct output wires RO', 1, r~e, a4A095, each connected to a distinct storage bin of the parallel storage0 Each distinct Pi is activated by a different set of twelve digits which may be carried by the Address Decoder's twelve input wires S,4 s5, 0oo9 ISD The functional connection is accomplished through the use of 4,096 threshold-12 elements, as shown in Fig0 5o5 The same twelve input wires are connected to each of the 49096 threshold-12 elements, those connections being described by the equations: O (54 -(E4E5 -l Ds4El5) P~ ~ ~ 4094 - (- -E14 1) P4095 _ (-E4_E5 -El 5oo) General directions for the parallel storage are carried by control wires Srp, Srt, and St (Figso 1 and 5), at most one of which is in state 1 at any time0 Each of these control wires is connected to 4,096 different conjunction elements, whose other input wires are the 4,096

150 distinct v~ sO Since at most one of the control wires Srpl, Srt, St is activated at any time, and exactly one of the Address Decoder8s output wires R0, g1, ooo Po4095 is activated at any given time, there is at any given time at most one bin n for which any of the control wires R, Rt Tn is activated at that time, and, if there is such a bin n, at most one of those three control wires Rn, Rt, n is activated at that time. The equations which describe the circuits diagrammed in Figo 5 are of the forman (S p n Sn)~ r rPn) Rt (S rt n) T (St ) LP;p - p For example, in the execution of instruction 4 of Fig, 2, ADD X, the operand 0100 of that instruction causes control wire St to be stimulated and the address x4X5 00X15 enters the input wires of the Address Decoder to stimulate its output wire ix0 That stimulates TxP the output wire of a conjunction element whose two input wires are St and Px, to make the number in bin X pass onto the trunk where it is available to the ARITHMETIC UNITo Here and throughout this paper we speak as if the electrical response of a circuit were instantaneous, which is not strictly accurate0 For our remarks to be made unobjectionable we need only make the duration of the time interval we refer to as a "moment" sufficiently large to permit the signal to pass from any part of the machine to any other part during that interval0 Our "momentst need

16 0 not all be of the same duration, of course, and intervals of any different durations may lie between what we refer to as'successive momentso" It should be kept in mind that the shorter the durations of these "'moments" and the shorter the time lapses between them, the higher the speed of computation that can be achieved by the machine0 These remarks should suffice to indicate that the states 0 and 1 of our wires need not be pulses, but can alternatively be static stateso It is, of course, part of the idealized representational function of our diagrams that they permit of either interpretation0 In practice a relatively uncomplicated physical device may correspond to a very complex logical net; no one-to-one correspondence is suggested between the elements of our diagrams and the physical components of the computing machine which realizes them0 For example, our general design for the parallel storage (less the keys) can be realized physically without using separate delay lines, as by a Williamsv tube cathode ray storage device which consists of many tubes and associated circuits, The delay elements in our diagrams represent the fact that information is stored, but do not represent the specific physical devices that may be used to accomplish that storage function, Our design is intended to represent the logical role rather than the physical constitution of a computer and its parts0 Hence many

17. of the details of the circuits involved in the Williams' tube storage (pulse shaper, etc.) are not represented by our diagrams. Nor is the breakdown into parts similar, for a single tube will store bits from many bins (say, 1024 of them), with the contents of a single bin distributed over sixteen different tubes.. Serial Storage. In addition to the relatively limited parallel storage already described, our computer has a theoretically infinite serial storage,6 which supplements the parallel storage. The serial storage consists of sixteen parallel strings of cells, every cross section of which may be regarded as a storage bin. Our computer is so designed that exactly one storage bin belongs to both the parallel storage and the serial storage.7 For definiteness, we specify it to be bin 4095 of the parallel storage, which must be given somewhat more complicated cells to enable it to play its dual role. In Fig. 6, which shows only three cells of the topmost string, the middle cell diagrammed belongs to this special bin. Each string is to be thought of as extending indefinitely in both directions. It is clear from the diagram that if neither of the control wires Sb,Sf is activated, every bin of the serial storage save b4095 continues to store whatever information

18. it contains, and if R095 R4095 0, then b4095 also continues to store whatever information it contains. Now, if control wire Sb (Sf) is activated at time'T, the internal circulation or storage of information in each cell is interrupted at the threshold-3 element in each ordinary cell and at the threshold-4 element in each special cell of the shared bin, and any bit of information in each cell will pass up the wire to the right of its delay element, through the left (right) conjunction element above, and down to the input wire of the delay element of the cell to its left (right). If we assign the labels..., 2 i l, 02 to the cells of the serial storage, where 0 is _4095 the behavior of the serial storage is described by the expression Rp4095 ~R t495 n('T+l)-. b( T).n, l( b f ( i'(/T?] where n-...-2, -1, 0, 1, 2,... If a word located in an ordinary bin of the serial storage is to be used, the contents of the serial storage must be shifted backward or forward until that word occupies the special bin b4095, from which it is immediately available to the computer as described in Section 4.2. Hence the greater capacity of the serial storage is purchased, so to

19. speak, at the expense of ready availability of its contents. At this point the analogy should be noted again between our diagrammatic conventions and the process of definition. Just as a single term can be introduced as an abbreviation for a whole sequence of other terms, so some parts of our diagrams are to be understood as definitional abbreviations for other, more complicated parts. We have already pointed out that each right-hand diagram in Figs. 3b, c, d, f, and g is a definitional abbreviation of the diagram to its left. Similarly, in Fig. 5 each box bn is to be understood as a shorthand notation for the more detailed diagram of storage bin bn presented in Fig. 4. (Both, it should be noted, are connected to the same three control wires and the same sixteen components of the trunk.) And the block labeled STORAGE in Fig. 1 is a definitional abbreviation of the complete net whose parts are represented in Figs. 5 and 6, that is, of the combined and interconnected parallel and serial storages.

20. 5. ARITHMETIC UNIT. 5.1_. Machine Arithmetic. Before describing the operation of the ARITHMETIC UNIT we must discuss the arithmetic of the machine. A binary numerical expression + O.x1...Xl 5 (o0) is directl reresented in the machine by the word OX1'.xl5' and a binary number -O.x1...x15 (< O) by the word 2-.x1. x'l5 For example, +.110...0 (f- 3/4) is directly represented by 0.110...0, and -.110...0 (-3/4) by 1.010...O. Clearly any binary number x in the range -l. x ( 1 can be directly represented in the machine to within 2-15. Numbers outside this range can be indirectly represented in the machine through shifting them into the range by multiplying them by 2-n with some appropriate n. The binary point of a number is not directly represented in the machine. However, it is convenient to imagine, and sometimes to show, a binary point to the right of the leftmost bit of every machine word that directly represents a number. It will be convenient to introduce an additional convention at this time. Just as a symbol like bi may either name a wire or symbolize a function (which takes on one of the two values 0,1 at each time "r) (see Section 3), so a symbol like b may either name a sequence of sixteen

21o wires b0,.~, bl5 or symbolize a function (which takes on one of the 216 values: O0O...00, OeO.o.O1,..., lol. oolO, olo.eoll at each time T7). Our earlier use of t (Section 2) to stand for the trunk consisting of the wires ~,.00, tl5 accords with this convention. We shall introduce four operations on machine words: machine addition, machine subtraction, machine doubling, and machine halving; defining them so as to maintain a certain correspondence with the analogous operations of ordinary arithmetic. Where x and y are machine words which directly represent the numbers Co and /~, respectively, and z is the result of performing machine addition on x and _, then if O(+ / can be directly represented in the machine, it is directly represented by z, whereas if oX+4 can not be directly represented in the machine,,z directly represents a number congruent to OL + modulo 2. Similar remarks apply for the other three operations also, We will hereafter use the signs x-+ Ad -x+ys 2y, and (1/2)y to denote our four machine operationso Basically, the machine does arithmetic modulo 2 with a precision of one part in 2150 For example, O,110.o04-O.11O.*.O - 1.100O...O i.e,e 3/4+-3/4 = -(1/2), since 3/4+3/4 -(1/2) modulo 2; and halving 0. o...O1.(2-15):igivesQ O, tile halving lol...ll (-2-15) gives -2 }

22. The machine operations of addition, subtraction, doubling, and halving are the only machine arithmetic operations for which there are instructions in Fig. 2. However, other machine operations (e.g., multiplication, division), as well as machine operations on numbers which cannot be directly represented in the machine, can be programmed; that is, there exist routines (sequences of instructions of Fig. 2) for making the machine perform these additional operations. Our machine arithmetic operations are to be performed by nets constructed out of our logical elements, and these nets must all be realized by our ARITHMETIC UNIT. The machine arithmetic operations performed on sixteen digit words (x,y) must be defined in terms of logical operations performed on the several bits (xi, yi) of those words. We first define machine addition. Our task is to express (A) z = x+y as a logical relation between xi, ji, and zi. It is helpful to define the auxiliary word ~ whose i-lst bit i-1 (i > 0) is the carry digit from the addition of the three summands: xi, yi, and the carry digit i. It is clear that ~15 is 0, and that zi is 1 if and only if an odd number of the summands x~ yi, i are 1. The

23. result concerning inequivalence established in Section 3 enables us to express this rule by (A1) i - (i i i)* And since $i-1 is 1 Just in case at least two of the three summands are 1, we have the equations: (A2) Si-l - (XiziIVxi j mYi v L i) for i > 0, (A3) 15 =. Before defining machine subtraction we introduce the machine operation of complementation C, whose field consists of words. We define C(x) to be the machine representation of that number within the range -1 e x < 1 which is congruent modulo 2 to 2-x. The complementation operation is very useful because a negative number -.Xl...Xl5 is directly represented in our machine by C(O.xl...Ol5). Machine complementation is related to logical complementation (negation) in the following way. We define x =df Ao X'. - s5; and refer to x as the bitwise complement of x. Now 2 is the arithmetic sum of 1.11...ll and 2-15, and clearly x lll 1.... ll-x, whence c(X_) -= oX4 l xlS5+ o.o...01. Machine complementation is therefore performed on a number by adding 2-15 to the bitwise complement of that number. Since the arithmetic operation of subtracting O( from S is equivalent to the addition of the negative of o< to ~,

we can define machine subtraction in terms of complementation and addition. Thus, the formula for machine subtraction (S) z - -x, z becomes z - C(x)+ y = x + Zy*O.O.. 01 By using (A1) and (A2) we can translate z = -t- into logical terms; and since ~15 is one of the summands in the rightmost digital position, the addition of 2-15 can be accomplished by setting 515 equal to 1. Thus, machine subtraction of the word x from the word y can be defined in terms of the following logical relations among the bits xi' hi' i' and zi (S1) i (i $ i i) (S2) ~i- = (xizi~ — i iv iSi) for i > O, (S3) 15 1. To define machine doubling we want to express (D) z = 2y in logical terms. Since a 1 in the ith position has twice the value of a 1 in the i -lst position, doubling consists merely of shifting each digit of left onel-binary position with respect to the binary point. We express (D) in terms of the logical operations on the bits Yi by (D1) i Z i~-l for i 15, (D2.) 15 ~

25. Similarly, halving is accomplished by a right shift. We define machine halving, (H) z- (1/2) by (H1) i - Zi-1 for i> O, (H2) so Zo..2_. Operation of the CONTROL. Instructions 4, 5, 6, 7, 8, 9, 10, and 11 of Fig. 2 all involve the ARITHMETIC UNIT. Before describing how the ARITHMETIC UNIT is to function in their execution, we must explain briefly how the CONTROL affects the ARITHMETIC UNIT. Exactly how the CONTROL performs the functions we are going to describe will be explained later in Section 6. Since the instructions involving the ARITHMETIC UNIT all refer to a "number in the ARITHMETIC UNIT", it will be convenient to have a way of referring to this number. We will stipulate that it is located on the sequence of wires a. At any time /T the wire sequence' dA l2, A3 is in exactly one of sixteen distinct states. These sixteen states, together with the state of the CONTROL CLOCK, completely determine the states of the thirteen control wires labeled A, S, and C with appropriate subscripts. (When the machine is inoperative, none of the wires is stimulated.) Fig. 2 tells what control wires are activated for the various

26. states of d l, d2, d3 when the machine is operating; control wires not marked as active are stipulated to be inactive. The state 1111 can occur only by a mistake in programming; when it does occur, no control wires are activated, and it produces no effect. When one of the instructions 4, 5, 6, 7 is being executed, the CONTROL will activate St and also send the address X to S4,..., sl5, thereby causing the STORAGE to transmit the number in storage bin X to the trunk t. Hence we may assume that when these instructions are being executed the number in storage bin X is on t and therefore available to the ARITHMETIC UNIT. When instruction 10 or 11 is being executed, the CONTROL will activate Srt or Srp, respectively, and will also send the address X to s4,..., sl5, causing bin X to receive in the desired fashion any number on the trunk t. Hence we must so design the ARITHMETIC UNIT that these instructions cause the contents of a to occupy t. We may summarize the effect of the CONTROL on the ARITHMETIC UNIT as follows. When one of the instructions 4 through 11 is being executed, control wires Ar, Ah, Ac, Als, Ar, Att are in the states shown in Fig. 2; at any other time these wires are all inactive. When instruction 4, 5, 6, or 7 is being executed, the number in bin X is also on the trunk t. Finally, when instruction 10 or 11 is

27. being executed, the CONTROL causes whatever number the ARITHMETIC UNIT places on t to be properly received by the correct bin. 5.3. The Functions of the ARITHMETIC UNIT. In the previous subsection we described every possible way for information to be directed to the ARITHMETIC UNIT by the CONTROL. In this subsection we consider three general functions performed by the ARITHMETIC UNIT on the basis of this information, and explain how it performs the first two. The first function is the transmission of information. When either instruction 10 or 11 is executed, the ARITHMETIC UNIT is to transmit its contents onto the trunk t. If either of these instructions is executed (see Fig. 2) Att will be stimulated, hence we want the machine to realize the expression Att D (ai - ti)This function is accomplished by the conjunction elements to the right in Fig. 7. The ARITHMETIC UNIT is also to supply the bits 0 and a15 to the CONTROL, which is accomplished simply by running wires from these cells to the CONTROL as indicated in Fig. 7. We will simplify the discussion of the remainder of this section by ignoring the transmission function of the ARITHMETIC UNIT (and the relevant parts of Fig~ 7).

28. The second function performed by the ARITHMETIC UNIT is storage. It is clearly required that when the ARITHMETIC UNIT is not executing any of the instructions 4 through 9, it must continue to store the number a. Inspection of Fig. 2 shows that Ar is activated when and only when one of the instructions 4 through 9 is being executed. Hence when Ar(rr) = 0 we want a(-) - a(rT-tl). This storage may be accomplished by using sixteen delay elements, with input wires 0,..., rl5 and output wires aO,''' a l 5' as in Fig. 7, so connected that A (ri = ) Since ai(rt1Rl) = i(T-), the ARITHMETIC UNIT does perform the desired storage function. The third function performed by the ARITHMETIC UNIT is the modification of its contents from a('T) to a(T+l) in accordance with instruction 4, 5, 6, 7, 8, or 9, which we shall refer to as arithmetic instructions. The design of a net which will realize the arithmetic instructions is the most complicated and difficult part of the task of designing the machine. To it we devote both the following subsection and Appendix E.

29. 504. Execution of the Arithmetic Instructions. In this subsection we shall derive a set of formulas which the ARITHMETIC UNIT must realize for the arithmetic instructions to be executed. We derive them by combining the various arithmetic instructions with the equations (A), (S), (D), and (H) of Section 5.1, which define the various machine arithmetic operations. We note that the result of an operation performed at time Pr is to appear at r at time T and at a at time TrFl. Instruction 4 demands that r contain the result of performing the machine addition of the number at t to the number at a. For the ARITHMETIC UNIT to fulfill its intended function, it must realize the conditional (Am) If ADD X is enjoined, then r = t-fa. Now by Fig. 2, ADD X is the only instruction which involves the stimulation of Ar and Ah but not Ac. Hence the antecedent of (Am) may be replaced by ArAhA c And a translation of the consequent of (Am) into a logical formula concerning the states of individual wires may be made by using (AL), (A2), and (A3), substituting ri for zi, t for xi, and ai for yi. In the ARITHMETIC UNIT we are constructing, the auxiliary word 5 will be realized by the set of wires 0o, Cl,.', Cl5; hence we also substitute ci for Xi in the (A) equations. We thus obtain the following formulas for the ARITHMETIC UNIT to realize:

30. (A1) ArihAc r (i *( i a, ci)-, (Al) ArAhAc ci-1 (tiai V tiCiv aii)} for i ~ 0, (AM) Mhc 3 C = o A set of formulas for the ARITHMETIC UNIT to realize to execute instruction 5 may be derived from the (S) equations in a parallel way. We thus obtain (Sm) If SUBTRACT X is enjoined, then r -t+ a, (SM) ArAhAc D ri (i a* i) (S2) ArAhAc ci ( i vticiaici) for i > OC (Sm) Arhc 3 {-1l5 } Instruction 6 demands the replacement of r by t. For it to be executed, the ARITHMETIC UNIT must realize the conditional (Tm) If TRANSFER X is enjoined, then r = t. Consulting Fig. 2, we find that this can be represented as (T.) ArAhAc (ri i) Instruction 7 demands that r be replaced by -t; for it to be executed the ARITHMETIC UNIT must realize the conditional (TCm) If TRANSFER COMPLEMENT X is enjoined, then r- C(t). Since -t = -t +0, the formulas required here can be regarded as special cases of the (S) formulas, with 0 substituted for y. After that substitution has been made,

31. the resulting formulas easily simplify to (TCM) 1(TC) ArAhAc {ri ( i t Ci) (TCm) Ar-hAc Ci-l (tici)} for i > 0, (TC3) ArAhAc - C 5 =i, which the ARITHMETIC UNIT must realize to execute instruction 7. Instruction 8 demands that r be replaced by 2a; for it to be executed the ARITHMETIC UNIT must realize the conditional (Dm) If DOUBLE is enjoined, then r = 2a. Again substituting r for z and a for y, this time in the (D) formulas, and consulting Fig. 2, we obtain (Dm) A A a for i ~ 0. (D2) ArAls i {l5 = j These formulas must be realized by the ARITHMETIC UNIT for it to execute instruction 8. Instruction 9 demands that r be replaced by (1/2)a; for it to be executed the ARITHMETIC UNIT must realize the conditional (Hm) If HALVE is enjoined, then r - (1/2)a. Again we substitute r for z and a for y, this time in the (H) formulas, and consult Fig. 2, to obtain (H) A~rAArs D (ri - ail for i > 0, (HmA) ArArs D O a

32. These must be realized by the ARITHMETIC UNIT if it is to execute instruction 9. We have now completed the task of deriving a set of formulas which the ARITHMETIC UNIT must realize if it is to do its part in executing the arithmetic instructions. These are the fourteen formulas whose labels have superscript m and subscripts 1, 2, t*3. These fourteen formulas, together with the storage formulas (see Section 5.3) r i i and (Kt) ai(Tr ) - provide a complete specification of the ARITHMETIC UNIT (since we have agreed to neglect its transmission function). Any logical net which realizes these sixteen defining formulas will be a satisfactory ARITHMETIC UNIT. It is readily verified that Fig. 7 is such a net, by observing that the last formula above is satisfied by the delay elements, and then taking each of the remaining formulas in turn and determining that under the conditions stated each ri has the proper relations to ai and ti. Performing this verification will facilitate understanding how the ARITHMETIC UNIT works.

33. 6. CONTROL. 6.1. ADDRESS COUNTER. Apart from "jump" instructions (12, 13, 14 of Fig. 2) the computer executes in order the instructions stored in a sequence of bins of the parallel storage. To do so it must count off those instructions as they are executed, and this function is performed by the ADDRESS COUNTER diagrammed in Fig. 8. Each of its twelve cells at a,, a5 can receive and store one bit of information, so the ADDRESS COUNTER as a whole can receive and store a twelve digit number xx5...x15. If all control wires are in state 0 and no keys are activated, each cell at continues to store whatever information it contains. Any number in the ADDRESS COUNTER is the address of some bin of the parallel storage. To load the ADDRESS COUNTER with the address of the bin containing the first instruction we want the machine to execute, we must be able to change the contents of the ADDRESS COUNTER. The keys shown in Fig. 8 enable us to make any desired change. Activating the key at the lower left (when the machine is idle) clears all of its cells to 0, and activating the key of cell. a at time7- makes af(~-1) = 1; thus we can load the ADDRESS COUNTER with any number we please.

34. As remarked at the bottom of the TABLE OF INSTRUCTIONS on Fig. 2, at every even numbered time /r = 2k when the machine is operating, control wires St and Ct are activated. At any such time, then, Ct -1 permits the bit stored in cell at to pass through the rightmost conJunction element onto si (i 4, 5,..., 15). Since S4, S5,..., Sl5 are input wires to the Address Decoder (see Fig. 5), and since St is also activated then, that storage bin whose address is contained in the ADDRESS COUNTER at any even numbered time T = 2k will transmit its contents onto the trunk at that time. Hence when the computer begins to solve a problem the first instruction it executes is the one stored in that bin whose address is stored in the ADDRESS COUNTER, usually bin O. To keep track, whenever the ADDRESS COUNTER sends an instruction from the nth bin onto the trunk it must count, that is, add a 1 to the number it contains at that time. (Any twelve digit number xx... contained in the ADDRESS COUNTER is the address of some bin of the parallel storage, and can also constitute the address part of an instruction word, as in 2do Whenever we consider the numerical aspect of a word we must keep in mind the discussion of range presented in Section 5, and the convention that a binary point is imagined to follow

35. the leftmost bit of every number word. This convention should apply to instruction words too, for it is often convenient to perform arithmetic operations on instruction words, as will be illustrated in Appendix D. From this point of view the 4096 addresses of the 4096 bins of the parallel storage are 0.000000000000000, 0.000000000000001,..., 0.000111111111111, and the number in the ADDRESS COUNTER is 0.0_00 -.5.. xl5 or (x4x5 *xl15)2-15 Consequently the address of the next bin after that one is (x45...xl )215-2l15. It will, however, be convenient to continue to speak in this connection of the number in the ADDRESS COUNTER as x4x5...x15, and of its successor as that number +- 1.) Let us suppose that the number in the ADDRESS COUNTER at time'r is x x 5...x5, and to it we wish to add 1, which is Y4Z5''Y15 where X15 = 1 and Y4== 5' - 14. - 0. The sum z4z5...z1 5 of these two numbers is recursively defined (see Section 5) by the equations: Zi - (xi t zi f i) and ~i-1- (xli~ Xi.v iv i i) where 15 = Since 015 and Y15- 1, by the first defining equation we have 15 - x15, and by the second defining equation we have S14 - x15. Now for every i < 15, Yi - O, whence x i- Xii, and also i (xi f i). These formulas

36~ must be realized by the ADDRESS COUNTER if it is to perform its counting function correctly. For the formulas developed in the preceding paragraph to be realized by a circuit, that circuit must contain wires corresponding to x4, X5, o, xl to f4, 5,'.. 14' and toz z4, z, ooo, Zl5, and these wires must be so connected that their behavior is described by those formulaso If net wires a&, c, and rt correspond to xi. i' i -i i c-i, and zi, respectively, those wires must realize the equations ri (a t C?) and cil =.ai for i 4 15, r- a5 and ct = at 1-4 -15 The diagram in Fig0 8 satisfies the preceding equations when C O and Ct - lo By assumption, a x, and since Cr = 0 and Ct - 1 at every even numbered moment r = 2k, at every such moment rt will contain the immediate successor of the number in a, and that successor will occupy a at the following moment T- = 2k +Lo If at an odd numbered moment T = 2ktl a "Jump" is to be made in executing instruction 12, 13, or 14 of Figo 2, control wire C r 1 and C t 0, and the address X of bin X referred to in the "Jump" instruction OBEY X (or OBEY X IF MINUS or OBEY X IF al5 IS 1) occupies wires s4, S5, o.o, sl5 (as will be explained in the following section)~ Since C O, no signal can pass from a onto

37. Si through the cell's rightmost conjunction element; and since C 1, no signal can pass from at to ri T-r -i through the conjunction element to the left of at But the lower left-hand conjunction element permits any bit of information on si to pass onto r' at time r= 2k-+l and to occupy at at time 1-r =2k*2. Hence the address X of bin X referred to in the "jump" instruction OBEY X will be contained in the ADDRESS COUNTER at time'l- 2k-e-2. At that even numbered moment both St and Ct are automatically activated, which makes bin X of the parallel storage transmit its contents onto the trunk at time'T= 2k+ 2, and causes the ADDRESS DECODER to contain, at the following.oment T = 2k+3, the address of bin X+ 1. 6.2. CONTROL CLOCK. We wish to be able to start the machine at any time, and we want control wires St and Ct to be automatically activated at every even numbered moment while the machine is solving a problem. Our device for accomplishing this function is the CONTROL CLOCK, which occupies the lower right-hand part of Fig. 9. The behavior of the right-hand delay circuit, which may be described as a "blocking oscillator circuit", is described by the equation A(T) = ( 5 O mod 2). Thus g is activated at r'T= 0, 2, 4,..., 2k,... independently of anything that may happen elsewhere in the machine.

38. The left-hand delay circuit operates somewhat differently. If the wire f is inactive, then activating the START KEY at time f will activate h. At time'T+-1 the signal will emerge from the delay element above, and if f is still inactive, the signal will pass onto h again and up again to the delay element. Thus, so long as f = 0, activating the START KEY at time'A will activate h at times'T, r-tl, T4-+2,... The two delay circuits work together to produce the following result. So long as f = 0, if the START KEY is activated at either time'T 2k-1 or 2k, h will be activated at times 2k, 2k+l, 2k+-2,.... The other input wire g is activated by the right-hand delay circuit at times 2k, 2k+-2, 2k+4,... Hence the output wire controlling Ct and St is activated at times 2k, 2k+2, 2k +4, and so on. Once started, the computer's activity is cyclic, with control wires St and Ct activated at every even part of the cycle, starting at the moment the START KEY is activated if that is done at an even numbered moment, or at the following moment if the START KEY was activated at an odd numbered moment. We wish also to be able to stop the machine, both manually and by instruction 1 of Fig. 2. To stop the machine we must activate f, which will prevent any signal from the upper delay element passing onto h, thus

39. clearing the left-hand delay circuit. As Fig. 9 shows, f can be activated either by activating the STOP KEY or by activating d3 but not d, dl, or d2. Hence the operand 0001 signals the machine to stop. This circuit is part of the OPERAND DECODER, which is discussed in the following subsection. 6.3. OPERAND DECODER. We have shown in Sections 4 and 5 how the STORAGE and the ARITHMETIC UNIT function when their various control wires are activated, and we have listed in Fig. 2 the various different instruction words that activate different sets of control wires. It is the operand or first four binary digits of an instruction word which specifies which control wires are to be activated for the instruction to be executed. The OPERAND DECODER which occupies the left-hand part of Fig. 9 is a switching mech-. anism which activates the proper set of control wires when it receives the four digits of an operand. The four wires,, d d d d3 are connected to various threshold elements in the way indicated. That the desired functional connections are realized by the OPERAND DECODER is easily verified. For example, the control wire Ar, which must be activated for the execution of instruction 4, 5, 6, 7, 8, or 9 of Fig. 2, is

40. activated by any of their operands, as described by the following equation: Ar ( %dd2d3 3V % d vdd2dV d122d3v jdd3 v kdldA12 d )* That equation can be simplified to Ar -_ (dodl vdold2), which is obviously realized by the address decoder as diagrammed in Fig. 9. The functional connections between operands and various sets of control wires could be specified in many different ways: the present arrangement was selected to permit simplifications of the kind indicated. 6.A. Operation of the CONTROL. Four parts of our computer are represented by blocks in Fig. 1, and each has been explained in detail. We have now to explain the rest of the CONTROL, which consists of sixteen conjunction elements and sixteen delay elements, together with the wires connecting them to the other parts of the computer. Each component t of the trunk is connected to an input wire of one of these conjunction elements, whose other input wire is connected to control wire Ct. The output wires t_" of those conjunction elements lead to separate delay elements, whose output wires lead to d d, d, and s s,,

41. The functioning of these parts can best be explained by showing how they operate when the machine is executing an instruction under the direction of the CONTROL. When the machine is engaged in solving a problem, at any even numbered moment T-= 2k control wires St and Ct are automatically activated, making the ADDRESS COUNTER send the address of some storage bin down wires s4, s5,..., Sl5 to the STORAGE. The STORAGE is thereby caused to transmit the instruction word from that bin onto the trunk. The sixteen digits of that instruction word pass through the sixteen conjunction elements above (since Ct(2k) - 1) to occupy the sequence of wires t'". At the following moment T= 2k-il (an odd cycle) the sixteen bits of the instruction word emerge from the sixteen delay elements. The first four bits (its operand) pass along do dl, d2, d3 to the OPERAND DECODER, and the last twelve bits (its address) pass along 4, s *,..., 15 either up to the ADDRESS COUNTER, if its operand causes the OPERAND DECODER to activate control wire Cr, or down to the STORAGE if its operand causes the OPERAND DECODER to stimulate either control wire St, Srt' or Srp Thus we see that at every even cycle the computer brings a new instruction word from STORAGE onto its trunk, and at each following odd cycle the computer executes the instruction enjoined by that instruction word. We will

42. now illustrate this process. Consider the actual sequence of occurrences when the computer begins a routine whose first two instructions TRANSFER 101 and OBEY 6 IF al5 IS 1 are in bins 0 and 1, respectively.8 Now if the ADDRESS COUNTER contains all zeros, and we activate the START KEY at either time =- 2k-1 or - 2k, the machine will begin its run at 7 = 2k, when S C = 1, and the ADDRESS COUNTER trans-t -t mits OO...00, the address of bin O, along wires s4, S5,..., S-l5 to the STORAGE. Bin 0 transmits its contents OllO0000000llOO101 onto the trunk, up through the conjunction elements onto ti. Then at r = 2k-i1 those bits emerge from the delay elements, the operand 0110 going along do, d2, d d to cause the OPERAND DECODER to activate control wires S and Ar. At the same time the address 000001100101 goes down $s4), s,..., 5 to the STORAGE, which transmits the number x from bin 101 onto the trunk, and then into the cells of the ARITHMETIC UNIT, since Ar is activated. At T= 2k* 2 we have St = Ct - again, and the ADDRESS COUNTER transmits 00...01, the address of bin 1, along s4', s5,.., s15 to the STORAGE, which transmits its contents 1110000000000110 onto the trunk, up through the conjunction elements onto tn. Then at'- 2k+ 3 those bits emerge from the delay elements,

439 1110 along O, d1, d2, d3 to the OPERAND DECODER, and 0...OllO onto s4,,..., S15. Now what control wires the OPERAND DECODER activates will depend upon the present contents of the ARITHMETIC UNIT, which contains the number oxl...Xll5 If the rightmost digit Xl5 of that number is, al15 - 1, and control wire Cr is stimulated by the OPERAND DECODER. In this case the address 00...0110 now occupying wires s4, s5,..., Sl5 enters the ADDRESS COUNTER, which at the following time T-= 2k -4 will transmit it down to the STORAGE to cause the instruction word in bin 6 to pass onto the trunk. But if the rightmost digit x15 is 0, a15 = 0, and the OPERAND DECODER activates no control wires. In this case the address in the ADDRESS COUNTER remains OO...010, and at the following time'7 2kt-4 it is transmitted down to the STORAGE to cause the instruction word in bin 2 to pass onto the trunk.

44. Footnotes 1. The writing of this paper was done under the sponsorship of the Burroughs Corporation, Research Center, Paoli, Pennsylvania. The logical design and analysis is primarily the work of the first author (A.W.B.) and the exposition is largely the work of the second author (I.M.C.). Thanks are due to Dr. R. L. Cartwright for helpful criticisms and suggestions. 2. Some logical nets involving several primitive elements may be physically realized by devices no more complicated than those required for the physical realization of a single primitive element. For example, an electronic circuit using a single multigrid tube can realize a conjunction element. 3. The threshold elements here defined are different from those discussed in either [5] or [6. 4. Forty bits is a word length more typical of actual computers. 5. The complexity of the Address Decoder could be reduced by using a less straightforward design, as explained in 6. An actually infinite serial storage is not a net in the sense of [21. But the serial storage is so connected to the machine that the whole net has the property

45. that at any arbitrary time only a finite number of its wires have changed from their initial states. Hence at no time is the net presumed to contain an infinite amount of information, and it can therefore be regarded as a finite but indefinitely expansible net. 7. The serial storage may be realized by a magnetic tape (or set of tapes) with sixteen parallel channels of information. Here a single cell corresponds to a region of the tape which is or is not magnetized, and the operation of shifting the contents of the bins forward or backward is realized by moving the tape mechanically. On this interpretation the serial storage represents a relatively rapid way in which information can pass between the computing machine and its operator. 8. See Appendix C for a complete routine of which this is a segment.

46. Bibliography [1] Burks, Arthur W., Herman H. Goldstine, and John von Neumann, Preliminary Discussion of the Logical Design of an Electronic Computing Instrument, Part I, Vol. I, The Institute for Advanced Study, 1946. 2 Burks, Arthur W., and Jesse B. Wright, "Theory of Logical Nets," Proceedings of the I.R.E., Vol. 41, 1953, pp. 1357-1365. [31 Burks, Arthur W., Robert McNaughton, Carl H. Pollmar, Don W. Warren, and Jesse B. Wright, Complete Decoding Nets: General Theory and Minimality, ERI Report 1828-1-T (Burroughs Corporation Research Center, Paoli, Pennsylvania), Ann Arbor, 15 July 1954. To be published in the journal of the Society for Industrial and Applied Math. [4] Copi, Irving M., Symbolic Logic, New York, 1954. [5] Kleene, S. C., "Representation of events in nerve nets and finite automata," RM-704, RAND Corporation, 1951. L[6 McCulloch, Warren L., and Walter Pitts, "A logical calculus of the ideas immanent in neuron activity," Bull. of Math. Biophysics, Vol. 5, 1943, pp. 115-133. L7] Patterson, George W., "Logical Syntax and Transformation Rules,"t Proceedings of a Second Symp Oslumon LargeScale Calculating Machinery (Cambridge, Mass., September 13-16, 1949), Cambridge, 1951, pp. 125-133.

Srp Srt St OPERAND Sf DECODER AND Sb CONTROL CLOCK Cr ADDRESS r8 Ct~~~~~~~~~~~O. COUNTER 0 7~~~~~~~~~~~~~~~~~~~~ do dl,, d3 Ar Ah Ac Als A Att t2 3,....;,4 ts4 s5....,s14 s15 Po~~~~~~~~~~~~-t ARITHMETIC STORAGE UNIT 14' Sr' tl5 t 15 BLOCK DIAGRAM OF COMPUTER Fig. 1

48. OPERAND DECODER OUTPUT WIRES INSTRUCTION OPERAND ACTIVATED AT dodd2d3 X = 2k + 1 1. STOP 0001 2. SERIAL FORWARD (Move contents of serial storage one bin forward) 0010 Sf 3. SERIAL BACKWARD (Move contents of serial storage one bin backward) 001l Sb 4. ADD X (Add the number in storage bin X to the number in the arithmetic unit) 0100 StArAh 5. SUBTRACT X (Subtract the number in storage bin X from the number in the arithmetic unit) 0101 StArAhAc 6. TRANSFER X (Transfer the number in storage bin X to the arithmetic unit) 0110 StAr 7. TRANSFER COMPLEMENT X (Transfer the negative of the number in storage bin X to the arithmetic unit) 0111 StAr Ac 8. DOUBLE (Double the number in the arithmetic unit) 1000 Ar Als 9. HALVE (Halve the number in the arithmetic unit) 1001 Ar Ars 10. STORE IN X (Replace the number in storage bin X by the number in the arithmetic unit) 1010 SrtAtt 11. SUBSTITUTE IN X (Replace the rightmost 12 digits of the number in storage bin X by the corresponding digits Of' the number in'- the arithmetic unit) 1011 Sr Att 2. OBEY X (Execute next the instruction in storage bin X) 1100 Cr 13. OBEY X IF MINUS (If ao = 1, then execute next the instruction in storage bin X) 1101 aocOCr 14. OBEY X IF al5 IS 1 (If al5 = I, then execute next the instruction in storage bin X) 1110 al5 D Cr (At every even cycle X = 2k when the machine is operating, do = dl = d2 = d3 = O, and wires St and Ct are activated. ) TABLE OF INSTRUCTIONS Fig. 2

f fg a. STROKE ELEMENT: fig b. NEGATION ELEMENT: TFdf(flf) fjfj]- offvg) f fv c. DISJUNCTION ELEMENT: (fvg) df(flg) - (f g) d. CONJUNCTION ELEMENT: (f g) df (? T) e. MATERIAL IMPLICATION ELEMENT:(fmg) df(f vg) (frog) f mg) f. EOUIVALENCE ELEMENT:(f-g) =df [(fg)v(f)] f f f=g) f(f kg) g. INEQUIVALENCE ELEMENT: (f*g)=df [(fo)v(fg)] h h. GENERALIZED THRESHOLD ELEMENT i. DELAY ELEMENT: g(O) =, g r+1)-ffr) FOR r, 0,1,2,.... f h f h k j. MULTIPLE JUNCTION ABBREVIATING A MULTIPLE INPUT DISJUNCTION ELEMENT: (fvgvh)il.J, k. ELEMENTS Fig. 3 49.

Rt Tn hn bn 2 L 1 1 n,t3 2 b L 1b 12 2 L 2 K BIN OF PARALLEL STORAGE Fig. 4

S4 so S S 6*b,.., 13 po PI,...p4094 P4095 Srp Srt. -----— H, — t, Rf Rt R~c R9t T bo I 0 b6b 494 b40X PARALLEL STORAGE Fig. 5 51.

Sb Sf Sb Sf %. ~ Sb 4095 b \"~ P~3 2 bL'p0 S R~5 4Sf s 41 sf4 4095 Sb Sf T up to SERIAL STORAGE Fig. 6

(TO CONTROL) AcC c r wA C0 W0 Ah,, AI-, (y-hi - - WI Cl5t lA ARITHMETIC UNAtt h Ars) —-- Aim Fig. 7 15C15 Ac [ w15All $~ ~ ~~RIHEI 2 ~. Fig.~~~~ A r

83lNnoo SS3dGGICV Jo }D 103 L ( ~ - 3 (i i I I I

Cr -. Ars --- _ " — h h ( J! J' "~ Att d, d d_ d3 STOP START KEY KEY OPERAND DECODER CONTROL CLOCK OPERAND DECODER AND CONTROL CLOCK Fig. 9 55.

56. Appendix A. Some Operations of the ARITHMETIC UNIT In this appendix we shall illustrate the actual machine procedure in executing arithmetic instructions. 1. Subtraction. If the instruction SUBTRACT X is executed, t Ar - Ah = A= 1 and all other control wires are in state 0O. Let us suppose that the number X1o...Xl5 is in storage bin X and the number yOyl... 15 is in the cells of the ARITHMETIC UNIT. Since St = 1, the number in bin X will pass onto the trunk, whence ti E xi. Each trunk component ti is an input wire to an inequivalence element (at the left of Fig. 7) whose other input wire is Ac, and whose output wire is ti, whence ti (ti Now Ac, so ti - ti or t! _ Xi By assumption, ai - Yi, and since Ah = 1, each bit Yi passes through the lower left-hand conjunction element of its cell onto wire wi, whence wi = yi. We now observe that It, wi, and ci are the three input wires of an inequivalence element whose output wire is Ui, whence ui (t! wi Ci) or ui -(i ) We also observe that where i 0, t1, wi, and ci are the three input wires of a threshold-2 element whose output wire

57. is cil, whence (twiv t!CiWiCi) or C. i-ii whence C -i —i i V. -1i)i -i-i (xiy-iv x iciv ici), for i> O. Now c15 A and Ac = 1, whence Cl5 =, and with this condition added, the two preceding equations for u and ci conform to the general recursive definition of subtraction, whence the number whose bits occupy wires ui, say ozl...Z15, is congruent modulo 2 to the difference Yt...X15 — XOXl..-X15 Since Ar-r 1, the bit occupying ai cannot pass through the conjunction 2 element below ri, but the bit (zi) occupying wire u. can pass through the conjunction element to the left of ri and thus pass onto ri. Hence, if SUBTRACT X is executed at time'T, a number congruent modulo 2 to the result of subtracting the number in bin X from the number in the ARITHMETIC UNIT will occupy wires ri at time'T and will occupy the cells ai at time l+ 1. 2. Doubling. A number in binary notation is doubled by moving its binary point one position to the right, which amounts to shifting each of its digits one position to the left. If the instruction DOUBLE is executed, Ar = Als - 1 and all other control wires are 0. Suppose the number yO.Yl...Z1 5 occupies the cells ai of the ARITHMETIC UNIT. Since St = Att O, every component of the trunk _ti = 0; and since Ac = O, each t = 0 because it is the

58. output wire of an inequivalence element whose input wires are equivalent (both O). Since A O-, Cl5 O0, and every Ci = O, since each ci for i L 15 is the output wire of a three-input threshold-2 element3 two of whose inputs are 0. Since Ah (and A O, which is relevant in cell aR) no signal from ai can pass through the lower lefthand conjunction element onto wire wi. Instead Wl5 = O and each wire wi for i < 15 is occupied by the bit Yif 1 from ai l, which can pass up to wi through the conjunction element whose input wires are ai4l1 and Als, since Als = 1. Now each ui contains the same bit as w., for ui is the output wire of an inequivalence element whose three input wires are tt, ci, and wi, the first two of which are in state O. Since Ar = 1, ri j ui, whence the number occupying wires ri is }-Z2-*-Yl150- Hence if DOUBLE is executed at time T, a number congruent modulo 2 to twice the number in the ARITHMETIC UNIT will occupy wires ri at time'T and will occupy the cells ai at time T4-1l.

59. Appendix B. Machine Solution of a Simple Problem. To program the computer for evaluation of the polynomial 2x*-y-z for a particular set of values of its variables, say 1/4, 3/8, and 5/16, we proceed as follows. First, we store the indicated values of x, A, and z in bins 11, 12, and 13. Then we decide that a straightforward way for the machine to solve the problem is to have it transfer x to the ARITHMETIC UNIT, double it, add to that result the number y, and then subtract from that result the number z. At that time the desired solution will be in the ARITHMETIC UNIT. Standard procedure is to have the machine store its answer in a bin of the parallel storage before it stops; we select bin 14 for this purpose. Now the routine is inserted into the computer: the first instruction word in bin 0, the second in bin 1, and so on. The routine for this problem is written below, on the left informally, on the right coded for insertion into the machine. bin 0: TRANSFER 11 0110000000001011 bin 1: DOUBLE 1000000000000000 bin 2: ADD 12 0100000000001100 bin 3: SUBTRACT 13 0101000000001101 bin 4: STORE IN 14 lOlOOOOo000000000lllO bin 5: STOP 000100000000l000

60. bin 11: x 0010000000000000 bin 12: y 0011000000000000 bin 13: z 0010100000000000 bin 14: (to contain solution: 0100100000000000) Having completed preparing the machine by clearing its ADDRESS COUNTER to 00...0, we activate the START KEY at time 7' = 2k-1 or'7 2k, and the computation begins at time' = 2k. At'r 2k the ADDRESS COUNTER transmits its contents along S4- s5, s,.., 5 to the STORAGE, which sends the instruction word from bin 0 onto the trunk and up through the sixteen conjunction elements to t". At T- = 2k +l the instruction word initially in bin 0 emerges from the delay elements above t"', its operand 0110 going via d,'0', d3 to the OPERAND DECODER, and its address O...01011 going via 9s, 5,..., l5 to the STORAGE. These cause bin 11 to transmit its contents 0010...0 onto the trunk and cause the ARITHMETIC UNIT to receive that number from the trunk into its cells ai. At 7' 7 2kt 2 the ADDRESS COUNTER transmits its contents (now O...O1) along 4s,'55, *.., 15 to the STORAGE1 which sends the instruction word from bin 1 onto the trunk and up through the conjunction elements to t". At every even cycle a new instruction word goes through the trunk up to the delay elements, and at the following odd cycle that instruction is executed. Finally, at T = 2k+ll the machine stops.

61. The machine's activity, during this run can be shown in tabular form. All storage bins retain their initial contents throughout the run except bin 14 which receives the solution at time' T 2kt- 9. Significant changes occur in the ADDRESS COUNTER, in the ARITHMETIC UNIT, and in wire sets t"'; dO..., d3; and s s,... l5 These are all shown in the following table. Address Arithmetic TimeT Counter t_, t.... t..*.td I,5 Unit _..........'-15.......' 2k 0 01100... 01011 0000 0..00000 0 2k +1 1 00000...00000 0110 0...01011 x 2k-t2 1 10000...00000 0000 0...00001 x 2k +-3 2 00000... 00000 1000 0...00000 2x 2k +4 2 01000... 01100 0000 0..,00010 2x 2k +5 3 00000...00000 0100 0...01100 2x# y 2k +6 3 01010...01101 0000 0...00011 2x+ y 2k +7 4 00000...00000 0101 0...01101 2x+ y-z 2k +8 4 10100...01110 0000 0...00100 2x+ t-z 2k +9 5 00000...00000 1010 0...01110 2x + y-z 2k+10 5 00010... 00000 0000 0...00101 2x+ y-z 2k+11 6 00000...00000 0001 0..00000 2x+ -z

62. Appendix C. Multiplication. To program the computer for multiplication we make use of all of the "Jump" instructions listed in Fig. 2. For simplicity let us suppose that the two numbers to be multiplied are positive and have been scaled into the range of the machine, so O -' x < 1 and 0 - J 1. Since x is O, it is obvious that -0 x 152 15 +x142-14+...+ X121 and that = x 2-15+ x z2-1 +...+ xl2which is equivalent by successive partial factorings of 2-1 to M = (... (x5l-2-I+ x24 2-1... + x z) 2-1 It is conveni~et to define the product of two such numbers x and y by recursion, letting PO 0 be the 0th partial product and i (Pi Xl6- iZ)2 th partial product. The product of x and X is the 15th partial product P15. (Because of the limited number of cells in our ARITHMETIC UNIT the product x formed by the machine will be truncated after its 15th binary place, and equal to the correct product only within 2-15.) We program the multiplication of x and y by having the machine form the successive partial products P, P2,..., and stop when it has formed P4=. Given Pil we

63. form P by adding Xl6-_i to Pi-1 and halving their sum. Now X16_-i if X16_i =1, and X_16-iZ O if xl6_i O. The computer can determine whether Xl6_i is 1 or 0 by transferring x21-i to the ARITHMETIC UNIT and sensing its rightmost digit —xl6_i, which occupies cell al5. If al5 is 1, Z must be added to Pi-' and their sum halved to obtain Pi, whereas if al5 is O, Pi is obtained simply by halving Pi l To form successive partial products until P15 is obtained the machine must keep count of the number of partial products it has formed. This count is kept by placing an index i (initially O) in bin 104 and adding 1 to it* as each new partial product is fo'i d, so the index in bin 104 will be i when the machine has formed Pi. If the number 15 is subtracted from i, the result will be minus if P15 has not yet been formed (in which case we want the machine to continue the process of forming successive partial products), whereas that result will fail to be minus for the first time when P15 has been formed (in which case we want the machine to stop). Consequently, when the number i-15 has been formed in the ARITHMETIC UNIT our next instruction should be OBEY 0 IF MINUS, and the instruction after that one should be STOP. *See, however, the discussion in Section 6.1.

Our complete routine for the multiplication of two positive numbers x and y can now be set down as follows. bin 0: TRANSFER 101 bin 1: OBEY 6 IF 5 IS 1 bin 2: HALVE bin 3: STORE IN 101 bin 4: TRANSFER 103 bin 5: OBEY 10 bin 6: HALVE bin 7: STORE IN 101 bin 8: TRANSFER i 102 bin 9: ADD 103 bin 10: HALVE bin 11: STORE IN 103 bin 12: TRANSFER 104 bin 13: ADD 105 bin 14: SUBTRACT 106 bin 15: OBEY 0 IF MINUS bin 16: STOP

bin 101: x2-' (x, x2 24 bin 102: y bin 103: P (, ** P15 bin 104: i (0,..., 15) bin 105: 1 bin 106: 15.

66. Appendix D. Arithmetic Operations on Instruction Words. As remarked in Section 6.1, it is sometimes convenient to have arithmetic operations performed on instruction words as well as on number words. Such operations occur in the following routine, which also illustrates the use of the instruction SUBSTITUTE IN X. The problem is to compute the sum of a collection of numbers lOO, a1Ol',..., a99 stored in bins 100, 101,..., 199 of the parallel storage. bin 0: TRANSFER 202 bin 1: ADD 200 bin 2: STORE IN 202 bin 3: SUBSTITUTE IN 4 bin 4: TRANSFER 0 bin 5: ADD 203 bin 6: STORE IN 203 bin 7: TRANSFER 202 bin 8: SUBTRACT 201 bin 9: OBEY 0 IF MINUS bin 10: STOP

67. bin 100: alo0 bin 101: bin 199: bin 200: 1 bin 201: 199 bin 202: i (99,..., 199) i 199 bin 203: a; (0, *., E A) J-100 J=100

68. Appendix E. Logical Design of the ARITHMETIC UNIT. The discussion of the ARITHMETIC UNIT in Section 5.4 conveys no idea of the process of discovering or inventing a net to realize the sixteen defining formulas there presentedo In this appendix we shall attempt to show how symbolic logic can be used to achieve that end. The present discussion is intended to serve three purposes: first, to provide an alternative method of showing that the ARITHMETIC UNIT does p-rform the functions required of it; second, to show how symbolic logic can be used in logical design; and third, to help the reader understand more clearly how the ARITHMETIC UNIT works. It is obvious that (K'), the sixteenth defining formula of Section 5.4, which is ai(T- 1) - ri(7-), can be realized by sixteen delay elements with input wires r. and output wires aj, and these will constitute the core of our ARITHMETIC UNIT. The task of constructing the remainder of the ARITHMETIC UNIT can be viewed in the following way. We have sixteen output wires ri whose states are to be determined in every case by the states of all the input wires t, a, and the five control wires Ar, Ah, Ac, Als, Ars. Our task is to construct a net from these inputs to outputs r. which will be governed by the fifteen remaining defining

69. formulas of Section 5.4. That task is easily accomplished if we can find an expression of the form ri - F(t a, Ar, Ah Ac, Als' Ars) for each ri, such that these expressions logically entail the remaining fifteen defining formulas. For any net which realizes these expressions will also realize any formulas logically entailed by them. And once the ri's are expressed as explicit functions of the other terms, we can construct the net quite mechanically from theelements explained in Fig. 3. In carrying through the program sketched in the preceding paragraph we shall find it convenient (though it is not necessary) to consider wires ri and ci-1 as outputs whose states are determined by the states of the input wires ci, ti, ail, ai, ai+l, and the five control wires. The fifteen defining formulas of Section 5.4 describe the ways in which the states of these output wires are determined by the states of those input wires. But those fifteen conditional formulas express the functional dependence of ri and ci_l on the other terms not explicitly but only implicitly. What we now wish to find is an expression of the form (Er) ri F(ci ti ai-l' am' am l' Ar' Ah Ac' Als' Ars) for each rj, and an expression of the form

70. for each Cil, in which ri and ci_l appear as explicit functions of the other terms. Of course we must also find an expression of the form (E15) C15 F(Ar Ah A A As) to complete our program. The defining formulas governing ri and ci_l are all of the form (Ir) G(ArAhAcAlsArs) D ri HA(it iai-l aiai+ 4), (IC) G(Ar AhAcAlsArs) Cil- H(ci tiailaiai ) and (115) G (ArhAcAls Ar )3 15 (iiai atl in which ri and ci_l appear as implicit rather than explicit functions of the other terms. From them, however, it is easy to derive the desired expressions of the type (Er) and (Ec) by means of the following theorem, in whose statement we use the notation 5 0C for o( v O(2v...v J J J=l Theorem J. If? 0X and 0(i D0 for every i K, J=1 J J J J -(Tr-ij)} J if and only if J - i. Since the antecedents of the various (Ir) formulas cover all possible cases, exactly one of them being true at any given

71. time that the ARITHMETIC UNIT is to function, Theorem J can be applied to obtain the desired expression [Er] ri (ArAbhc) (ti*aici)v (ArAhAc) (-itai*ci) v *.. Ara -ijIn tihe same way Theorem J applies to (Ic) to yield the desired expressions Ec] ci- - (ArAhAc)(tiaivtiCivaici)v(ArAhAc) (tiai i aci) (ArhA ici)} for i> O, and [E15] clS-1 {ArAc > This last expression is equivalent to 2[E1515 _LAC since inspection of Fig. 2 shows that AC = (ArAdc). From these expressions we can pass directly to a net constructed out of the elements of Fig. 3. But such a net, while realizing the defining formulas, would not do so very economically. It would have, for example, different 3-input inequivalence elements for the first two disJuncts of [Er], whereas it is possible to use Just one such inequivalence element, as in Fig. 7. To construct a more minimal net we first alter some of the defining formulas of Section 54 to bring them into the same general form as the others. The formulas whose labels are (Alm), (Am), (Am), (St), (St), (Sm) remain unchanged.

72. But (Tn) is replaced by three formulas, by the following considerations. In Section 5.4 instruction 6 was regarded simply as demanding the replacement of r by t. We can equally well regard it as demanding the replacement of r by t4-O, which makes it a special case of addition. By substituting ri for z i, ti for Xij 0 for Yi, and ci for i in the (A) equations of Section 5.1, we obtain in place of the single formula (T4) the three formulas [Tl] _ArhAc D Eri -- (a t 0 ci)}, T2m] ArAhAcD il- (tiov tici V Oci)} for i O, [T3m] Ar-hAc P5 X to be realized by the ARITHMETIC UNIT. Similarly, the three formulas for TRANSFER COMPLEMENT X are written as [TC~3 ArAhAc i (i 0 ci), [TC2] Ar-hAc c1 - (tiOV tii Ov ci) for i 7 O, [Tc3] ArAhAc - 1 Just as the transfer can be treated as machine addition to zero, so doubling can be treated as the combination of a left shift (to accomplish the doubling) with an addition of zero. Since t = 0 whenever instruction 8 is being executed, doubling can be treated as the combination of left shift with addition of t. This treatment permits us to develop, for instruction 8, formulas of the same general type as for the others. Here we obtain four formulas

73. [D] ArAis m r (t amA c c)} for i 4 15, [Dv] ArAis cc. Cj= (tiai-1va~ticvaij ~)j for i O, [D4] Arks - =3 By a parallel route we arrive at four formulas to be realized by the ARITHMETIC UNIT in executing instruction 9. [H4] ArArs D fri (ti ~ ai1 % ci)J for i > 0, [Ha] A rArs D [Cil= (tiailV _tiCiv ai1lCi)3 for i > O, [H3] ArArs jCl5 0' These twenty formulas take the place of the first fourteen defining formulas of Section 5.4* We construct a more minimal net by first deriving a smaller number of expressions which will logically entail these twenty. To exploit the fact that all of the twenty which have the same subscript have the same general form, and that Ar occurs in every one of their antecedents, we introduce the auxiliary variables t, wi, and 6, and construct an expression of the form [E1] i r {~l — (i ( -i)} which will entail (At), (S),T [ TCJ, TC, [D and [H]. We also try to construct an expression [2] A ~ ~-iA (t-tlw v tlo-i I wc h2ic wlr eai-l-( -i -i) -i -i-Ta which will entail (A2), (S2), ITel, [TC2], [DD], and [H2m],

74. and an expression which will entail (Am), (Sm), LTm], fTC3), LD3, and CH].3 3 3 3 3 3 When they have been constructed they can be readily combined with [DM, [H, and (K) to give us a set of expressions whose realization by the ARITHMETIC UNIT will enable it to fulfill its part in the execution of all arithmetic instructions. Let us first consider ti. By inspection we note that when A is stimulated (tSm],[TCJ), ti is ti whereas in all other cases ([Am],PTm],fDm,FHmI), t4 is tie Hence we have Ac (ti -i) and Ac (tj ti), and by Theorem J - (Acti v -cti) or [:Do] -i N (A~c:t-i) Next let us consider wi. When Ah is stimulated ([Am], [Smi), wi is ai; when Als is stimulated (lbmJ), is ai+ 1; when Ars is stimulated ([Hmj), wi is ail; and in all other cases ([Tm], [TCm]), wi is 0. Hence we obtain [Mo] wi (Ahaiv Alsai+ iVArsai-1) for 0 -. i - 15 By FDm3, for wl5 we drop the second disJunct-?Of [M~O; and by [H2], for!O we replace the third disjunct of EM~J

75. by A a. Here we may replace the restriction on i in [MO~ by the convention that a16 - 0 and a1 = 0' Finally let us consider those of the twenty defining formulas whose labels have a subscript 3. When Ac is not stimulated ([A], T3 D, ), =. When Ac is stimulated (CS 3, ETC3), l5 1. Hence [E3J becomes [E3J Ar (c15 Ac)' We now assert, without proof, that formulas [E1], [E21] [LO~J,CM~,, and [E3I Jointly entail all twenty of our defining formulas.* *The proof is complicated, but may be facilitated by using appropriate versions of the following theorem, in whose statement we use the notation S F for the result of replacing every occurrence of the variable 1 in F by the expression Q(: Theorem M. O( S F if and only if both oC 4 F and (a _ S F. An example of its use is the following. Inserting.in formula [E1J the value of t' given by [L~], we obtain the expression A_ D fri - [(Ac ~ ti) $ wi` ciJ. Now applying Theorem M to that expression we obtain and ArAc O ri (t i ~ ci)J'(footnote continued p. 76)

76. We can now use Theorem J to derive an expression of the desired form (Er) which is equivalent to (K) and [E1l. The derived expression is [N -ri L ai —riv Ar(M a wi t ci)] We can also derive an expression of the desired form (Ec) from [E2] and the formula Ar {ci-l - (t!wi V tici vwi.i) which can be stipulated to hold since (K) places no restriction on ci_1. The derived expression is [] i - ii ) (Footnote from p. 75 continued) In these two formulas we insert the value of wi given by LM~O to obtain ArAc i - i (Ahaivklsai#lVArsai-_l)ci1} and Arc {ri _ -i i-haiAlsailArsai Oci Since Ah (Ah 1) implies both Ars O and As = 0 from the two formulas above we obtain ArAhAc i (ti ai i) and ArAhAc i r i (ti), which are (Am) and (St) of our defining formulas. The other defining formulas may be derived from fE1J, (E2J, [L~], [M~], and [EjJ by similar procedures.

77, Thus [Po] implies UE2J, though not conversely. The net realizing [po] is satisfactory, however, since any net which realizes [Po] will also realize [E2. Now we introduce a new variable, ui, which we define by means of the equivalence [Q ] —i -( t wi ci). If we now replace the expression which defines ui by ui in IN], we obtain [N~ _ ri- (Araiv ArUi) The degree expressions [Lo], [MO], [NO], L[po, [QO] constitute the definition of the ARITHMETIC UNIT which was sought. Any net which realizes them will perform the functions required, and it is easy to construct a net which realizes them out of the elements explained in Fig. 3. This net is in fact Fig. 7 (less the elements used in accomplishing the ARITHMETIC UNIT's transmission function).

UNVERSITY OF MICHIGAN 3 9015 02846 7374