THE UNIVERS ITY OF M I C H IGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department Technical Report ASEXUAL AND SEXUAL REPRODUCTION EXPRESSED IN THE VON NEUMANN CELLULAR SYSTEM (FORMALISMS FOR LIVING SYSTEMS (PART I) SECTIONS 9.2, 9.3, AND 9.4) Richard A. Laing with assistance from: Department of Health, Education, and Welfare National Institutes of Health Grant No. GM-12236 Bethesda, Maryland and National Science Foundation Grant No. GJ-519 Washington, D.C. administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR January 1970 Distribution of This Document is Unlimited

ABSTRACT This paper continues the investigation of automaton formalisms for representing biological phenomena which was initiated in Formalisms for Living Systems (Part I). (The present paper consists of continuation sections 9.2, 9.3 and 9.4 of that report.) A brief discussion of the suitability of the von Neumann cellular system for representing reproduction by fission of plastic cells, fission of rigid cells, budding-off of new cells, cell fragmentation, and filamentous growth of new cells, is presented. A procedure analogous to cell sexual reproduction, by which genetic variation can be generated in an automaton model of biological cells, is given. Some comments on ways of achieving indefinite variation employing only finite means are also given.

9.2 Asexual Reproduction in the von Neumann System The specific form reproduction takes may or may not be critical for explanations of growth and development; certainly at some level the precise form reproduction takes is important to what one is studying, while for other levels, all that may be necessary is that where once there was one cell there are now two, the precise nature of the intermediate stages having no particular significance. There are many forms of cell reproduction which have been distinguished; five of them are: 1) fission of a "plastic" cell. This is the (commonly described) process by which the parent cell increases its size and then separates into two or more complete offspring by a process of duplicating the nuclear material and "dividing up" the cytoplasmic material by a constriction of the parent cell, and a pulling apart of the offspring cells. 2) fission of rigid ceZZs, in which the cell wall material is less plastic and the shape of the cell consequently more fixed. In this form (characteristic of plants in particular) the parent cell elongates and a cross wall is formed, producing two offspring cells. Important features here are the considerable rigidity of cell shape, of relative position, and of general motility. 3) budding off of cells, in which the parent cell produces a "blister" at its surface which expands to the size of the parent, acquires a full complement of intra-cellular equipage and may then separate off entirely. Sometimes complete separation does not occur, and a whole chain of cells can be produced. 4) fragmentation, in which the parent cell nucleus divides into numerous complete offspring nuclei, appropriate cytoplasm coalesces about each new nucleus, walls are formed about these new cells, and the offspring cells disperse. 5) filamentous growth, which occurs in fibers, and only at the tip of the fiber. The tip elongates, a cross wall is erected to form a

new final cell with a growing tip, and the process repeats. The growing tip can split, so that branching may occur. Let us now consider whether the above cell reproduction processes can be represented in automaton systems, especially in the von Neumann cellular system. 9.2.1 Plastic Cell Fission The most familiar cell reproduction process is that of fission of plastic cells. This process is representable in the von Neumann cellular automaton system but only with difficulty, and with considerable loss of "naturalness". Fission of plastic cells involves an increase in cell material, which would be mirrored as an increase in the size of that part of the surface of the VNCS which is not inactive environment and which we interpret as being the Cell (the automaton system contains both cell and environment). In a gross sense, this increase in cell size could be achieved; a subroutine which generates size increases could readily be added to the tape of the von Neumann cell machine, or could be carried as a fixed subroutine inside the cell proper (as opposed to coding it on the "genetic" tape along with the other duplication instructions). In any case, mere increase in size is, for a single VNCS cell complex no problem. What should be pointed out though is that increase in size in this sense is quite gratuitous, where in the biological cell case the increase has a function: a sufficient complement of cell materials must be available for both of the two offspring cells. If increase in size enters into morphogenesis only in this "external" manner then the VNCS is theoretically capable of mirroring the process. [The "puffing up" of a cell in this fashion in the VNCS, is essentially "fake", like a false pregnancy, the baby arriving from elsewhere, and being "smuggled" into the construction site.]

