THE UNIVERSITY OF M I C H IGA N COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Communication Sciences Program Quarterly Report No. 2 15 July 1962 - 15 October 1962 MACHINE ADAPTIVE SYSTEMS Arthur W. -urks J. Willisdoi Crichton Marion R. Finley ORA Project 05089'under icontract with: DEPARTM NT OF THE ARMY U. S. ARMY SIGNAL SUPPLY AGENCY CONTRACT NO. DA-36-039-SC-89085 FORT MONMOUTH, NEW JERSEY administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR October 1962

tea 9 Ed i a a,.: t t _,., / v\. --, I.-... i,

TABLE OF CONTENTS Page TOWARD A THEORY OF AUTOMATA BASED ON MORE REALISTIC PRIMITIVE ELEMENTS by Arthur W. Burks 1 List of Figures 2 1. Introduction 3 2. Idealized Automata 3 3. Behavior and Computation 5 4. Slow Automata 7 5. Probabilistic Automata 13 6. Cellular Automata 24 References 26 NERVE-NET SIMULATION by J. Willison Crichton and Marion R. Finley 35 PERSONNEL 39 OBJECTIVES FOR NEXT QUARTERLY PERIOD 41 iii

TOWARD A THEORY OF AUTOMATA BASED ON MORE REALISTIC PRIMITIVE ELEMENTS Arthur W. Burks

LIST OF FIGURES Figure Page 1o Idealized primitives. 28 2. Input tape reader. 28 3. Output tape writer. 29 4. Computation of an automaton. 29 5. Slow primitives 30 6. Normal form net. 30 7. Probabilistic nan. 31 8O Slow probabilistic primitives. 31 9, Probabilistic automaton. 32 10. Deterministic state diagram. 32 11. Probabilistic state diagram. 32 12. Restoring organ-multiplexing factor N = 3. 33 13. Multiplexed-and-restored nan organ- multiplexing factor N = 3. 33

1. Introduction* We will begin with automata composed of the idealized primitive elements usually studied in automata theory, and then consider automata based on primitive elements which simulate more closely the actual operation of both artificial and natural systems. We are particularly interested in comparing the computational powers and rates of these more "realistic" automata with the computational powers of idealized automata. 2. Idealized Automata An idealized automaton is constructed from instantaneous "nan" (not-and) switches and unit delays whose initial output states are either one or zero (Fig. 1). Unlimited branching ("fan-out") is allowed, but all cycles must pass through delays. These primitive elements operate synchronously, with time having the integral values 0, 1, 2,... A finite idealized automaton is composed of a finite number of elements. Those wires which are not driven by other wires are called the inputs of the automaton; certain wires are designated as the outputs of the automaton. There does not exist a single satisfactory general definition of an infinite automaton, and we will consider only one special case. A Turing machine *The writing of this paper was supported by the U. S. Army Signal Corps through Contract DA-36-039-SC-89085 and Grant DA-SIG-36-039-61-G4.

consists of a finite idealized control automaton attached to an infinite tape. The tape itself is an idealized automaton. It is an infinite shift register, that is, an infinite iterative array of finite idealized automata. Each finite automaton of this linear array is the same except that a finite number of them may have delays whose initial outputs are one instead of delays whose initial outputs are zero. Our only purpose in having both kinds of unit delays is to be able to vary the kind of delays in an automaton (i.e., the initial state) while leaving the rest of the automaton unchanged, as in the present instance. Either kind of delay can be synthesized from the other by means of the nan switch. This is the same as saying that only a finite number of squares of a tape may be marked initially; all the rest must be blank. Since the control automaton is finite, only a finite amount of information can be stored in a Turing machine initially. It follows that at each time t only a finite amount of information will be stored in a Turing machine, though this quantity of information can grow without bounds. Note that a Turing machine in our sense has a finite number of input wires and a finite number of output wires, in contrast to Alan Turing's original conception [1]. Since actual switching takes time, this separation of primitives into instantaneous switches and pure delays is clearly an idealization. It is a useful idealization for two reasons. First, Boolean algebra (i.e., truth-function theory) may be applied simply and directly to the analysis of instantaneous switches, whereas the analysis of switches with built-in delays is more complicated. Second, the time actually required for switching varies with the

