Cellular Automata FAQ


[Non-Java version]

Related Systems

Collapse all tree nodesExpand all tree nodes
Expand this node
Expand/collapse
Expand this node
What are coupled map lattices?

Contributions by: Franco Bignone <abignone@igecuniv.cisi.unige.it>

Coupled Map Lattices (CML) are like CA in that they operate in discrete time on discrete lattices. Each cell, however, supports a continuous variable. CML were introduced by Kuni Kaneko, who has extensively investigated their properties.

A good starting point for applications is Ray Kapral's work. He, together with Kaneko, started this field. I would recommend Ray's reviews explaining relationships between: CA, CML, LGCA in simulation of complex chemical reactions.

Along the same subject there are a lot of papers published in physics journals. Another node where one can gather information on this subject is at Bruxelles group

For a related study, with software for Windows, see Rudy Rucker's (rucker@jupiter.sjsu.edu) CAPOW.

Expand this node
Expand/collapse
Expand this node
What is the iterated prisoner's dilemma?

Contributions by:

Patrick Tufts <zippy@cs.brandeis.edu>

See:

Iterated Prisoner's Dilemma and the Evolution Of Non-Mutual Cooperation', by Peter Angeline (pja@owego.unet.ibm.com).

Other good sources for Prisoner's Dilemma papers are the two Simulations of Adaptive Behavior proceedings, otherwise known as "From Animals to Animats" volumes 1 and 2.

Expand this node
Expand/collapse
Expand this node
What are Cellular Neural Nets?

Contributions by: Frank Puffer

A CNN is practically a CA with continuous states that may be disrete or continuous in time.

CNN web site

There will be a conference on CNN's, CNNA96

Expand this node
Expand/collapse
Expand this node
What are continuous spatial CA?

Contributions by: Bruce MacLennan <maclennan@cs.utk.edu>

A continuous spatial automaton is analogous to a cellular automaton, except that the cells form a continuum, as do the possible states of the cells. After an informal mathematical description of spatial automata, we describe in detail a continuous analog of Conway's ``Life,'' and show how the automaton can be implemented using the basic operations of field computation.