In plastic cell fission; the nuclear materials must be duplicated and separated in distinct cell regions preparatory to physical splitting. In the VNCS, the nuclear "genetic" materials can be duplicated and available to all successor cells. That is, the function at least of duplicating and transmitting the genetic inheritance to offspring cells can be carried out. After plastic cell fission has taken place it is assumed that the daughter cells are free to wander, governed less by any ironclad internal program, than by the more general "rules" of a cell interaction with its environment. In the "usual" VNCS reproduction process, the successor cells end up permanently in a fixed relative position. In addition, variation in shape (such as is found in plastic-cells) is not part of the "standard" process. Movement and variation in shapes can be "programmed" into VNCS system, but it must be said, only at the cost of a great deal of "unnaturalness." One final remark must be made: the VNCS has so far been presented as being limited to operating in a two dimensional rectangular array. It could of course be given larger dimensionality; in addition the unit cells need not be rectangular: any of several regular patterns would serve (with varying degrees of ease). If in a study of morphogenesis it is necessary to mirror precisely the position and relationship of organism units, then any particular VNCS may produce a distortion or loss of the pertinent spatial properties. As far as plastic cell fission goes, the general conclusion to be reached is, I believe, that the VNCS system is very poorly designed to mirror such cell movement and change of shape. It is not impossible for the system, just messy and counter-intuitive. It is, of course, in part a matter of the point of view taken, the interpretive level assumed. In counteracting the above "dismissal" of the VNCS as a useful vehicle for the study of plastic cell fission we might mention that 1) a system such as the VNCS might be useful for studies of plastic

cell fission if one were to employ the system at a finer level of interpretation, using the VNCS elements to represent the macro-molecular elements in the cell which bring about mitosis: the formation of spindle fibrils, the action of the centromere, etc. That is, using the VNCS to study particular "fine" features of cell division. 2) a system such as the VNCS could be employed at a much grosser LeveZ of interpretation (relative to specifics of the reproduction of individual cells), using it to study position and movement of plastic cells; in this usage a cell of the space might be "on" or in some specific state, to represent the presence of a cell of a certain kind or shape and in another state to represent the absence of a cell of a certain kind or shape; no attempt would be made to employ the geometry of the VNCS space to explain the finer details of how change of position or change of shape might be brought about. That is, under this system of representation and interpretation, the position of a real cell "maps" roughly to the position of a VNCS cell, and VNCS shape or size of real cell, maps to a state of VNCS cell (that is, maps "poorly" since the "image" in the VNCS system is not only considerably altered but is from the ordinary point of view "not even the same sort of thing"). What about the fission of rigid cells? How well can the VNCS handle this form of biological cellular reproduction? 9.2.2 Rigid Cell Fission In rigid cell fission, the parent cell increases in size (often principally in length) and a rigid cross wall is formed to yield a pair of separated successor cells. The rigid "geometric" features of this form of cell fission would appear to make it more amenable to "natural" representation in the VNCS. A fairly good (and natural) image of the arrangements of rigid cells in a regular order (as is found in woody plants) can be formed in a VNCS. There is a serious

difficulty however if one wishes to study the growth and development of such cell systems; the static completed image of the cell structure is easily expressed in the VNCS; the successive images of the cell structure as it develops are not at all easily and naturally expressed (in the naive and direct "geometrically isomorphic" sense). The problem is that in the case of real rigid cells the formation of a new cell by the growth and fission of an already existing cell, in effect causes new cells to arise among already existing cells. The already existing cells are thus to some extent forced to accomodate to this expansion in their midst by shufflings and re-alignments. The positions of the growth points and the consequent re-positionings of cells constitute of course an important factor in determining the ultimate form of the multicellular organism. Some of the effect of these internal expansions and consequent re-alignments of cells and blocks of cells, must be mirrored in the rigid geometric framework of the VNCS: the intellectual "overhead" attendant on keeping all this straight may lead to a complete "fuzzing-up" of what is happening. The system of representation has to carry such a burden of nonessential activity that detecting what is of consequence for understanding development may easily be lost. If one were to represent repeated rigid cell fission in a VNCS one would spend by far the largest amount of effort in moving pre-existing cells about, to accomodate the new ones. All this movement, shifting, re-alignment etc. may provide important clues to understanding development; on the other hand it may be only a monstrous and irrelevant if not totally distorting burden. 9.2.3 Budding-off The budding-off of new cells, appears, on the surface at least, to most resemble VNCS "standard" self-duplication. That is, in both budding-off and