state of technology, and hence it is desirable to have both instantaneous switching primitives and switching elements with built-in delays, the former for studying what is needed from a purely logical point of view, the latter for studying what is needed from a technological point of view. 3. Behavior and Computation Let there be given a finite alphabet of input {'output) characters or states. Let I be the set of all infinite sequences of type omega (i.e., corresponding to the numbers 0, 1, 2,... ) of input characters, and let G be the set of all infinite and finite sequences of output characters. A finite sequence may occur as the computed output of an automaton; see below. When a sequence < io, il, i2,... > of I is fed into the inputs of an automaton at times 0, 1, 2,... respectively the automaton will produce an output sequence <G, 01g 029... > belonging to 0; the behavior of an automaton is the mapping it produces from I into 8. Finite automaton behaviors have been studied intensively (e.g., [2], [3]), but though the behaviors of Turing machines are of interest ([4], [5], [6]) the concept of behavior is not nearly so important for the theory of Turing machines as the concept of "computation." This latter concept has been defined in a number of different ways, none of which is applicable to finite automata, so we will offer a new definition of computation. This is an extension of the definitions of [4], p.o 285. 5

Each sequence of I tG) may be regarded as an input [output.) tape. An input tape may be placed in the input tape reader R of Figs. 2 and 4, which works as follows. The tape symbol being scanned at time t appears at the output instantaneouslyo When the "read control" wire is activated (put in state one) at time t the tape reader advances -the tape one square, so that at time t+l the next symbol appears on the output of the tape reader and hence at the input of the automaton. If the read control is inactive at time t the tape is not advanced, so that in this case the symbol which appeared at the output of the tape reader at time t also appears there at time t+l. The output tape writer W of Figs. 3 and 4 works similarly: whenever the "write control" wire is activated the tape sym.bol being presented to the tape writer by the automaton is recorded on the output tape and the tape is advanced to the next blank square. Note that the read and write control wires are outputs of the automaton, so that it controls their actions. Both reader and writer can only move their tapes forward, so that neither can be used for intermediate storage during a computation. The computation of an automaton is the mapping it produces from I into 0 when the sequences of I are supplied to the input tape reader and the sequences of 0 are produced by the output tape writer (.see Fig. 4). It is clear from this definition that behavior is a special case of computation: that case in which the read and write control wires are always active (in state one), That is, behavior is "real-time' computation. The foregoing definitions of behavior and computation also apply to the slow automats and cellular automata to be introduced later. It is of interest to compare finite idealized automata and Turing machines 6

with respect to certain problems concerning behavior and computation. Consider, for example, the four problems: Is there an algorithm (i.e., Turing machine) for deciding whether any two < finite idealized automata > (Turing machines) have the same (behavior) [computation]? There is an algorithm for deciding whether any two finite automata have the same behavior ([2], [3], [7]), but there is no algorithm for deciding whether any two Turing machines produce the same computation. It can be shown that if there were there would be an algorithm for deciding whether or not an arbitrarily given Turing machine will "halt," and Turing [1 ] showed that there is no such algorithm. In our terminology a machine which halts is a machine which records only a finite number of output characters on the output tape. The solutions to the other two problems are unknown. Friedman [8] gives a solution for the case of finite automata in which the read control wire is always active (i.e., the input tape advances one square every unit of time). See also Burks and Wright [9]. 4. Slow Automata The automata we consider next are intended to reflect, to some degree, the physical facts that time is required for switching and that the number of wires a single component can drive is limited by power and time requirements. The primitives we will use are shown in Fig. 5. Every "nan" switch is added fol7

lowed by n units of delay. An "and" switch is added which has a units of delay. The output wire of an element can be connected to at most one input wire. Hence when information is to be sent to two or more places a branching or fan-out element must be used; this element has b units of delay. The output of the (nan) (and) [branching] element is inactive for the first (n) (a] [bI units of time. It is stipulated that an element output wire which is designated as the output of the aut.,cmaton can be connected to notic-1ing within the automaton itself, but is to be reserved to operate something else, e.g., a tape writer. Any automlnaton consr,ructed from a finite number of slow elements by these rules is called a finite slow automaton. While the slow primitives of Fig. 5 are more realistic than the idealized primitives cf Fig. 1, we could have chosen an even more realistic set of primitives. For example, we might have chosen four switching primitives realizing pq, pq, pq, and pq- each followed by a unit delay, and a branching element with four outputs and a unit delay. The reason for our less realistic choice is as follows. When one is interested in a particular type of equipment he should choose a set of slow primnitives which mirrors the properties of this equipment. But, we are interested in the general computational powers of automata composed of slow elements, and have chosen the primitives of Fig. 5 because they can be made arbitrarily slow by choosing n, a, and b to be large. It wll1 be seen that the results we give belcw are easily extended to cover faster sets of primitives. 8

We will now compare finite slow automata with finite idealized automata. It is clear that corresponding to each slow automaton there is a behaviorally equivalent idealized automaton. The converse is not the case, however. Given a finite idealized automaton, in general there is no slow automaton behaviorally equivalent to it, because the switching done instantaneously in the idealized automaton takes time in the slow automaton. But for each idealized automatonr one can construct a computationally equivalent slow automaton. More particularly, there is an algorithm which, when supplied with the design of a finite idealized automaton Ai, will design a finite slow automaton As computationally equal to Ai. We will call this our first algorithm. There is not time to present this algorithm in detail, but we will sketch the essential parts of it. it contains a subalgorithm which operates on an idealized finite switch S to produce a slow switch S' which realizes the same truth-function as S but with a fixed delay d, the length of the delay depending on the switching function. S' is constructed from S as follows. Each "nan" element of S is replaced by a slow "nan" element with n units of delay. Then each branch of S is replaced by a tree of branching elements. This must also be done where a wire of S is used both as an output wire for the whole switch and to drive another wire within the switch. Finally sequences of delays are introduced into the lines so that the timing is correct, ioe., so that for each point of switch S' the transit times over all paths from the inputs to this point are equal, and so that the transit times through the switch from inputs to outputs are all the same integer d. 9

Let a and P be finite bi nary sequences and let Z be a sequence of c zeros. COur first algor-itrL21 also cntains a su.balgoriin which when given, designs a siow autoJJmaton t1wit hout inputc~s) whose behavioral output is the infinite seq-uence ZCf3f55.3,T where the index c is a fcnction of a and 5o Each finite binary seluenee cX9, is form-<ed by generataing a single puLse, sending it along paths of dciferet lengths, and merging tihese paths. 3 is repeated indefinitely by means of a cycle. Hence any ult-imately periodic sequence appp'.o can be produced by a slow a:utomaton after some fixed delay c. Our first al goritrum now operates on the given idealized automaton Ai as follows. i ut puats Ai in'ne nonmal form of Fig. 6, where the switch Si is instantaneous. It t.en replaces t+his switch Si with a slow switch Ss which does the following. First, Ss realizes the same switching function as Si but with delay e. Second, Ss receives th'e initial state of Ai at some appropriate time t whenr signaled to do so by a control pulse. Third, under the direction of an ultimatiely periodic control sequence the slow switch Ss only allows the tape read and t-ape wr-ite control wires to be ac tive at ti me t + (e+l) - 1, t + 2(e+l) - I, s+ 3& (ei)-) -!r,.. As a final step the first algorithm adds the ulltimat.ely periodic circuits needed for controlling Ss and to supply the inital state of Ai toj -Ss,'The result. of t: IiJ algoriLtm.n is a slow automaton AS -which mimics the behavior of Ai at. a slow rate. Ai start+s in some internal state at time zero; As starts in this s+tate at a later time. Ai makes a transition from one internal state to the next in one unit of time; As makes the same transltion in el units of time. What As does in between these times does not 10

