THE UNIVERSITY OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Department of Philosophy Final Report APPLICATION OF LOGIC TO THE DESIGN OF COMPUTING MACHINES A. W. Burks H. Wang J. Holland UMRI Project 2512 under contract with AIR FORCE.OFFICE OF:SC-IENTIFIC RESEARCH CONTRACT NO. AF 18(603)-72 BALTIMORE.,.MARYLAND administered by: THE UNIVERSITY OF MICHIGAN RESEARCH INSTITUTE ANN ARBOR August 1959

- A) C-I~ a Q

PREFACE This final report has two parts. In the first, the results obtained on fixed automata are summarized. (The detailed account of these results is to be found in the technical report, The Logic of Automata, by Arthur W. Burks and Hao Wang. ) Results obtained on growing automata are summarized in the second part. ii

TABLE OF CONTENTS Page PART I 1 "THE LOGIC OF AUTOMATA" — SUMMARY by Arthur W. Burks and Hao Wang PART II 6 "A UNIVERSAL COMPUTER CAPABLE OF EXECUTING AN ARBITRARY NUMBER OF SUB-PROGRAMS SIMULTANEOUSLY" by John Holland Abstract 7 Summary 7 DISTRIBUTION'LIST 10 iii

PART I "THE LOGIC OF AUTOMATA"*-SUMMARY Arthur W. Burks and Hao Wang *AFOSR TN-56-539, ASTIA AD-110-358, also published in the Journal of the Association for Computing Machinery, 4, No. 2, 193-218, 279-297.

Classes of automata are distinguished: fixed and growing, deterministic and probabilistic (Section 2.1).* Attention is then focussed on finite automata. A finite automaton is a fixed finite structure with a fixed finite number of input junctions and a fixed finite number of internal junctions such that (1) each junction is capable of two states, (2) the states of the input junctions at every moment are arbitrary, (3) the states of the internal junction at time zero are distinguished, (4) the internal state (i.e., the states of the internal junctions) at the time t+l is completely determined by the states of all junctions at time t and the input junctions at time t+l, according to an arbitrary pre-assigned law (which is embodied in the given structure). An abstract automaton is obtained from an automaton by allowing an arbitrary initial internal state (Section 2.1). Let there be M possible input states (M possible combinations of activations or non-activations on the input wires). Designate by I the class of input states. Let there be N possible internal states and designate by S the class of internal states. Let there be P output states and designate by 0 the class of output states. The values of M and N and P are not necessarily powers of two since the structure or use of the automaton may prohibit certain states from occurring (Section 2.2). An Automaton is in general characterized by two arbitrary effective transformations ( T and A) from pairs of integers to integers. These. integers are drawn from finite sets (I), (S), and (0). (S) contains a distinguished integer So (the initial internal state of the automaton). The transformations are given by S(O) = So S(t+l) = [I(t), S(t)] O(t) = [I(t), S(t)] (If we omit the condition S(O) = So, we obtain an abstract automaton.) (Section 2.2. ) We can produce a table of MxN pairs<< I,S, S'> such that, if <I,S >is part of the state at t, then S' is part of the state at t+l1 We shall call this set the complete table of the given automaton, Each complete table is a definition of the function T. In a similar way we can construct an output table for the automaton, each now being of the form<<I,S >, 0 >. Such a table defines the function X. The function T and the complete table involve a time shift, while the function X and the output table do not. For an investigation of the behavior of an automaton through time the complete table is basic, the output table derivative (Section 2.2). *Section references are to the complete version of The Logic of Automata. 2