VNCS self-duplication as presented by von Neumann, the parent cell retains its integrity as it gradually, piece-meal produces the offspring. Unlike plastic and rigid cell fission, there is (on the surface at least) an observable and identifiable parent, and an observable and identifiable offspring cell. The offspring cell can completely separate, or can remain connected to the parent while the offspring itself may produce offspring, yielding a chain of offspring. All this is representable in the VNCS in an easy straight forward manner. What is not so easily represented is (as we have seen with other "plastic" cells) is the shape and the movement-migration of the cells. Again, though these things are theoretically representable in the VNCS, the effort required and the distortion inherent in this should be taken into account. 9.2.4 Fragmentation Production of new cells by fragmentation is, on the face of it (and actually) quite unlike the standard VNCS self-duplication. The new cells are formed within the parent cell, multiple copies are made at the same time, spatial location of the construction site is not rigid, and the identity of the parent cell is lost in the reproduction process, and the offspring cells disperse freely to take up further growth at indeterminate sites. Despite all the differences, the process could be mimiced in a VNCS, albeit with great difficulty and artificiality. In effect, though it can be employed, the VNCS does not seem to provide a very appropriate vehicle for studying morphogenesis of any real cell system in which close conformity to a fragmentation reproduction system is required. On the other hand, if one merely wishes to study the growth and dispersal features of this form of reproduction, the VNCS or some similar tesellation system might be quite useful.

9.2.5 Filamentous Growth Superficially, filamentous growth does not appear much like the VNCS reproduction. In fact, however, it is probably the system of natural cell reproduction most susceptible to adequate informative and natural rppresentation in the VNCS. In filamentous growth, new cells are formed only at the tip of an already formed filament. The tip elongates, and a cross-wall is formed; this yields a new cell with a growing tip. It will be thus seen that the problem of moving a whole cell or a whole block of cells to a new location does not occur, the spatial relations between old cells and new growth remain stable. A new cell is normally always created in an "unorganized" region, i.e. one in which there is no obstruction, such as another cell. The parent cell is always "turned off"' after growth occurs, so that there is no problem of moving or displacing a cell to make room for a sister cell. There is one related problem however. The problem lies in the possibility of splitting. In filamentous growth systems, a single cell can possibly give rise to two offspring cells, each offspring possessing a growth tip. Thus, the system can branch. A modelling problem occurs when the number of branches from a single basal cell exceeds the dimensionality constraints of the natural spatial geometry of any rigid cellular automaton system being employed. The "standard" VNCS is two-dimensional. This means that in this particular VNCS a single tip cell can give rise to at most three branches before "strain" is placed on the representational system. Additional dimensions may be represented in other VNCS, and one need not adhere to a system of rectangular coordinates and rectangular underlying cell-automata. If, however, unlimited branching is to be permitted then sooner or later difficulties are going to arise either because of excessive numbers of branches arising from a single cell, or from crowding in the sub-branch system.

The very difficulties may however be an important part of what is being studied; one may wish the system to modify its growth behavior under the pressure of conflict and crowding of branches. This suggests that some useful study of filamentous growth systems might be carried out using the VNCS, where either there is good reason to limit branching, or where the threat of crowding and conflict is believed to be important in determining the eventual form of the filamentous organism. It should also be remarked that the cell-tag system discussed earlier in Formalisms I readily permits the modelling of filamentous growth systems. In this system there are no pre-existing environmental or spatial constraints; indefinite basal cell branching as well as consequent proliferation of subbranches could occur. Therefore, in the cell-tag automaton system, from one point of view the crowding and branching problems do not arise, while from another, the problems are not intractable because they cannot even be expressed in the automaton system.