matter, because the control signals prevent these intermediate actions from affecting the operation of the input and output tapes. Consequently, As produces the same computation as Ai. Clearly the rate of computation of As is only a fraction (e+l)-l of the rate of computation of Ai. The question naturally arises: Is there a slow automaton which computes as fast as any given idealized automaton? In general there is not, because the decision as to whether or not to advance the input tape may depend on the tape symbol being scanned, and while this decision can be made instantaneously in an idealized automaton, it takes time in a slow automaton. This argument does not apply when the read control output from the idealized automaton is input-independent. In this case the read control signal is ultimately periodic and can be produced by a slow automaton (see the first algorithm). Moreover, there is an algorithm which, when given an idealized automaton Ai, will synthesize a finite slow automaton As* whose behavior is the same as that of Ai except that the outputs of As* are delayed by some fixed amount g. This algorithm is given in [10]. According to this reference the algorithm was discovered by a number of different people. A control circuit and gate may be added so that the write control wire cannot be activated before time g. Combining all this we get our second algorithm. When given the design of an idealized finite automaton Ai whose read control output is ultimately periodic, this second algorithm designs a computationally equivalent finite slow automaton As* which computes at the same rate as Ai 11

after an initial delay g. The slow automaton As* produced by the second algorithm will generally have many more primitive elements than the slow automaton As produced by the first algoritZn, Hence the greater speed of As* is obtained at the cost of additional equipment. it would be of interest to automata theory to have some general theorems gcoverning interchanges of speed and equipment of this sort. There is an extended concept of computation which is of interest. Let the <input tape reader scan> [output tape writer print ] up to h squares at once and allow it to be advanced from 1 to h squares in a time step. Then for each idealized finite automata A and each integer h there is a finite idealized automaton A' which is computationally equivalent to A but computes h times as fast. We can consider Turing machines only briefly. A Turing machine consists of a finite control automaton connected to an infinite shift register, and in our original definition these were both constructed from idealized primitive elements. Both the finite control automaton and the infinite shift register can also be constructed from slow primitive elements so that for each Turing machine mnade of idealized primitives there is a computationally equivalent Turing machine made of slow primitives. There is not time to give the construction here. 12

5. Probabilistic Automata The automata we have discussed so far are all deterministic. Actual computers make errors, and natural systems often function in non-dete.rministic, statistical ways. Probabilistic automata are intended as models which mimic, to a first approximation, the statistical characteristics of real systems. Each primitive element of a probabilistic automaton produces the "correct" output with probability l-e: and the "incorrect" output with probability e. For example, a probabilistic "nan" element has the probabilistic truth-table of Fig. 7: it produces the "nan" function with probability 1-e and the "and" function with probability e. The matter of whether a primitive element is probabilistic or not is independent of whether it is slow or not. However, for the sake of simplicity we will consider only finite automata made from either of two sets of probabilistic primitives: the probabilistic version of the idealized primitives of Fig. 1, and the slow probabilistic primitives of Fig. 8. In each case the probabilistic operation of the primitives is defined with respect to a specified deterministic operation. The deterministic definition gives the desired or "correct" answer, and in discussing probabilistic automata it is often convenient to refer to this deterministic norm. Probabilistically the element gives the correct answer with probability 1-e, the incorrect answer with probability c. In view of what has just been said, the probabilistic elements of Fig. 8 may be defined by specifying their deterministic behavior. The second primitive is a "majority element" whose initial output is zero and whose output at time t+l is one (active) if and only if two or more of 13

