cgl@t13.lanl.GOV (Chris Langton) (02/04/91)
In article <1991Jan21.190759.3684@midway.uchicago.edu> kawl@quads.uchicago.edu (david john kawliche) writes: | | I have recently written a program (in LSC 4.0, for the mac) |that allows two 'teams' of cellular automata to be grown in the same |medium. The interactions between cells of the same type can be set |and so can the interactions between cells of differing types. I have |gotten some very interseting results in the first few passes at this sort |of simulation and believe that the possiblity for warring, symbiotic, |segragationalist and other general behaviors are possible. I am interested |in knowing if anyone has done this before, and if there is interest in |such a program. From the earliest days of CA research, there have been many CA rules and systems studied which give rise to such life-like behavior, which is one of the reasons CA have played a large role in the field of Artificial Life. The earliest work, of course, goes back to von Neumann and Ulam. Von Neumann discusses this possibility in The Theory of Self-Reproducing Automata, Ed. A.W. Burks (1966). There are several articles by Stan Ulam on competition between CA patterns in Burks' collection: Essays on Cellular Automata (1970). Note that the distinction between competing patterns and competing rules is not a clean one, because different rules can be collected together in one larger rule, and different patterns can be seen as invoking different "subrules" of one CA rule. Systems which can be viewed as extensions to CA which involve a cleaner (but still not necessarliy complete) distinction between patterns and rules have been devised. John Holland had several articles in Burks' collection involving such systems. Richard Laing - a long-time member of Burks' Logic of Computers Group at U. Michigan - devised a system involving what he called Molecular Automata, which would interact with each other in the context of a "soup" of such machines, much like a beaker full of reactive enzymes and substrates. More recently, Lugowski and company at U. of Indiana have been developing a system they refer to as a Computational Metabolism, which is much like a CA in which the cells are no longer nailed-down to particular lattice positions and can migrate around the lattice, interacting with other cells under control of an internal state-transition function. These cells are much more complex than traditional CA cells - and are reminiscient of John Hollands iterative circuit computers, described in the articles mentioned above. A system involving Movable Finite Automata (MFA) has been developed by Narendra Goel and Richard Thompson and successfully applied to a number of biological problems, including the self-assembly of a T4-phage virus. In this sytem, the "cells" are also free to move about and have complex internal state machines, which are connected to "sensors" and "effectors" on the cell's surfaces. These sensors and effectors are fairly general purpose, but have been used to mimic molecular recognition and bonding sites. The MFA machines are typically driven about a 3-D volume by diffusion. Walter Fontanna and Steen Rasmussen at Los Alamos and Tom Ray at U. Deleware are developing what might be called "artificial-chemistries" or "computational chemistries", in which the reaction-logic of real chemistries is abstracted to a logic of interacting algorithms or pure lisp functions. Competition, selection, symbiotism, complex ecological dynamics, evolutionary progress, and much more are seen in such systems. With a team at UCLA, we are developing a system for the Connection Machine which we are calling a "process-gas" - an object oriented system in which a large collection of arbitrarily programmable processes move around within the space of processors, interacting with each other and with local environmental objects, which are also programmable. This system should be general enough to allow the investigation of the whole hierarchy of biological phenomena, from molecule-molecule interactions to evolving eco-systems. To date, it has been partially implemented by Rob Collins at UCLA, and applied to the study of ant-colony dynamics, in which up to a million or so "ants" (neural-net-driven objects) swarm around inside the CM2, interacting and competing with each other to collect "food" and return it to their nests. In general, many of these CA-extensions are well-suited to the study of biological phenomena because they all share an underlying architecture that captures the basic architecture of most biological phenomena: a huge number of semi-autonomous parts engaged in local interactions with one another according to their own individual behavioral repertoires in the context of a complex environment. All of this takes place *IN THE ABSENCE OF A CENTRAL CONTROLLER*! I.e., these systems are "bottom-up" as opposed to "top-down" - as are CA - and I argue (although many disagree) that they allow, in principle anyway, the actual synthesis of biological phenomena in computers, something which goes beyond mere simulation. A feature which distinguishes many of these systems from CA's is that the researcher specifies behavioral rules at the level of the "object", rather than at the level of the lattice. Although in principle CA with large state sets can be though of in this way, it is much easier to work from the perspective of the objects which interact in the system than it is to work from the perspective of the lattice in which the objects interact. For problems in which the study of the latter is important (such as reaction-difusion systems), CA are great. But having to work out the kinetics of moving objects covering many CA sites is quite a chore, and for the study of such things as ecosystem dynamics, the low-level physics of movement is irrelevant to the behavior of interest, and movement can be finessed in simpler ways, without affecting the behaviors that the researcher is interested in studying. I would be interested in seeing discussions of such CA-extensions in this group in addition to discussions of CA themselves. Much of what makes us interested in CA is retained in such systems: they are bottom-up, spatially distributed collections of processes interacting with one another. They are like CA in which the cells are free to move about - or equivalently - in which the contents of cells are free to move about if one insists on keeping the cells themselves fixed. They may involve alterations to the basic CA paradigm, such as allowing continuous representations of space or state instead of discrete ones, or allowing for arbitrarily powerful computing machines within each "cell". Some representations are more suited to the study of certain natural phenomena than others. I have found CA very useful for some problems but unmanageable for others which could, in principle, be studied by CA. All seem to capture that essential CA feature of allowing the study of hierarchies of "emergent" global dynamics. So, how about it? What CA-like systems have others worked with and found useful? What research topics are they addressing?What research topics are they addressing? Cheers! Chris Langton Complex Systems Group MS B213, Theoretical Division Phone: 505-667-9471 Los Alamos National Laboratory Email: cgl@t13.lanl.gov