Two abstract automata are equivalent just in case they have the same complete table. (If the complete tables are the same, then for the same initial internal state and the same input functions, the initial complete states in the two automata are the same, and the same complete state at any moment plus the same input functions always yield the same complete state at the next moment. Section 2.2. ) In the case of automata with predetermined initial internal states (i.e., nonabstract automata), identical complete tables are sufficient but not necessary to show the equivalence of any two automata. This is possible because it can happen that, for every pair<< IS>, SI> which occurs in one table but not in the other, we can never arrive at the internal state S from the distinguished initial internal state So, and hence can never have the complete state<I,S>, no matter how we choose the input functions. To secure a necessary and sufficient condition, it suffices to determine all the internal states which the given initial internal state can yield when combined with arbitrary input words, and then to repeat this process with each of the internal states thus found: if two complete tables coincide insofar as all the pairs occurring in these determinations are concerned, the two automata are equivalent. Since there are only finitely many pairs in each complete table, the process of determination will repeat itself in a finite time. To describe the procedure more exactly, one can think of a "tree" with the chosen initial internal state So as the trunk. From the trunk M branches are grown, one for each possible input word, with the corresponding internal state at the next moment of time at the end of the branch. Whenever in the construction we come to an S that is already on the tree, we stop; otherwise we grow M branches on it as before~ This process is continued as long as some new internal state is introduced at every height. Since there are altogether only M a priori possible internal states, the number of distinct branch levels of the tree cannot exceed M. Such a tree will be called the admissibility tree of the automaton, If we collect together the ordered pairs which represent branches of the admissibility tree, we obtain a subset of the complete table which we shall call the characterizing table of the automaton. Two automata are equivalent if they have the same characterizing table. Since there is an effective method of deciding whether two automata have the same characterizing table, we have a decision procedure for testing whether two automata are equivalent (Section 2.2), If the words of the characterizing table are put in a binary form and the digits related to the junctions of the automaton, it can be decided whether or not two junctions behave the same (Section 2.2). Automata can be represented by diagrams called automata nets, which show the internal structure of automata. These nets are composed of switching elements which realize truth functions, and dela elements which delay an input one unit of time. Well- formed nets are constructed by the following rules:

(1) A switching element or delay element is well-formed. (2) If N1 and N2 are disjoint well-formed nets, then (a) the juxtaposition of N1 and N2 is well-formed: (b) the result of joining junctions of N1 to input junctions of N2 is well-formed; (c) the result of joining input junctions of N1 is well-formed; and (d) the result of joining junctions of N1 to junctions of N1 which are delay element input wires is well-formed (Section 2.3). A normal-form net is organized as follows. It has a direct-transition switch, fed by the net inputs and the delay outputs, and driving the delay inputs. It has an output switch, fed by the delay outputs and the net inputs, and not driving any delay elements, Given a sufficiently rich set of switching elements, we can always obtain the normal form net for any well-formed net. We can label the input wires to a normal form net and let I (the input state) be the concatenation of the negated (for nonactivated) and unnegated (for activated) syimbols for the separate input wires. In similar fashion we obtain designation for delay inputs, delay outputs, and direct-transition switch, We let the initial concatenation of states of delay output wires be So (the initial state of the automaton). The remaining elements of S are the other concatenations of states of the delay output wires determined by the net and its inputs. From the states of the net we can construct a complete table. By use of the admissibility tree we can construct the characterizing table. Therefore, given a well-formed net, we can construct a complete table, a characterizing, and an output table describing its behavior. By considering the binary codings, if we are given a complete table, characterizing table, and an output table, we can construct a well-formed net realizing these tables (Section 2.3). The information in a characterizing table can be arranged in a direct-transition matrix. The rows and the columns of the matrix are labeled with the internal states of the automaton; the matrix entries themselves are the input states which will take the automaton from one internal state to another. When there is no input which will directly take the automaton from a certain internal state to another particular internal state the matrix entry "O'" is to appear (Section 3.1)e An abstract automaton is backwards deterministic if and only if for each finite sequence I(0), I(1),..., I(t), S(t+l), there is a unique sequence S(0), S(1),..o. S(2) satisfying the complete table, A direct transition matrix is backwards deterministic if and only if for each I and S there is at most one other internal state such that I and this other internal state directly produce S. If a direct-transition matrix is backwards deterministic, the associated abstract automata is backwards deterministic (Section 3.3). Fixed, deterministic nets can be analyzed in terms of cycles. A sequence of junctions Al, A2,..., An, A1 (possibly with repetitions) constitutes a cycle if and only if each Aj is an input to an element whose output is Ak, where k- j+l modulo n. Thus a junction occurs in a cycle if it is possible 4

to start at that junction, proceed forward (in the direction of the element wire arrows) through switching elements and delay elements, and ultimately return to the junction. A junction which does not occur in a cycle has degree zero, as does an input-independent junction. The degree of a noninput-independent junction which occurs in a cycle is the maximum number of distinct delay elements it is possible to pass through by traveling around cycles in which the junction occurs. The degree of a net is the maximum of the degrees of its junctions (Section 4.1). The close correspondence between switching nets and the theory of truth functions has been noted earlier. If to the theory of truth functions we add a 5 operator (which when applied to the input value of a delay element gives the output value of that delay element) and also allow the system to include expressions like t = a, t > a, (t-a) - c mod b (where t is a variable and a, b, and c are integers) we can describe any periodic function. This system is called the extended theory of truth-functions. For every junction of a net of degree zero, we can effectively construct a formula of the extended theory of truth functions which describe the behavior of the junction as an explicit function of the behavior of the inputs (Section 4.2). For explication of all the foregoing remarks, including many examples of the processes discussed (and also consideration of and comment on numerous other automata problems), the reader is referred to the original technical report. 5