its inputs are active at time t. The third primitive of Fig. 8 produces a constant zero (inactive) output. For simplicity we will allow unlimited branching with each set of primitives. A great deal may be learned about probabilistic automata by studying the input-free case. Consider the simple example of Fig. 9, where the initial state of the delay is left unspecified. Its deterministic state diagram is given in Fig. 10; whatever its starting state, it remains in that state for ever. Hence, as a deterministic system its memory span is infinite, though of course its memory capacity is finite. But probabilistically it behaves differently, as its probabilistic state diagram (Fig. 11) shows. Probabilistically it can make a transition from either state to either state. Consequen-tly a finite probabilistic automaton has only a finite memory span, as we shall now show. Consider the state diagram of an arbitrary input-free finite probabilistic automaton. When the automaton is in a given internal state ai it may pass from this to any other state aj with a non-zero probability Pij. Let n be the number of internal states of the automaton. Then for each internal n state ai we have Z pij = 1, and there is an n by n probabilistic transition j=1' matrix M governing the transitions between states, with every element of M being non-zero. Let IT = [Pl, P2,.'', Pn] be the probability vector of the initial state, where Pi is the probability that the automaton will start in state ai. It is clear from all this that the sequence of states of the automaton is a Markov chain, starting in some state at time zero in accordance with the probability vector n and making transitions according to the Matrix M.

A regular Markov chain is one in which some finite power of the transition matrix has only positive elements. Since all elements of M itself are positive, the sequence of internal states of a finite, probabilistic, inputfree automaton is a regular Markov chain. For any regular transition matrix M there is a unique probability vector G such that for any probability vector (1) Limit ~* Mt =. t - 00 Note now that as we vary the unit delays of the automaton between those whose initial outputs are zero and those whose initial outputs are one, while leaving the rest of the automaton unchanged, we are varying the initial vector A but leaving the transition matrix M unchanged. Hence this theorem tells us that the ultimate statistical character of the sequence of internal states of a probabilistic automaton is independent of the initial state. For example, whether the question mark of Fig. 9 is replaced by a zero or a one, in the limit the output is as likely to be a one as a zero. Hence the initial state of a probabilistic automaton has less and less influence on its behavior as time increases. We can study the memory properties of a probabilistic automaton by investigating how fast an input-free probabilistic automaton forgets its initial state. Specifically, we ask how much information its present internal state gives us about its initial state. Without any essential loss of generality we may confine our attention to Fig. 9. Let O(t) mean that the output is one (active) at time t. Imagine that Fig. 9 is a black box, so that we do 15