Availability: `/pub/complex_systems/ca/MacLennan-CSA.ps.Z'

Expand this node
Expand/collapse
Expand this node
What is known about mapping neural nets onto parallel machines?

Contributions by:

Benedict A. Gomes <gomes@ICSI.Berkeley.EDU>

References on this subject, compiled by Benedict Gomes, are available.

Work in this area is diffuse and might be published in a wide variety of areas, including software, parallel systems and neural networks, making it hard to keep track of what has been done.

Expand this node
Expand/collapse
Expand this node
What are Gray Codes?

What are Gray Codes?

For a discussion of Gray Codes, including C implementation, see Gray Codes

Expand this node
Expand/collapse
Expand this node
What are 'non uniform' CA?

Contributions by: Ron Bartlett bartlett@memstvx1.memst.edu Paulo Sergio Panse Silveira <silveira@fox.cce.usp.br> Andrew Wuensche <100020.2727@compuserve.com> Moshe Sipper <moshes@math.tau.ac.il>

When each cell has a different rule, the resulting CA is called ``inhomogeneous''.

Kauffman's "random Boolean network" model allows different rules AND connections, with applications in theoretical biology.

[Wue93] discusses intermediate architectures between CA and random Boolean networks. Homogeneous rules - varying degrees of random wiring, homogeneous wiring template - various degrees of rule mix.

[Hal89]: structurally dynamic CA.

References

[VTH86] [HV00] [Kau69] [Kau84]. [Wue93] [Hal89] [Ale93] [Sip94] [Sip95b] [Sip95a]

Expand this node
Expand/collapse
Expand this node
What are Fuzzy CA?

What are Fuzzy CA?

Contributions by:

Holger Doernemann <doerne@lluja.informatik.uni-dortmund.de>

[Ada91]

Really interesting work, describing 14(!) classes of fuzzy cellular automata and their hierarchy (but are there any related applications??): []

These articles are (let me say) ,,young`` (1991 and 1994), but the roots seem to be ,,very old``: [San68], [MJK69], [WF69]

Expand this node
Expand/collapse
Expand this node
What are Movable Finite Automata?

Thomas Worsch <worsch@ira.uka.de>

Movable Finite Automata is one name given to systems with entities which move about a fixed lattice.

Perhaps the first one to consider such a model was Armin Hemmerling. He called the model ``system of Turing automata'': there is a d-dimensional tape on which finite automata can move around and read and write the tape squares. The paper [Hem79b] is in German, but you can also have a look at [Hem79a].

Expand this node
Expand/collapse
Expand this node
Overviews on relationship be CA and other systems?

Contributions by:

Dave Demaris <demaris@austin.ibm.com>

Demaris Master's thesis (postscript) treats the intersection of the topic areas: neural nets, neuroscience, nonlinear dynamics, cellular automata, coupled map lattices, cellular neural networks.

Expand this node
Expand/collapse
Expand this node
Are there any implementations of CA on quasicrystals?

Contributions by: David Ardell <ardell@charles.Stanford.EDU> <baujard@cih.hcuge.ch> BAUJARD Olivier

We have implemented a few majority rules on Penrose tilings. Relevant links can be found

here;

You might check out Eric Weeks's homepage (link is accessible through the CARGO page) for some really nice graphics of "Penrose Automata", CML's and other neat stuff.

The problem with implementing Life on a (5-fold quasiperiodic) PA is that, while all tiles have four edge-sharing neighbors, when you include vertex-sharing the neighborhood sizes vary.

I (Baujard) am using Voronoi (Dirichlet) tesselations as lattices for my CA.

Expand this node
Expand/collapse
Expand this node
References

References

Ada91
Andrew I. Adamatzkii. Identification of Fuzzy Cellular Automata. Automatic Control and Computer Sciences, 25(6):72-76, 1991.

Ale93
Zoran Aleksic. Computation in inhomogenous celluar automata. In David Green and Terry Bossomaier, editors, Complex Systems: From Biology to Computation. IOS Press, Amsterdam, 1993. anonymous ftp life.anu.edu.au: /pub/complex_systems/anu92/papers/aleksic.ps.

Hal89
Paul Halpern. Sticks and stones: a guide to structurally dynamic cellular automata. American Journal of Physics, 57(5):405-408, May 1989.

Hem79a
Armin Hemmerling. Concentration of multidimensional tape-bounded systems of Turing automata and cellular spaces. In L. Budach, editor, Fundamentals of Computation Theory, pages 167-174, Berlin, 1979. Akademie-Verlag.

Hem79b
Armin Hemmerling. Systeme von Turing-Automaten und Zellularräume auf rahmbaren Pseudomustermengen. Elektronische Informationsverarbeitung und Kybernetik, 15(1/2):47-72, 1979.

HV00
H. Hartman and G. Vichniac. Inhomogenous cellular automata. In E. Bienenstock and et al., editors, Disordered Systems and Biological Organization. unknown, 1900.

Kau69
S. A Kauffman. Metabolic stability and epigenisis in randomly constructed genetic nets. J. Theoretical Biology, 22:437-467, 1969.

Kau84
S. A Kauffman. Emergent properties in random complex systems. Physica D, 10:146-156, 1984.

MJK69
M. Mizumoto, J. Toyoda, and K. Tanaka. Some Considerations on Fuzzy Automata. Journal of Computer and Systems Sciences, 3:409-422, 1969.

San68
Eugene S. Santos. Maximin Automata. Information and Control, 13:363-377, 1968.

Sip95a
M. Sipper. Quasi-uniform computation-universal cellular automata. In ECAL95: 3rd European Conference on Artificial Life, Granada, Spain, June 1995. Springer-Verlag.

Sip95b
M. Sipper. Studying artificial life using a simple, general cellular model. Artificial Life Journal, 2(1), 1995. The MIT Press, Cambridge, MA.

VTH86
G. Vichniac, P. Tamayo, and H. Hartman. Annealed and quenched inhomogeneous cellular automata. Journal of Statistical Physics, 45, 1986.

WF69
W. G. Wee and K. S. Fu. A Formulation of Fuzzy Automata and its Application as Model of Learning Systems. IEEE Transactions on Systems, Man, Cybernetics, 5:215-223, 1969.

Wue93
Andrew Wuensche. The ghost in the machine:basins of attraction of random boolean networks. Cognitive Science Research Paper 281, University of Sussex, 1993, 1993. to be published in Artificial Life III, Santa Fe Institute Studies in the Sciences of Complexity.