PART II "A UNIVERSAL — COMPUTER CAPABLE OF EXECUTING AN ARBITRARY NUMBER OF SUB-PROGRAMS SIMULTANEOUSLY" John Holland

ABSTRACT The paper describes a universal computer capable of simultaneously executing an arbitrary number of sub-programs, the number of such sub-programs varying as a function of time under program control or as directed by input to the computer. Three features of the computer are: (1) the structure of the computer is a 2-dimensional modular (or iterative) network; (2) each sub-program is spatially organized, thus facilitating the simulation of "highly parallel" systems having many points or parts; and (3) the computer's structure and behavior can, with simple generalizations, be formulated so as to make it a useful abstract tool for investigating problems in automata theory. SUMMARY The main purpose of this paper is to describe a univeral computer capable of simultaneously executing an arbitrary number of sub-programs under program control. The formulation is intended as an abstract prototype which, if current component research is successful, could lead to a practical computer. The computer can be considered to be composed of modules arranged in a 2dimensional rectangular grid; the computer is homogeneous (or iterative) in the sense that each of the modules can be represented by the same fixed logical network. The modules are synchronously timed and time for the computer can be considered to be divided into discrete units or time steps, t = 0, 1, 2,.... Basically each module consists of a binary storage register together with associated circuitry and some auxiliary registers. At each time-step a module may be either active or inactive. An active module, in effect, interprets the number in its storage register as an instruction and proceeds to execute it. There is no restriction (other than the size of the computer) on the number of active modules at any given time. Ordinarily, if a module M(i,j) at coordinates (i,j) is active at time-step t, then at time-step, t+l, M(i,j) returns to inactive status and its successor, one of the 4 neighbors M(i+l,j), M(i,j+l), M(i-l,j), or M(i,j-l), becomes active. The successor is specified by bits sl, s2 in M(i,j)'s storage register. If we define the line of successors of a given module as the module itself, its successor, the successor of the sucessor, etc., then a given sub-program in the computer will usually consist of the line of successors of some module. The action of a module during each time-step can be divided into three successive phases.

1. During Phase One, the input phase, a module's storage register can be set to any number supplied by a source external to the computer. Although the number in the storage register can be arbitrarily changed during Phase One, it need not be; for many purposes the majority will receive input only during the first few moments of time ("storing the program") or only at selected times t1, t2,... ("data input"). 2. During Phase Two, an active module determines the location of the storage register upon which its instruction is to operate by, in effect, marking a path to it. The path-building action depends upon two properties of modules. First, each module has a neighbor, distinct from its successor, designated as its predecessor by bits ql, q2 in its storage register; the line of predecessors of a given module is then defined as the sequence of all modules MO M1,..., M,... such that, for each k, Mk is the predecessor of Mk-l and Mk_1l is the successor of Mk. Secondly, by setting bit p in its storage equal to 1, each module may be given a special status which marks it as a point of origination for paths; the module is then called a P-module. Each path must originate at P-module, and only one path can originate at any given P-module. The modules belonging to a given path can be separated into subsequences called segments. Each segment consists of y modules extending parallel to one of the axes from some position (i,j) through positions (i+bl, j+b2), (i+2bl, j+2b2),..., (i+(y-l)bl, j+(y-l)b2), where bl=l, 0, -1 and b2= +(l-Ibll); the module at (i+ybl,jybb2) will be called the termination of the segment. Each module possesses 4 *-registers and if the module belongs to a segment in direction (bl, b2) the appropriate *-register, (bl,b2)*, is turned on gating lines between (i,j) and (i+bl,j+b2). Since each *-register gates a separate set of lines, a module may (with certain exceptions) belong to as many as four paths. Once a *-register is turned on, it stays on until it is turned off; thus a path segment, once marked, persists until "erased." Each segment of a path results from the complete Phase Two action 6f a single active module. At the start of Phase Two the path specification bits Yn-, * Y-, o and dl, d2 are gated down the line of predecessors from the storage register of the active module to the nearest P-module along the line of predecessors. Let the termination of the final segment of the path originating at that P-module be called the nearest path termination. Then,if yn= 0, bits Yn-l,'.', yo and dl, d2 determine the length and direction, respectively, of a new segment which has as its initial module the nearest path termination. If yn=l, then the final segment of the path is erased (bits Yn-1,..., Yo and dl,d2 not being used in this case). 3. Phase Three, the execution phase, depends upon the fact that, by setting the pair of bits (p,a) in a module's storage register to the value (0,1) the module can be given a special status which marks it as an accumulator; a module in this status is called an A-module. The number in the storage register of an A-module is treated simply as a binary number with yn being the sign bit and Yn_1 the high-order digit. 8