not know which delay element of Fig. 1 is there. There are two hypotheses: h says that the question mark is to be filled in with a one, h that it is to be filled in with a zero. That is, p[O(O) Ih] = 1-E and p[O(O) 1h] = E. If Fig. 9 were deterministic, O(t) for any t would give us perfect information about the box: O(t) implies h, O(t) implies h. Since Fig. 9 is probabilistic, O(t) gives us only statistical information about h and h. To see exactly how much information it gives we will apply Bayes' theorem of inverse probabilities. Let P[h|O(t)] be the probability of hypothesis h conditionally on the observation O(t), and similarly for P[hjO(t)]. By Bayes' theorem (2) P[h O(t)] P(h) P[O(t) h] P[IjO(t)] P(h) P[O(t) (h] i.e., the ratio of the posterior probabilities equals the ratio of the prior probabilities times the ratio of the degrees of prediction. The ratio of the posterior probabilities divided by the ratio of the prior probabilities is a measure of the amount of information the observation O(t) gives us about the hypothesis h. This amount of information can be computed as a function of c, M, and t. We will not make the calculation here, but will instead look at what happens in the limit. By (1) Limit P[O(t) h] = 1 t -+ o P[O(t) h] Hence Limit P[hlO(t) ] t P(h) = 1 t + 0I P[hlO(t) ] P(h) In other words, as t increases the observation O(t) gives us less and less information about the contents of the black box, and in the limit it gives us 16

no information. Hence a probabilistic automaton forgets more and more as time continues and in the limit remembers nothing. The forgetting of an input-free finite probabilistic automaton can also be analyzed in terms of Shannon's information theory [11]. For this purpose we can think of the automaton (cf. Fig. 6) as being stretched out in space, so that it consists of noisy unit delays alternating with a perfect switch ad infinitum. The initial state of the automaton is then transmitted through this infinitely long channel. At time t it will have passed through t delayswitch combinations, i.e., through t noisy delays and through t deterministic recodings. The loss of information as a function of time can be calculated by means of information theory. The result will be the same as we obtained by means of Bayes' theorem: as t increases indefinitely the amount of information transmitted approaches zero. The result just given is for memory in input-free probabilistic automata. But remembering is a special kind of computation (as we defined the term) and input-free automata are a special kind of automata, so one can see by analogy that a similar result holds for the computation of probabilistic automata generally: as time passes the probability of a mistake in computation rises, and in the infinite limit the computed answer is mere noise. Fortunately, from a practical point of view we are interested only in finite computations, that is, in computations which take a finite amount of time. With respect to finite computations the actual rate of degeneration of information is of interest, as well as techniques for retarding this loss of information and rendering errors less likely. 17

The late John von Neumann developed a method for synthesizing reliable automata from unreliable elements [12]. His method is for slow switches only, but by means of the algorithms of Section 4 we will extend it to cover arbitrary finite automata. Von Neumann's method involves replacing single lines driving single elements by multiplexed cables driving arrays of elements. As extended, it accomplishes roughly the following: given a probabilistic idealized automaton Ai it produces a multiplexed automaton Am related to Ai as follows: deterministically, Am is much more reliable than Ai. We will build the multiplexed automaton from the primitives of Fig. 8, but these are first made into multiplexed organs: a restoring organ (Fig. 12) and a multiplexed-and-restored nan organ (Fig. 13). The inputs and outputs of these multiplexed organs are cables of N wires rather than single wires; N is called the multiplexing factor. For simplicity we have used a multiplexing factor of only three in Figs. 13 and 14, but in practice the multiplexing factor must be much larger; the multiplexing factor N must be sufficiently large to give the reliability desired and to warrant the use of statistical methods in analyzing the behavior and computation of the multiplexed automaton. A finite automaton constructed from these two kinds of organs is called a finite multiplexed automaton. Its inputs and outputs are cables of size N. In the sequel we will compare the computation of idealized automata with the computation of multiplexed automata; in this comparison single wires of idealized automata are to be compared with cables of multiplexed automata. 18

A multiplexed automaton is so constructed that if it were deterministic all the wires of a given cable would be in the same state at the same moment of time, Since the automaton is probabilistic this will not be so, but if N is sufficiently large compared to E and the design is suitable then it will be nearly so; more precisely, under these conditions the probability will be high that most of the wires of a given cable will be in the same state at any given moment. The activity level of a multiplexed cable is interpreted relative to a statistical fiduciary parameter A as follows. If (1-A)N or more wires are active (in state one), the cable is taken to represent a one; if AN wires or less are active, the cable is taken to symbolize a zero; and if the activity level falls between A and (1-A) the signal on the cable is not interpreted (i.e., is "nonsense"). A restoring organ consists of a randomizer driving a parallel array of N majority elements (Fig. 12). Each of the N wires of the input cable is split into three wires before entering the randomizer; the randomizer permutes these wires before they drive the majority elements. Deterministically a restoring organ merely delays the pulses of the input cable one unit of time. Probabilistically a restoring organ operates as follows, Let (5) y] be the probability that an (input wire) (output wire) is in error at any given time t. Since the randomizer only permutes wires, X is also the error probability of a single input wire of a majority element. If the randomizer rearranges the wires in a sufficiently random fashion the error probabilities of the three wires going into a single majority element will be independent. A detailed analysis of cases shows that 19

(5) Y < C + 32 For suitable c and C we will have y < 5, i.e., the probability of output error is less than the probability of an input error. An important use of the restoring organ is as part of the multiplexedand-restored nan organ (Fig. 13). This consists of a parallel array of nanelements followed by a restoring organ. Deterministically, the multiplexedand-restored nan organ performs the nan switching function on two input cables and then delays the output two units of time. Probabilistically it operates as follows. Let (Ca) (o2) be the probability that a wire of the (first) {second) input cable is in error at time t, and let c = Max (al, a2). We consider how the error probability P of the input to the restoring organ depends on a. There are two main cases to consider. First, the two input cables may come from the same source (i.e., the nan organ negates the input), in which case (6) 3 < e + c Second, the two input cables may come from separate sources; these will be either constant sources (e.g., all zeros) or other organs. In the former case the errors on wires of different cables are assumed to be independent; in the latter case the input cables came from restoring organs, so that the error probabilities a,, U2 for the two input cables operate independently. Considering the different possible input states we get 20

(7) B < C + a2 (for the zero-zero input state) (8) 5 < e + a (for zero-one or one-zero inputs) (9) f < E + 2a (for one-one input) Of the formulas (6) through (9) the last gives the greatest error. Combining (9) with (5) we have, for the multiplexed-and-restored nan organ, in the worst case, (10) y < E + 3(e+2c)2 So, for suitable E and a it is the case that y < K, i.e., the probability of an output error is less than the probability of an input error. A comparison of formulas (5) and (10) shows that the latter sets a bound on the output error probability of a single wire as a function of the input error probability, for any organ in a finite multiplexed automaton. Hence it is relevant to examine the effect of iterating formula (10) on itself, starting with the initial case of a = e. It turns out that for sufficiently small e the output error probability y is always bounded. For example, if c <.01 the output error probability of any multiplexed organ is bounded by 1.5E, and if c < e001 the output error probability is bounded by 1.03e. A full statistical analysis requires a consideration of the distribution of errors on the cables. There is not space for this here, but von Neumann L12] has done it for the (in general) worst case of a restoring organ composed of nan elements. Von Neumann considered only slow switches, and hence did not study nets with cycles. Since the randomizing networks are fixed throughout time and 21

