For something closely related, you might want to contact Deliang Wang at the
Ohio State University, who has written a paper, "Global competition and local
cooperation in a network of neural oscillators," which describes an attractive
dynamical mechanism involved in pattern recognition. It is not a CA, but it is
very close and could without much difficulty be converted to a CA.
For applications of genetic algorithms to image processing see: GA
Image
Cellular models in Geographical Information Systems: [SOB92].
The book uses the field of urban geography as a practical example for
point-in-cell methods of spatial subdivision and analysis. For example, chapter
8 "Point Pattern Analysis" describes the use of cellular models for Nearest
Neighbour analysis in: -Voronoi diagram of distribution of settlements in an
area of Montana -Location of robberies in Milwaukee area vs location of victims'
addresses -Voronoi cellular diagram of Japanese black pine saplings -The
distribution of appartment buildings vs streets in Kohto-Sumida,Tokyo
Bauchau, Vincent" <bauchau@cto.nioo.nl> Perry Wagle
<wagle@cs.indiana.edu>
Most models of ants (and other social insects) are not strictly CA since the
rules of behavior are associated with elements that move, rather than with a
site in space. However, there are many basic questions ("How do simple local
rules give rise to global complex behavior?") which apply equally well to CA and
ant models.
The definitive book on ants is: Wilson E.O. and Holldobler B 1990 The Ants.
Springer, 732 pp, 1000 ill. (This book won the Pullitzer price.)
"A Parallel Distributed Model of the Behaviour of Ant Colonies" D.M. Gordon,
B.C. Goodwin and L.E.H. Trainor, J theor Biol (1992) 156, 293-307. Models the
dynamics of task-switching in harvester ants.
What computations can CA do?
Contributions by: Benedict.M.Wightman@cm.cf.ac.uk
If you just want a CA that does !gates then 'Wireworld', a CA that simulates
'electron streams' is probably an easier starting point than Conway's Life that
exhibits the same level of computational complexity, just on a more manageable
scale. It's in the CA Lab (Rudy Rucker's PC-based CA package), but the rules are
fairly simple and it may well be elsewhere too.
Contributions by: Matthew Burke <burke@delta.math.wsu.edu>
Marimar Villagarcia <MARIMAR@dma.ulpgc.es>
Recently there has been a significant increase in the number of articles that
deal with cellular automata (CA) and ecological modeling. There are also several
questions on how various aspects of CA affect their usefulness in ecological
models. What follows are some quick thoughts on where the major difficulties
with CA and ecological models lie. It is not intended to be thorough, and it is
not as well argued as I'd like. At the end is a list of interesting references
in the area.
The major question that needs to be addressed is that of CA's synchronicity.
[Hog88],
and others, have claimed that the simultaneous updating of all cells is at odds
with the localness of interaction that is one of the strengths of CA. It has
been shown that changing the definition of a CA to allow for asynchronous
updating of cells can dramatically alter the behavior of the CA
[Hog88][HG93].
In particular, frequently the interesting structure seen in the evolution of a
CA is, in fact, an artifact of the synchronous updating.
What needs to be addressed is whether or not there are ecological systems for
which universal updating is not an unwarranted assumption. For example,
[SHJD92]
develop a CA model of competition between grass species. I have not yet
researched the characteristics of the species involved in their model, but it is
not inconceivable to think that the dynamics of a set of annual plants may be
modeled synchronously (perhaps the species all germinate at close enough times
that on the scale of a year, we can think of it as synchronous).
On the other hand, [Gre90]
develops a CA model of the effects of fire and dispersal on spatial patterns in
forests. I see no a priori reason, however, to assume that synchronous updating
is reasonable in this situation.
Another issue that needs to be investigated is the problems associated with
multiple scales, both spatial and temporal. Typically CA models are developed
with the assumption that a cell is a physcial region of the right size for one
(or, perhaps, a few) individuals. Consider a model of plankton in the Celtic Sea
(I have, which is why I bring it up). If we assume that over a certain
horizontal distance, conditions are homogeneous, it suffices to limit ourselves
to a water column, i.e. we only need one spatial dimension. At typical
concentrations (private communication with R.A. Parker) we have enough plankton
that it is impractical to assume one plankton (or a few) per cell. Now the
relevant scales for the diffusion of plankton nutrients (such as nitrate) is
even smaller. Also, consider three typical organisms: cyanobacteria,
flagellates, diatoms, and copepods. The ratio of the fastest sinking rate to the
slowest is 200:1. Thus, if we use this information to scale spatially or
temporally, we also run into difficulties (again, the temporal scale of
diffusion for nutrients is smaller still).
Are these problems insurmountable? Is this even the best way to begin
thinking about such a model? I don't have the answers. Finally, are there
systems with inherent action-at-a-distance? Returning to the plankton model
mentioned above, we note that during chlorophyll maxima (blooms of plankton) it
is not uncommon for the plankton near the surface to dramatically decrease the
amount of light to plankton at depth due to shading. Thus, we have an effect
that (rapidly) is felt at great distance. Is this incompatible with the CA
methodology?
Below is a list of ecologically-related papers that use CA models.
Can CA be used to model reaction-diffusion systems?
Contributions by: Joerg Richard Weimar <jweimar@ulb.ac.be>
I have developed a method for constructing a CA for reaction-diffusion
equations. It basically relies on large square neighborhoods for the diffusion
part and a discretization of phase space combined with (mostly probabilistic)
state transition tables derived directly from the nonlinear reaction-diffusion
equation. I simulate excitable media (chemical waves), pattern formation,
non-conservative phase transitions, and many less spectacular RD-systems.
There is a great collection of papers [unk82].
These are the proceedings of a conference on the Physics of Computation and
Computational models of Physics.
They contain some classic papers, including many that view the universe as a
CA. Authors include Toffoli, Fredkin, Bennett, Landauer, Hillis, Feynman,
Wheeler, and so forth.
There is a fascinating paper by Marvin Minsky entitled ``Cellular Vacuum'' in
which he shows that a version of relativity holds in CA's as clocks
(oscillators) approach the speed of light - they slow down, but not in the same
way that they do in continuous space.
All in all, this collection is a must for those interested in computational
aspects of the physical universe or in the physics of computation.
David Ardell <ardell@charles.stanford.edu> Bruce M. Boghosian
<bruceb@bu.edu>
B. Ostrovsky and M.A. Smith and Y. Bar-Yam", "Applications of parallel
computing to biological problems" Ann. Rev. Biophys. Biomol. Struct. (1995)
24:239-67 - uses Margolus dynamics to conserve mass and implement excluded
volume, or a novel two-space algorithm to do the same, discusses fine- vs.
course-grain simulation issues
and
S. Rasmussen and J.R. Smith, "Lattice Polymer Automata" Ber. Bunsenges. Phys.
Chem. (1994) 98(9):1185-1193 - extension of LGA that uses particle-interactions
to implement excluded volume and polymeric bonds
There are further references within these two. The first is particularly easy
to find in a good biology library. The second may not be so easy. Try
contacting:
VCH Verlagsgesellschaft mbH, D-69451 Weinheim Paper #0005-9021/94/0909-1185
Also, for the modeling of microemulsions with lattice gases, see B.M.
Boghosian, P.V. Coveney, A.N. Emerton, "A Lattice-Gas Model of Microemulsions,".
You can obtain the paper by sending mail to comp-gas@xyz.lanl.gov with the words
"get 9507001" (no quotes) in the subject line, or via the World Wide Web at:
http://xxx.lanl.gov/abs/comp-gas/9507001
Microemulsions consist of two immiscible fluids (e.g., oil and water) plus a
surfactant or amphiphile (e.g., detergent). The surfactant usually has a
hydrophyllic ionic head, and a hydrophobic hydrocarbon tail, so that it likes to
live at the oil/water interface. Depending on the relative concentrations of the
three components, the mesoscale behavior of microemulsions can be exceedingly
complex, as structures self-organize in order to provide sufficient surface area
to accomodate the surfactant. (Not exactly deformable, but a very interesting
material nevertheless.)
When Von Neumann started working on robotic self-replication, he first tried
the "robot in a warehouse of spare-parts" approach, otherwise known as the
kinematic approach. But it was was mathematically too unweildy, so he invented
CA. I wonder if there has been any serious theoretical work making CA more
kinetic.
Last year I developed a simulation I called "Biomatrix" which sounds similar
to what you're asking about. Cells in the matrix could have a variety of states,
divided into three general categories: empty, structural unit, or instruction.
Cells could also contain a "program
You might want to have a look at our paper: R. Sosic and Robert R. Johnson.
Computational Properties of Self-Reproducing Growing Automata. (to appear in
BioSystems)
The latest American Scientist (May-June 1995) has a cover story on 1-D CA
patterns found on shells (such as Oliva porphyria and Cymbiola innexa Reeve).
Try the following book by Hans Meinhardt: "The Algorithmic Beauty of Sea
Shells" ISBN 3-540-67842-0 ISBN 0-387-57842-0 Springer Verlag, 1995
G.T.Herman, G.Rozenberg - Developmental Systems and Languages. North-Holland,
1975:
In the book you'll find may be the first biologically oriented applications
of cellular automata. This study of synchronization aspects of growing filaments
is very interesting. There are also some shell patterns in the book, firing
squad synchronization problem description, French flag problem solution, and
many other topics on cellular automata and their biological context.
What do CA have to do with biological computation?
Two good references for molecular and biomolecular computing are:
IEEE Egineering in Medicine and Biology, February-March, 1994.
IEEE Computer, volume 25, number 11, November, 1992.
In both of these magazines there are many articles on this topic with
references or pointers to many others.
Of particular interest to this group may be:
Hameroff, S.R., J.E. Dayhoff, R. Lahoz-Beltra, A.V. Samsonovich and S.
Rasmussen. 1992. Conformational automata in the cytoskeleton. Computer,
25(11):30-40.
Can CA be used to construct random number generators?
Contributions by: Nelson Minar <nelson@santafe.edu>
See: nelson
including a README.html, a bibliography, and lots of code.
As for a quick summary.. there are two basic classes of generators in common
use. Both classes have some theoretical grounding
Linear Congruential Generator
Lagged fibonacci
LCGs have a lot of history and are the root of most random number libraries.
As long as the modulus m is prime and a is chosen carefully, they seem to do
fairly well. But many implementations choose m to be some power of 2, which
result in low order bits with extremely low periods. The particular generator of
this class I use is I
have an article by Park and Miller in my bibliography about this generator: it's
period is
.
Lagged Fibonacci generators are also fairly old, but are not as well known.
Knuth deprecates them for lack of theory, but that doesn't seem entirely fair to
me based on what I've read. Many choices of the function f have been suggested,
usually very simple and fast ones. The one I use is based on a recent
recommendation by Marsaglia:
where
"carry" is from the previous calculation. The Marsaglia paper in my bibliography
has a nice bit of theory on this generator: it's period is roughly
.
There are other methods of generating random numbers. Numerical Recipies
recommends using a shuffling algorithm to mix up the output of one of these
simple generators. Several researchers here recommended that method to me.
Also, a lot of cryptographic research can be thought of as a search for the
perfect random number generator. Several good ones have been found: DES, for
instance, is great at generating random numbers. It's also pretty slow and
weighty, though.
See:
1) Tsalides Ph., York T.A., Thanailakis A. Pseudorandom number generators for
VLSI systems based on linear cellular automata. IEE Proceedings-E, vol. 138,
No.4, July 1991, pp. 241-249.
What links are there between CA and complexity theory?
See: Juris Hartmanis. On the Computing Paradigm and Computational Complexity.
MFCS'95. (eds.) J.Wiederman, P.Hajek. Berlin, Springer 1995, LNCS No.969, pp.
82- 92.
In this paper you will find an overview of the state of affairs in
computational complexity theory. Note that the author is probably No.1 world
authority in the subject. The paper includes also an interesting disscussion of
recent Adleman's molecular solution of the Hamiltonian path problem. The
conclusion is that even molecular computations can not escape the exponential
curse. The weight of "soup" becomes prohibitive. The calculations show that for
a graph with 200 nodes the biologically encoded set of paths will weight more
than the Earth ! The exponential function grows too fast and even atoms are a
bit too heavy to break this barrier.
There is also another worthwhile paper:
3) Paul Vitanyi Physics and the New Computation MFCS'95. (eds.) J.Wiedermann,
P.Hajek. Berlin, Springer 1995, LNCS 969, pp. 106-128.
It discusses the physical limits for doing computations: the geometry of
space and speed of light, energy dissipation by laws of thermodynamics and
quantum mechancis constraints.
What is the relationship between CA and neural networks?
There is some litterature about this:
1) Preston K, Duff M., Modern cellular automata, advanced applications in
pattern recognition, New York, Plenum, pp317-328, 1984.
2) Terrier V. Real time recognition with cellular automata a meaningful
example,Rapport LIP-R-90-17,ENS Lyon 1987.
3) de Lassus H, Neural network clusters and cellular automata for the
detection and classification of overlapping transient signals on radio astronomy
spectrograms from spacecraft. IEEE Conference on time frequency analysis Paris
June 1996. (Accepted Paper).
What are Byl's rules for a self reproducing CA?
Contributions by: <hhchou@cs.umd.edu> H.H. Chou
Our research group have dealt with old self-replicating loops a while ago. I
don't have time to recapture my memory, but from a quick grep search on our old
rule sets archive I have found these rules which I believe implements Byl's
self-replicating rule set. I don't remember if it is the "newly updated" rule
set what you want, but I do know that these rules run well under our simulation
environment since they are taking from executable CA rules directly. I hope it's
helpful to your need.
P Deadman, R. D Brown, and H. R Gimblett. Modelling rural residential
settlement patterns with cellular automata. Journal of environmental
management, 37(2):147, February 1993.
G. Bard Ermentrout and Leah Edelstein-Keshet. Cellular automata approaches
to biological modeling. Journal of Theoretical Biology, 160:97-133,
January 1993.
D. G. Green, House A. P. N., and S. M. House. Simulating spatial patterns
in forest ecosystems. Mathematics and Computers in Simulation,
27:191-198, 1985.
David Geoffrey Green. Cellular automata models of crown-of-thorns
outbreaks. In R. H. Bradbury, editor, Acanthaster and the Coral Reef:A
Theoretical Perspective, volume 88 of Lecture Notes in
Biomathematics, pages 169-188. Springer-Verlag, Berlin, 1990.
Howard Gutowitz. Method and apparatus for encryption, decryption, and
authentication using dynamical systems. U.S. Patent 5,365,589 Issued Nov.
15, 1994, 1992.
Howard Gutowitz. Cryptography with dynamical systems. In N. Boccara, E.
Goles, S. Martinez, and P. Picco, editors, Cellular Automata and
Cooperative Phenomena, pages 237-274. Kluwer Academic Publishers, 1993.
B. A. Huberman and N. Glance. Evolutionary games and computer simulations.
Proceedings of the National Academy of Sciences, USA, 90:7716-7718,
August 1993.
P. Hogeweg and B. Hesper. Crowns crowding:an individual oriented model of
the acanthaster phenomenon. In R. H. In Bradbury, editor, Acanthaster and
the Coral Reef:A Theoretical Perspective, volume 88 of Lecture Notes
in Biomathematics, pages 169-188. Springer-Verlag, Berlin, 1990.
Kazuhiro Satoh. Computer experiment on the complex behavior of a
two-dimensional cellular automaton as a phenomenological mpdel for an
ecosystem. Journal of the Physical Society of Japan,
58(10):3842-3856, 1989.
Kazuhiro Satoh. Single and multiarmed spiral patterns in a cellular
automaton model for an ecosystem. Journal of the Physical Society of
Japan, 59(12):4204-4207, 1990.
Jonathan Silvertown, Senino Holtier, Jeff Johnson, and Pam Dale. Cellular
automaton models of interspecific competition for space-the effect of pattern
on process. Journal of Ecology, 80:527-534, 1992.
R. White, G. Engelen, and I. Uljee. Cellular automata modelling of fractal
urban land use patterns: Forcasting change for planning applications.
unknown, 1900.
Lagged fibonacci 
I
have an article by Park and Miller in my bibliography about this generator: it's
period is
.
where
"carry" is from the previous calculation. The Marsaglia paper in my bibliography
has a nice bit of theory on this generator: it's period is roughly
.