Three modules play an important role during the execution phase of an active module: the active module itself holds the order code in bits il, i2, i3 of its storage register; the storage register of the nearest path termination containsthe word to be operated on; and the A-module nearest along the line of predecessors, after the nearest P-module, serves as the accumulator. For example, if an active module has a TRANSFER ON MINUS order coded in bits il, i2, i3, and if the number in the nearest A-module is minus, then at the end of the time-step the module at the nearest path termination becomes active instead of the active module's successor. In the present formulation there are 8 types of instruction: (1) TRANSFER ON MINUS, which has already been described; (2) ADD; (3) SUBSTRACT; and (4) STORE act similarly, the nearest path termination serving as the address for the order; (5) NO ORDER causes the execution phase to pass without the execution of an order; (6) STOP prevents an active module from passing on its activity; (7) ITERATE SEGMENT causes 1 to be subtracted from the number in the the A-module, and, if the result is positive, the active module remains active on the next time-step (rather than passing on its activity); thus the pathbuilding phase of the given module is iterated; and (8) SET REGISTERS causes the first 9 bits of the A-module's number to be used to set all 9 auxiliary registers at the nearest path termination; by setting the auxiliary register which gives the module active status, both that module and the successor of the active module will become active on the next time-step. To resolve possible conflicts when several active modules interact, a set of interlock and over-ride rules are required. In the present formulation 10 such rules suffice. Recapitulating briefly, the universal computer described has three prominent features: 1. The basic structure is iterative. 2. The sub-programs have a spatial organization and any number can be executed simultaneously. 3. Features (1) and (2) make possible theoretical investigation of the interactions of various classes of sub-programs (e.g., by considering the rectangular grid to cover an infinite plane, cf. Church's potentially infinite automata and Von Neumann's scheme for self-reproducing automata). It should be noted that the present formulation is representative of a broad class of similar machines. 9

DISTRIBUTION LIST (One copy unless otherwise noted) Commander 3 Director of Advanced Studies European Office, ARDC Air Force Office of Scientific 47 Rue Cantersteen Research Brussels, Belgium P. 0. Box 2035 Pasadena 2, California Applied Mathematics and Statistics Laboratory Commander Stanford University Western Development Division Stanford, California Attn: WDSIT P. 0. Box 262 Commander Inglewood, California Fifteenth Air Force Attn: Operations Analysis Office Office of Naval Research 2 March Air Force Base, California Department of the Navy Attn: Code 432 Department of Mathematics Washington 25, D.C. University of California Berkeley, California Department of Commerce Office of Technical Services Assistant CINCSAC Washington 25, D.C. (SAC MIKE) Attn: Operations Analysis Office Director of National Security Box 262 Agency Inglewood, California Attn: Dr. Ho H. Campaigne Washington 25, D.C. C ommande r Air Force Flight Test Center Library Attn: Technical Library National Bureau of Standards Edwards Air Force Base, California Washington 25, DC. The RAND Corporation National Applied Mathematics Technical Library Laboratories 1700 Main Street National Bureau of Standards Santa Monica, California Washington 25, D.C. Commander Headquarters, USAF 1st Missile Division Assistant for Operations Analysis Attn: Operations Analysis Office Deputy Chief of Staff, Operations, Cooke Air Force Base AFOOA Lompoc, California Washington 25, D.C. Department of Mathematics Department of Mathematics Yale University Northwestern University New Haven, Connecticut Evanston, Illinois 10