are only pseudo-random, it is possible that higher-order errors will be amplified when signals go around cycles repeatedly. This problem needs investigation. To reduce such errors one can vary the structure of the randomizer from one part of the net to the other and one can also use more restoring organs than our design algorithms use. To see intuitively what happens we focus attention on a single finite multiplexed automaton and consider the effect of varying the multiplexing factor N or this automaton. Let 9 be the probability that the signal level in a given cable will fall inside the "nonsense" band A to (1-A). By increasing N indefinitely we can bring 9 arbitrarily close to zero. Since every finite multiplexed automaton contains a finite number of organs it follows that by increasing N indefinitely we can increase indefinitely the mean free path between errors in the automaton and hence increase indefinitely the reliability of the automaton. This increase in reliability is purchased, of course, at the cost of more equipment. For the cases he considered, von Neumann [12] found large multiplexing factors (e.g., 20,000) to be necessary, but two points should be noted in this connection. First, in order to treat an extreme case we have deliberately chosen a restoring primitive which requires large multiplexing factors for reasonable reliability. (Compare in this respect our choice of the slow primitives of Section 4.) There are restoring primitives which give much better results. For example, a generalized majority element with 2n+l inputs, whose output is active if and only if n+l or more inputs are active. As n increases 22

this becomes a better restoring primitive [13]. Second, the algorithms to be given next apply to arbitrary finite automata and for this reason will not give as good results as a procedure designed for a special class of automata (e.g., a computer organized into memories, arithmetic units, transmission lines, etc.). We will now adapt our earlier algorithms for slow automata (Section 4) to finite multiplexed automata. To begin with, look at the multiplexed organs determ inistically and in terms of operations on cables (rather than on single wires). Looked at this way the restoring organ is a unit delay and the multiplexed-and-restored nan organ is a nan-switch followed by two units of delay. There is also available the constant zero (i.e., a cable all of whose wires are inactive). From these logical elements we can synthesize all the slow primitives of Fig. 5, with the cables of the multiplexed automaton doing the job performed by the wires of the slow automaton. In this manner we obtain two more algorithms. When given a finite idealized automaton Ai and a desired mean free path between errors r, our third algorithm designs a finite multiplexed automaton Am with these properties: deterministically Am is computationally equivalent to Ai, probabilistically the mean free path between errors in Am is r. When given a finite idealized automaton Ai whose read control output is ultimately periodic and a desired mean free path between errors r, our fourth algorithm designs a multiplexed automaton Am* with these properties: deterministically Am* produces the same computation as Ai and at the same rate (after an initial delay), probabilistically the mean free path between errors in Am* is r. 23