9.3 Sexual Reproduction in the von Neumann System We have so far discussed only analogues of asexual cell reproduction in the von Neumann system. In these analogues of reproduction, the offspring cell is supplied with genetic material identical to that of the parent. [We have briefly touched (in section 9.1.1 Non-Standard Duplications) some of the variants of standard asexual cell reproduction in the VNCS. The variation in genetic material which is introduced by the procedures described there is very transitory. In 9.4 we will briefly comment on some less transitory variation proceduresJ. In order to carry out studies of adaptation and evolution it may be necessary to introduce some additional techniques by which genetic variability is promoted and sustained. Sexual reproduction provides enlarged opportunities for genetic "re-shuffling". For this it will be useful to consider whether an analogue of sexual reproduction can be obtained in the von Neumann system. (Consideration of adaptation and evolution will also force us to discuss populations of cells, and motility of cells.) To recall: In "standard" VNCS reproduction, the (asexual) cell-machine consists of a constructing unit and a tape. The tape carries two copies of instructions for the construction of an offspring cell-machine. The constructor unit acts upon one set of these instructions (possibly altering or destroying the tape contents in the process) and after the completion of the offspring construction unit, the parent constructor twice copies the remaining unaltered copy of the construction instructions onto the offspring's tape. The parent then "turns the offspring on" and separates from it. The offspring cell-machine is programmed to reproduce in turn. We now introduce the concept of a "female" cell-machine and a "male" cell-machine. The female cell will closely resemble the "standard" selfreproducing cell. We make however the following modifications: 1) construction

activity on the part of the female constructor cell will not take place unless a particular point on the cell surface (just above the terminus of the female cell's tape) is appropriately stimulated, 2) the tape itself will be somewhat longer in order to accommodate the following additional features: a) the contents of the tape square closest to the constructor unit will assist in determining the "sex" of the offspring cell, b) the separate "genes" (or "cistrons" or sub-functions) along the tape specifying the way in which particular construction routines or phases will be carried out will be separated by certain special "punctuation" or "spacing" squares (or sequences of squares) of the tape. The "male" cell machine will consist entirely of genetic tape constructions composed similarly to the genetic tape instructions of the female cell (with a possible difference in the initial, or sex-determining tape square). [Actually there is a great deal of latitude in assigning the sex determining features. We could for example assign the sex determination to the male cell entirely, rather than have the female cell take part in the choice. One way to leave the matter to the male cell would be to have the initial tape square (or segment) be either male or female determining, or to have both possibilities present but a random choice made by the constructor, etc.] See Figure 9.3a

Female Construction Unit Male "cell" Conception - initiation cell copy 1 copy 2 We M F Female tape unit — copy 1 copy Conjoined Male and Female Cells Figure 9.3a

Upon being stimulated (the male genetic tape being in place) the female cell will begin its construction routine. "Chance" behavior may enter at several points. [The sources of this "chance" behavior can be various. In "real" systems the physical workings of the organism and its environment will provide the chance behavior (though from a sufficiently "cosmic" point of view even this will be determined). In our system we could introduce randomness from completely outside directly to the cell, or the randomness could be "fed" to the environment, and thence to the cell, or we could design some "sufficiently" pseudo-random device for the cell itself.] First, the female cell may "randomly" choose to read either the F or the M tape square. If the female cell reads the F square, then the cell will produce a female cell (that is, a cell complete with construction unit). If however the female cell reads the M square, then the cell will produce a male cell (that is, a cell consisting entirely of genetic instructions ). Once the sex determining square has been read and the basic male or female construction routine thus determined, the female-mother cell will proceed to read down the tape, acting upon the tape instructions, or merely copying them, according to the basic female or male sex distinction of the offspring. In reading (and copying or constructing), the parent cell is free, at any point between "genes" to jump to the genetic information of the opposite tape. It is this feature which is intended to permit the propagation of genetic variability throughout the cell population. (See Figure 9.3b)

[The initial genetic differences in the population must be established either from the outside by the' experimenter, or from inside the automaton system by some internal analogue of "mutation". So also for the "chance" switching from reading one tape to reading the other: This choice, as in the sex determining action, must be introduced from outside the system or modelled within it.] "Mother" constructor Cell Cross-over regions - LI I LF] I I.. IF| Copy 1 Read Path Genetic Variation by Crossover Reading Figure 9.3b

As this sexual cell reproduction system has been described here, note that some "unnatural" genetic mixings are possible. Male cell production can consist of duplicating the identical information for both tape copies (which is "natural", the "soma" construction-instruction segment and the permanent genetic segment of the tape will have the "same" message) or the copies in the construction segment and permanent genetic segment could be different (which is not customary). The female cells produced could have a form which is not that expressed in the permanent genetic tape segment. On the other hand, the liberality of reading, acting, and transcribing could be constrained to produce closer analogues of the usual biological case, where differences of phenotype are a consequence of interaction with the "accidents" of the environment. The picture we have presented reduces the role of cells to their sexual and reproductive features. The female cells are the only cells which "do" anything, and what they do is make more cells. There is no reason why we can not add features to both male and female cells, features which only indirectly (but not to say unimportantly) have anything to do with sex and reproduction. Indeed, to "make the system work", we must provide some analogue to motility for the male cells. This again could be handled by means outside the automaton system (by experimenter assignment, or by an outside random selector process) or simulated within the automaton system (although as we have frequently mentioned, direct representation of movement of a VNCS cell-machine can be extremely awkward). [To elaborate on this point once more: movement in a VNCS is represented, not directly by movement itself, but by dissolution of entities in one place and reconstitution in another place. This means that if one "stares steadily" at a VNCS while the movement action is taking place, one will get "the wrong picture". To get "the right picture" the observer sort

of has to "blink" or peep at the right intervals or "avert the gaze for a moment". ] In order to carry out any sort of adaptation or evolution studies, we must introduce whole populations of cells. Also, in addition to motility for male cells we should probably also provide the cells with further properties allowing the cells to interact with each other and with their environment.

9.4 Indefinite Genetic Variability In Section 9.3 (as well as in 9.1) we discussed ways in which variation of genetic inheritance can be achieved in automaton cell systems. How can the soma and the genetic componenet of the offspring be made to differ from the parent? How long can genetic differences between offspring and parent be made to propagate? How can analogues of sexual reproduction be employed to induce further variation? In most of the discussions of these problems we have tried to suggest the employment of mechanisms which are quite biological-like. At this point, it may be worthwhile to some rather different methods by which variation can be attained; these methods are mathematically more sophisticated but biologically less "natural" than the methods so far mentioned. In particular, we should like briefly to discuss whether indefinitely propagable differences between parent and offspring can be obtained employing a single initial finite specification. [In the more biological-like methods the variation possible, though often very large, is usually finite.] M. Arbib has noted (informal observation) that in the VNCS there is an extremely simple way to get indefinitely persisting differences between parent and offspring. In VNCS self-reproduction two genetic tapes are employed; one tape is used in the construction of the offspring soma, and one tape is copied twice and inserted. in the offspring as its "genetic inheritance". Suppose we give the parent-constructor machine a regular construction routine which says that an "add a single new cell" instruction is to be made part of the offspring genetic tape. (The instruction can be arranged to so specify the location of this cell so that it does not inter

fere with any "regular" growth or construction process.) The effect of this is that each successive parent machine produces a copy of itself but then adds one extra cell; in addition the genetic inheritance of the offspring calls for yet another "extra cell", etc. Offspring and parent will differ by one cell and the difference (albeit superficial) will persist indefinitely. In this method of attaining indefinite parent-offspring difference, we have concentrated on producing an indefinite variation which does not perturb our general scheme of automaton construction. Thus although the condition of indefinite difference is met, the consequences are purposely held carefully in check. Is there a method of introducing less trivial indefinite variation? Is there a method of insuring that each offspring possesses capabilities beyond those of the parent? Such a method was one of von Neumann's objectives. He asked "... can the construction of automata by automata progress from simpler types to increasingly complicated types? Also, assuming some suitable definition of'efficiency', can this evolution go from less efficient to more efficient automata?" John Myhill has attacked this problem and has provided one possible method. Myhill makes use of that well-known results of K. Godel that any formal system capable of expressing elementary number theory is incomplete: there are truths expressible in the system, which are however not provable (not theorems) in the system (for a system in which no falsehoods are provable). For each such incomplete formal system one can effectively construct another formal system in which all of the previously provable truths remain provable and in addition at least one previously non-provable truth can now be proved. Thus an indefinite chain of formal systems can be obtained, each having more provable truths than its parent system.

Now the axioms and rules of inference of any formal system can be represented by a Turing machine. In addition, both the new formal systems (whose theorems consist of not only old provable truths but some previously unprovable truths) and the procedure by which the new system is obtained from the old can be represented by Turing machines. Since a cellular automaton system (such as the VNCS) can express any Turing machine computations the total procedure outlined above can be expressed in a cellular automaton system. Thus a cellular machine can be designed embodying a formal system and a constructing system; this composite machine can construct offspring consisting of a constructing system and an improved formal system capable of proving everything provable by its parent plus at least one truth not provable by its parents. (Each machine-child is cleverer than its parent, in particular because it can resolve its parent's self-reference paradox hang-up.) Although the use of words like "truth" and "provable" focuses attention on application of the above procedure to theoretical problems of artificial intelligence (indeed this was Myhill's intention) Myhill is also clearly aware of the application to biology and says it "suggests the possibility of encoding a potentially infinite number of directions to posterity on a finitely long chromosomal tape...". If we shift Myhill's own vocabulary, we can perhaps make the biological application more apparent: the additional distinction between "truth and falsity" each child-machine can make as it encounters the problems posed by its environment may permit machines to make wiser choices (or fewer stupid choices) in competition for resources with other possibly stupider but less encumbered machines. A major problem then, is determining the efficiency of such a scheme for increasing "biological" problem-solving capability.

[John Holland has devoted considerable attention to this crucial problem.]

BI BL IOGRAPHY Holland, John, Hierarchical Descriptions, Universal Spaces and Adaptive Systems, University of Michigan Technical Report, August 1968 Laing, R., Formalisms for Living Systems (Part I), University of Michigan Technical Report, January 1969,Myhill, John, "The Abstract Theory of Self-Reproduction" (Chapter 7 of Views on General Systems Theory (edited by M. D. Mesarovic) J. Wiley, 1964) von Neumann, J., Theory of Self-Reproducing Automata (edited by A. W. Burks), University of Illinois Press, 1966

DOCUK.T COROL DATA. R I D-:(secsw~qr rI~aalfte.~de, oi eNt bodyr tt~h~l ehtMwd Dting~i~ anntaM841on Mrns b10 entered when the oora1~ ). ni eti I. IVINA tNS ACtOyST_ orp a.. REPORT ISECURIT CL. A IrIC A TI ON LOGIC OF COMPUTERS GROUP Unclassified The University of Michigan a-b. rOtou Ann Arbor, Michigan ASEXUAL AND SEXUAL REPRODUCTION EXPRESSED IN THE VON NEUMANN CELLULAR SYSTEM (FORMULISMS FOR LIVING SYSTEMS (PART I) SECTIONS 9.2, 9.3 AND 9.4) 4. DoSCtIPtIbtio' O.ttf (te 1 ept and o ncumetlve dited) Technical Report S.- AU t16401SI (Fot# t mee, pliddte Itiftit goal "ame) Richard A. Laing _. REPORT DAT_ 7r. TOTAL NO. OF PAES -lb. NO. PO REFS January 1970 25 4 n. czftNrACT Or GRANT NO. On. ORIGINATOR" REPORT NUMBERIS) GM- 12236 b. PROJECt NO. C. 9b. OtHER REPORT NOIS) (Any other number. that may be assigned thi treport) d.10. OStrITUTION STATMEtNt Distribution of This Document is Unlimited it. SUPPLEMEWTARV NOTES 12. SPONSORING MILITARY ACTIVITY 1.. ABSTRACT This paper continues the investigation of automaton formalisms for representing biological phenomena which was initiated in Formalisms for Living Systems (Part I). (The present paper consists of continuation sections 9.2, 9.3 and 9.4 of that report.) A brief discussion of the suitability of the von Neumann cellular system for representing reproduction by fission of plastic cells, fission of rigid cells, budding-off of new cells, cell fragmentation, and filamentous growth of new cells, is presented. A procedure analogous to cell sexual reproduction, by which genetic variation can be generated in an automaton model of biological cells, is given. Some comments on ways of achieving indefinite variation employing only finite means are also given. DD F",ORM 1473 UNcS__ _ _ _ _ _

UNCLASSIFIED.C.. Security Clastio icaton__ 14. LINK A LINK, Is LINK- C VEY WORDS - - - ROL., W'T ROLE WT',Ocro. WT UNCLASSIF IED sucurity Cluswiticutlir