DISTRIBUTION LIST (Continued) Commander 2 Commander, Second Air Force Air Force Office of Scientific Attn: Operations Analysis Office Research Barksdale Air Force Base, Louisiana Attn: SRDB Washington 25, D.C. Institute for Fluid Dynamics and Applied Mathematics Commander 2 University of Maryland Air Force Office of Scientific College Park, Maryland Research Attn: SRE Department of Mathematics Washington 25, D.C. Harvard University Cambridge 38, Massachusetts National Science Foundation Program Director for Mathe- Commander, Eighth Air Force matical Sciences Attn: Operations Analysis Office Washington 25, D.C. Westover Air Force Base Massachusetts C ommande r Air Force Armament Center Department of Mathematics Attn: Technical Library Massachusetts Institute of Technology Eglin Air Force Base, Florida Cambridge 38, Massachusetts C ommande r Commander Air Force Missile Test Center Air Force Cambridge Research Center Attn: Technical Library Attn: Geophysics Research Library Patrick Air Force Base, Florida L. G. Hanscom Field Bedford, Massachusetts Institute for Air Weapons Research Museum of Science and Industry Commander University of Chicago Air Force Cambridge Research Center Chicago 37, Illinois Attn: Electronic Research Library L. G. Hanscom Field Department of Mathematics Bedford, Massachusetts University of Chicago Chicago 37, Illinois Department of Mathematics Wayne State University Department of Mathematics Detroit 1, Michigan University of Illinois Urbana, Illinois Willow Run Research Center The University of Michigan Department of Mathematics Ypsilanti, Michigan Purdue University Lafayette, Indiana Department of Mathematics Institute of Technology Mathematics and Physics Library Engineering Building The Johns Hopkins University University of Minnesota Baltimore, Maryland Minneapolis, Minnesota 11

DISTRIBUTION LIST (Continued) Department of Mathematics Professor J. Wolfowitz Folwell Hall Mathematics Department, White Hall University of Minnesota Cornell University Minneapolis, Minnesota Ithaca, New York Department of Mathematics Department of Mathematics Washington University Syracuse University St. Louis 5, Missouri Syracuse, New York Department of Mathematics Mathematics Research Group University of Missouri New York University Columbia, Missouri Attn: Professor M. Kline 25 Waverly Place Commander New York, New York Strategic Air Command Attn: Operations Analysis Department of Mathematics Offutt Air Force Base Columbia University Omaha, Nebraska Attn: Professor B. 0. Koopman New York 27, New York The James Forrestal Research Center Library C ommander Princeton University Rome Air Development Center Princeton, New Jersey Attn: Technical Library Griffiss Air Force Base Library Rome, New York Institute for Advanced Study Princeton, New Jersey Commander Rome Air Development Center Departnent of Mathematics Attn: RCWEA Fine Hall Griffiss Air Force Base Princeton University Rome, New York Princeton, New Jersey Institute for Aeronautical Sciences Commander Attn: Librarian Air Force Missile Development 2 East 64th Street Center New York 21, New York Attn: Technical Library Holloman Air Force Base Institute of Statistics New Mexico North Carolina State College of A and E Commander Raleigh, North Carolina Air Force Special Weapons Center Attn: Technical Library Department of Mathematics Albuquerque, New Mexico University of North Carolina Chapel Hill, North Carolina 12

DISTRIBUTION LIST (Concluded) Office of Ordnance Research 2 Applied Mechanics Reviews 2 Box CM, Duke Station Southwest Research Institute Durham, North Carolina Attn: Executive Editor 8500 Culebra Road Department of Mathematics San Antonia 6, Texas Duke University, Duke Station Durham, North Carolina Defense Research Laboratory University of Texas Commander Austin, Texas Air Technical Intelligence Center Attn: ATIAE-4 Department of Mathematics Wright-Patterson Air Force Base Rice Institute Ohio Houston, Texas Commander Commander Wright Air Development Center Air Force Personnel and Training Attn: Technical Library Research Center Wright-Patterson Air Force Base Attn: Technical Library Ohio Lackland Air Force Base San Antonio, Texas Commander 2 Wright Air Development Center Armed Services Technical Attn: ARL Technical Library, WCRR Information Agency 10 Wright-Patterson Air Force Base Arlington Hall Station Ohio Arlington 12, Virginia Commandant 2 Department of Mathematics USAF Institute of Technology University of Wisconsin Attn: Technical Library, MCLI Madison, Wisconsin Wright-Patterson Air Force Base Ohio Mathematics Research Center U. S. Army Department of Mathematics Attn: R. E. Langer Carnegie Institute of Technology University of Wisconsin Pittsburgh, Pennsylvania Madison, Wisconsin Department of Mathematics University of Pennsylvania Philadelphia, Pennsylvania Commander Arnold Engineering Development Center Attn: Technical Library Tullahoma, Tennessee 13

UNIVERSITY OF MICHIGAN 9015 02656 641711111 3 9015 02656 641