It is of interest to compare Ai, Am, and Am*, since deterministically they are all computaticnally equal. Am has many more primitive elements than Ai and cromputes more slowly than Ai, but probabilistically it is more reliable than Ai. Here reliability is bought at the cost of speed and equipment. Am* is even larger than Am, but computes at the same rate as Ai. Here reliability is bought at the cost of equipment (and a fixed initial delay). As in the case of slow automata, it is desirable to have some general theorems governing interchanges of speed, equipment, and reliability of the kind just illustrated. 6~ Cellular Automata Slow automata (Section 4) take account of the time required for switching and the limit on the number of wires that a single component can drive. In actual computers there are also limits on the length of wires and there are design problems which arise in connection with the geometrical arrangement of components. These factors are partially taken account of on a theoretical level by means of cellular automata. A cellular automaton is a finite or infinite array of cells, each cell containing a finite automaton which is connected to certain "neighbors." The infinite shift register (tape) of a Turing machine (Sections 2, 4) is a one-dimensional infinite cellular automaton. In an unfinished manuscript von Neumann [14 developed an infinite twodimensional cellular model with square cells. Each cell is occupied by the 24

same 29 state finite automaton There is a fiducial initial state U. Initially all but a finite number of cells must be in this state. which communicates directly with its four immediate neighbors with a delay of one unit or more. Though von Neumann did not finish the construction, he carried it far enough to show that both a Universal Turing machine and a selfreproducing automaton can be embedded in this model. One can also study finite cellular automata by considering some finite set of cells and taking the inputs and outputs from along the edges. The problems of Section 4 ("Slow Automata") and, if probability is introduced, of Section 5 ("Probabilistic Automata") then arise. There is time to mention only one result here. There is an algorithm, analogous to our first algorithm, which does the following: given a finite idealized automaton Ai, this algorithm produces a finite von Neumann cellular automaton AC which is computationally equivalent to Ai [15]. 25

References [1] Turingg A.M. "On Computable Numbers, with an Application to the Entscheaoidunrgsproblenm." Proceedings of the London Mathematical Society Series 2, 42 (1936) 230-265 and 43 (1937) 544-546. [2 ] Moore, E. F.'Gedanken-Experiments on Sequential Machines. " Pp. 129153 of Automa-a Studies edited by C, E. Shannon and J. McCarthy), Princeton University Press, 1956. [3 Burks, Ao W. and -ao Wang. "The Logic of Automata." Journal of the Association for Computing Machinery 4 (April, 19.57) 193-218) and 4 (July, 1957) 279-297. [4] Burks, A, W. "Computation, Behavior, and Structure in Fixed and Growing Automata.'" Pp. 282311 of SelfOrgaranizing Systems (edited by Marshall Yovits and Scott Cameron) s Pergamon Press, New York, 1960. [5] Yamada, Ho "A Mode of Real Time Operations of a Subclass of Turing Machines and the ExisJtence of a S-inclass of Recursive Functions Which are not Real Time Computable," to appear in Transactions of IRE, EC. [6 ] McNaughton, Robert. "Ihe Theory of Automata, a Survey." to appear in Advances in Computers, Vole II (edited by Franz -L, Alt), Academic Press, [7] Friedman, Joyce.'"Some Results in Church, s Restricted Recursive Arithmetic." Journal of Symbolic Logic 22 (Dec., 1957) 337-342. [8] Friedman, Joyce, "A Decision Procedure for Computations of Finite Automata." Unp-ublished manuscript. [9 Burks, A. W. and Jesse B, Wright~. Seco. 4,1 of "Sequence Generators and Digital Computers," to be published in the Proceedings of the Symposium on Recursive Function Theory (April, 1961, N.Y.C.). [10] McNaughton, Robert. "On Nets Made up of Badly Timed Elements. Part I: Slow But Perfectly Timed Elements.'" Mimeographed, 30 pages. The Moore School of Electrical Engineering, IUniversity of Pennsylvania, 1961. [11] Shannon, Cla-ude E. "A Mathematical Theory of Communication." The Bell System Technircal Journal 27 (1948) 379-423 and 623-656. 26

[12] Von Neumann, John. "Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components." Pp. 43-98 of Automata Studies, op. cit. [13] Verbeek, L.A.M. "On Error Minimizing Neural Nets." Pp 121-123 of Principles of Self-Organization (edited by H. von Foerster and G. W. Zopf) Pergamon Press, New York, 1962. [14] Von Neumann, John. "The Theory of Automata: Construction, Reproduction, Homogeneity." To be published by the University of Illinois Press under the editorship of the present writer. [15] Burks, A. W. "Cellular Automata." To be published in the Proceedings of the International Symposium on Theory of Relay Systems and Finite Automata held in Moscow, Sept. 24-Oct. 2, 1962. 27

Nan Switch Do Unit Delays Initially Zero -4 -K Initially One -I o Fig. 1. Idealized primitives. Tape C__ R - Symbol Read Control Fig. 2. Input tape reader.

Tape Symbol Write Control Fig. 3. Output tape writer. R C I Automaton W Fig. 4. Computation of an automaton. 29

r!! on Fig. 5. Slow primitives. Switch Fig. 6. Normal form net. 3o

Output with In put Probability State I- 00 1 0 0 1 I 0 1I0 I1 0 I I 0 I Fig. 7. Probabilistic nan. ( z ) —0 Fig. 8. Slow probabilistic primitives.

Output Fig. 9. Probabilistic automaton. State I |State Ze(o One Fig. 10. Deterministic state diagram. S tate s State Z-ezero _ - One I- E Fig. 11. Probabilistic state diagram.

Fig. 12. Restoring organ- multiplexing factor N = 3. Restoring Organ Fig. 13. Multiplexed-and-restored nan organ-multiplexing factor N = 3. 33

I

NERVE-NET SIMULATION J. Willison Crichton Marion R. Finley

p

This quarter was devoted to completing the adaptation of the nerve net program to The University of Michigan Computing Center's IBM 709 (and later, IBM 7090) system. The program had been written originally in the SCAT language for The University of Michigan Willow Run Laboratories IBM 709 system and debugged to the point where some vital changes in the underlying statistical analysis were found to be necessary and some experiments on sustained activity were carried out with positive results. From the time of the transfer of the IBM 709 from the Willow Run Laboratories to the Computing Center until August 1962, the main efforts were directed towards adapting the program to the University of Michigan system. The authors were forced to write their own assembly program, called SCALP, which is specially adapted to the needs of the simulation program, and yet operates within the procedures of The University of Michigan Computing Center's system. After converting the simulation program to SCALP, success was immediately obtained in debugging the inputoutput and tape handling routines and simultaneously runs on the three-neuron correlation experiment and a "shake-down" test of the central net program were begun. There was a gap in computer operation from August 28 until September 24 during which period the Computing Center was closed to replace the IBM 709 with the IBM 7090. This period was used by the authors to do additional preparation for future runs. After installation of the IBM 7090 was completed (which caused only minor changes in the simulation program), the runs above were continued. In early October, a complete interpretive trace routine with a monitoring option was written and debugged to allow detailed examination of 37

the net program as an aid in tracking down the surce of any anomalous behavior. The writing and cdebug:irng of t'he SCALP ronutine mentioned abcre took place in July- and August, A write- ur cn SCATP is availab-e (Sc-ALTP-;Symbol ic Cornpressed Assembl.y ard Loading Program by the same authors); a brief description fol Liows: The SCALP ss-ptem perf orms a minimal as-emb-ly and loading fulnction. It does not produce a rnew deck of cards o54 any kind., It does not possess any powerful translation f:eatures such as macro translation, It does not produce the kind of detailed.isting produced by the SOS assembler of The University of Michigan assembl y program (!JViAP) It does not make automatic provision for multiple core-load programs. Hrowever for those whio are obliged to write rather corpnl'.ex programs in machine language, it does possess the following advantageous fteatures I t Cis simple to'earn and has few pitfall s (2) t performs a very:fast a(ssembly relative to more e laborate systems, ) It a l lows the writing of several instructions per card) thus peTrmitting a long program to be contained in a rather small. symbolic: deck, (4) It does not require a strict card format, in the sense that ceta.in things must be pu-_nched in certain col-hurmns Thle iformat requiY-ement: are contextual rather than absolute. (5) it p:rovides optional linkage with The University of MlHichigan Executive System and I-O Supervisor., (6) It; provideIs for -t.. n....unc sion of reljocatable binary subroutine s The aim of' SCALP is to make it con/ vrenient and al.so feasi ble from the standpoint of machline time, to use the original syrmbolic deck as the permanent form in whlich a program is hand.led,

PERSONNEL The following is a summary of the hours worked under this contract for the period 15 July to 15 October 1962. A. W. Burks 205 J. H. Holland 368 J. W. Crichton 336 M. R. Finley 496 J. W. Thatcher 96 R. A. Laing 96 Total man hours 1597 39

OBJECTIVES FOR NEXT QUARTERLY PERIOD The research in environmental regularities (opportunities for the adaptive system to depart from random or enumerative behavior) which was begun in this last quarter, will be continued. This research topic will be developed in detail for the more particular "tree-search" case (an environment, specified by a tree with assigned utilities, which also includes games, search procedures, etc.). Specific theorems relating the limiting adaptive efficiency to the regularities present will be the longer range goal, with the immediate objective being to establish the maximum possible rate of adaptation when the utilities are assigned to the tree at random (the "absence of regularities" case). (Holland). In the nerve-net simulation experiments, the next quarterly period will be devoted to completion of the debugging of the main program, and initiating the planned series of experiments. A simple macro-instruction feature will be incorporated into the SCALP system, with a view to reducing the rate of errors in the programming of experiments (Finley and Crichton).

DISTRIBUTION LIST (One copy unless otherwise noted) OASD (R&E), Room 3E1065 Director The Pentagon U.S. Naval Research Laboratory Washington 25, D.C. Washington 25, D.C. Attn: Technical Library Attn, Code 2027 Chief, Research and Development Commanding Officer and Director OCS, Department of the Army U.S. Navryi Electronics Laboratory Washington 25, D.C. San Diego 52, California Commanding General Aeronautical Systems Division U. S. Army Materiel Command Wright-Patterson Air Force Base, Ohio Washington 25, D C. Attn: ASAPRL Attn: R&D Directorate Air Force Cambridge Research Commanding General Laboratories U. S. Army Electronics Command L. G. Hanscom Field Fort Monmouth, N.J. Bedford, Massachusetts Attn: AMSEL-AD Attn. CRZC Attno CRXL-R Commander 10 ASTIA Hq., Electronic Systems Division Arlington Hall Station L. G. Hanscom Field Arlington 12, Virginia Bedford) Massachusetts Attn: TIPCR Attn- ESAT Commanding General APSC Scientific/Technical Liaison USA Combat Developments Command Office Fort Belvoir, Virginia U.S, Naval Air Development Center Attn: CDCMR-E Johnsville, Pennsylvania Commanding Officer Commanding Officer USA Communication and Electronics UoS. Army Electronics Materiel Combat Development Agency Support Agency Fort Huachuca, Arizona Fort Mormnouth, New Jersey Attn: SELMS-ADJ Chief, UoS. Army Security Agency 2 Arlington Hall Station Director, Fort Monmouth Office Arlington 12, Virginia USA Communication and Electronics Combat Development Agency Deputy President Fort Monmouth, New Jersey U.S. Army Security Agency Board Arlington Hall Station Arlington 12, Virginia

DISTRIBUTION LIST (Concluded) Corps of Engineers Liaison Office Professor Heinz Von Foerster U.S. Army Electronics Research 215 Electrical Engineering Research and Development Laboratory Laboratory Fort Monmouth, New i.ersey University of Illinois Urbana, Illinois Marine Corps Liaison Office U.S. Army Electronics Research Dr. Saul Amarel and Development Laboratory RCA Laboratories Fort Monmouth, New Jersey Princeton, New Jersey Commanding Officer IBM Research Laboratory U.S, Army Electronics Research Bethesda, Maryland and Development Laboratory Attn: Dr. A. Babbitt Fort Monmouth, New jersey Attn: Logistics Laboratory Sterling Perkes Attn: Director, Research/Engineering Department of Electrical Engineering Attn: Technical Documents Center University of Utah Attn: SELRA/SL-NPE 4 Salt Lake City, Utah Attn: Technical Information Div. 3 Attn: Mr. Anthony V. Campi 14 Commanding General U.S. Army Materiel Command Washington 25, D.C. Attn: R&D Directorate Research Division Electronics Branch

UNIVERSITY OF MICHIGAN 3 9015 02082 78231111 3 9015 02082 7823