ca-faq.dvi2tty (ascii)
Howard GUTOWITZ
Frequently Asked Questions
About Cellular Automata
Contributions
from the CA community
edited by
Howard Gutowitz
December 8, 1993
Abstract
The FAQ has taken a great leap forward thanks to the contributions of
many individuals. Special thanks due to J"org Heitk"otter
<jo...@ls11.informatik.uni-dortmund.de> for many "infrastructure"
contributions.
Further contributions are needed and warmly welcome. In particular,
please send bibliographic material (see section 2.3). I have a couple hundred
typed pages of references which need to be converted to bibtex format, if
you are able to lend a secretarial hand, please make yourself known to
<h...@santafe.edu>.
1
Contents
1 What are Cellular Automata (CA)? 3
2 General Information 4
2.1 How can I get the latest FAQ? : : : : : : : : : : : : : : : : : : : : :*
* 4
2.2 How do I process the CA FAQ? : : : : : : : : : : : : : : : : : : : : 4
2.3 How do I contribute bibliographic material to the FAQ? : : : : : : : 4
2.4 What is the cellular automata mailing list? : : : : : : : : : : : : : *
*: 5
2.4.1 USENET : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* 5
2.4.2 BITNET : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* 5
2.4.3 INTERNET : : : : : : : : : : : : : : : : : : : : : : : : : : : *
* 6
2.4.4 ARCHIVES : : : : : : : : : : : : : : : : : : : : : : : : : : : *
* 6
2.5 What are some good general references for CA? : : : : : : : : : : : 6
2.6 What is the Complex Systems Journal? : : : : : : : : : : : : : : : : 6
3 Where can I get a CA Simulator? 6
3.1 General-Purpose CA Simulators : : : : : : : : : : : : : : : : : : : : *
* 7
3.1.1 automata : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : 7
3.1.2 CALAB : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* 7
3.1.3 CAMEX : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* 7
3.1.4 CAM-PC : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* 8
3.1.5 CART : : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: 8
3.1.6 CELIP : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : 8
3.1.7 Cellsim : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : 8
3.1.8 CELLULAR-3.0 : : : : : : : : : : : : : : : : : : : : : : : : : 9
3.1.9 CEPROL : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* 9
3.1.10 LCAU : : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: 9
3.1.11 Mathematica : : : : : : : : : : : : : : : : : : : : : : : : : *
*: 10
3.1.12 scamper : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : 10
3.1.13 Self-Directed Replicator (?) : : : : : : : : : : : : : : : : :*
* : 10
3.1.14 SimLife : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : 10
3.1.15 SLANG : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* 10
3.1.16 Wautom : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: 10
3.2 Simulators for the Game of Life : : : : : : : : : : : : : : : : : : : *
*: 11
3.2.1 bugglings : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : 11
3.2.2 Life : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : 11
3.2.3 lifelab : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : 11
3.2.4 Mac-CA : : : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: 11
3.2.5 Plife : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : 11
3.2.6 3dlife : : : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : : 11
3.2.7 xlife-2.0 : : : : : : : : : : : : : : : : : : : : : : : : : : *
*: : : 11
3.3 Does Cellsim for X exist? : : : : : : : : : : : : : : : : : : : : : : :*
* : 12
3.4 What is 3D-Life? : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : 12
2
3.5 How can I make CA simulations run fast? : : : : : : : : : : : : : : 12
3.6 What hardware implementations exist for CA? : : : : : : : : : : : : 13
3.7 Are there any simulators for CAM? : : : : : : : : : : : : : : : : : : *
*14
3.8 Are there simulators for self-criticality? : : : : : : : : : : : : : :*
* : : 14
3.9 What about running CA's on parallel or distributed machines? : : : 14
4 Applications 15
4.1 What computations can CA do? : : : : : : : : : : : : : : : : : : : : 15
4.2 How do you do computations with the Game of Life? : : : : : : : : 16
4.3 Can CA be used to model ecological systems? : : : : : : : : : : : : 17
4.4 The Universe as a Cellular Automata? : : : : : : : : : : : : : : : : *
*18
4.5 Can CA be used to encrypt messages? : : : : : : : : : : : : : : : : 18
5 Special Types of CA 18
5.1 What are Lattice Gas Automata? : : : : : : : : : : : : : : : : : : : 18
5.1.1 Does the lack of symmetry in the HPP model have any ob-
vious bad effect, other than to remove the inertial term? : : *
*19
5.1.2 Are there unphysical conservation laws with HPP? : : : : : 19
5.1.3 What are the physical manifestations of anisotropy? : : : : : 19
5.2 What are continuous spatial CA? : : : : : : : : : : : : : : : : : : : *
*19
5.3 Where can I read about the Gacs rule? : : : : : : : : : : : : : : : : *
*20
5.4 What's the Hodge Rule? : : : : : : : : : : : : : : : : : : : : : : : :*
* 20
5.5 What are some good references on Eater Rules? : : : : : : : : : : : 20
5.6 What are Vants? : : : : : : : : : : : : : : : : : : : : : : : : : : :*
* : 21
5.6.1 some vant simulators : : : : : : : : : : : : : : : : : : : : : *
*: 21
6 Properties of CA 21
6.1 What is Flocking Behavior in CA? : : : : : : : : : : : : : : : : : : *
*21
6.2 What about basins of attraction for CA? : : : : : : : : : : : : : : : *
*22
6.3 What are "inhomogeneous" CA? : : : : : : : : : : : : : : : : : : : 22
6.4 How important is Synchronicity in CA? : : : : : : : : : : : : : : : : 22
6.5 Which computations can 1D CA perform? : : : : : : : : : : : : : : 24
6.6 Is there is universal 1D CA? : : : : : : : : : : : : : : : : : : : : :*
* : 24
6.7 How to perform computations in the Game of Life? : : : : : : : : : 25
6.7.1 Must one use all of the logical gates to perform computations
in the Game of Life? : : : : : : : : : : : : : : : : : : : : : *
*: 26
6.8 Where can I learn about Spaceships in the Game of Life? : : : : : : 26
6.9 What about running a CA backwards? : : : : : : : : : : : : : : : : 26
6.9.1 The General Case : : : : : : : : : : : : : : : : : : : : : : : *
*: 26
6.10 What are some reversible rules? : : : : : : : : : : : : : : : : : : : *
*: 27
6.11 What is known about periodic orbits in CA? : : : : : : : : : : : : : 27
6.12 What are Subshifts of Finite Type/Sophic Systems? : : : : : : : : : 28
6.13 What is the mean field theory? : : : : : : : : : : : : : : : : : : : *
*: 29
6.14 When is a CA injective, surjective? : : : : : : : : : : : : : : : : : *
*: 30
3
6.15 Can one decide if a 2D rule is reversible/surjective? : : : : : : : : : 30
6.16 Where do I read about reversible cellular automata? : : : : : : : : : 31
4
1 What are Cellular Automata (CA)?
contributions by:
Lyman Hurd <hu...@math.gatech.edu>
Here is one physicist's view of the relevant definitions:
A cellular automaton is a discrete dynamical system. Space, time, and the states
of the system are discrete. Each point in a regular spatial lattice, called a *
*cell,
can have any one of a finite number of states. The states of the cells in the l*
*attice
are updated according to a local rule. That is, the state of a cell at a given
time depends only on its own state one time step previously, and the states of *
*its
nearby neighbors at the previous time step. All cells on the lattice are updat*
*ed
synchronously. Thus the state of the entire lattice advances in discrete time s*
*teps.
Here is one mathematician's view of the relevant definitions:
Conventions d=dimension, k=states per site, r=radius (all explained below).
For simplicity, assume d=1 for the moment.
A d-dimensional cellular automaton takes as its underlying space the lattice SZ
(Z=integers, infinite in both positive and negative directions) where S is a fi*
*nite
set of k elements. The dynamics are determined by a global function
F : SZ - ! SZ (1)
whose dynamics are determined "locally" as defined below.
A "local (or neighborhood) function" f is defined on a finite region
f : S2r+1 -! S: (2)
The all-important property of cellular automata, is that this function is deter*
*mined
by a finite lookup table. Both the domain and range of f are finite.
The global function F arises from f by defining:
F (c)i= f(ci-r; : :;:ci+r): (3)
A concrete example with k=2,r=1 would take a doubly infinite string of zeroes
and ones to a new string at which each site is replaced by the logical and of i*
*ts
two neighbors (Wolfram's elementary rule 90).
Some relevant facts from a topological standpoint are:
1. The base space SZ is compact and the global function F is continuous.
To insert an editorial comment, this makes CA an ideal meeting point be-
tween continuous dynamics and complexity theory, since they are discretely
defined but exhibit continuous dynamics.
2. The map F commutes with the shift operator which takes ci to ci+1.
5
In fact cellular automata are characterized completely by properties 1) and 2)
(Hedlund).
The transition to more dimensions is straightforward. The only difference is th*
*at
d
the global function F is defined over SZ (functions from a d-dimensional latti*
*ce to
S) and the local function f is determined by enumerating the image of all patch*
*es
d
of size 2r+1 .
2 General Information
2.1 How can I get the latest FAQ?
contributions by:
Bruce Boghosian <b...@Think.COM>
The FAQ will be available by anonymous FTP at think.com. It will be cross-
posted to comp.answers, and santafe.edu will serve as a mirror site.
2.2 How do I process the CA FAQ?
contributions by:
Joerg Heitkoetter <heit...@lusty.informatik.uni-dortmund.de>
James Kennedy CSMR x6238 <JI...@RCC.RTI.ORG>
The CA FAQ is configurable for US letter size and standard A4 paper sizes; it a*
*lso
comes with a Makefile included. All there is to do, is (1) unpack the ca-faq.ta*
*r :
(a) uudecode <this-file> (b) gunzip ca-faq.tar.gz (c) tar xvf ca-faq.tar then "*
*cd"
to the ca-faq folder; and type "make us-ps" or "make a4-ps" (us-ps is the defau*
*lt);
The makefile will take care of bibtex'ing, and will strip off the latex command*
*s, if
you so desire.
2.3 How do I contribute bibliographic material to the
FAQ?
Send references you do not see in "ca.bib" to h...@santafe.edu. Use bibtex format
whenever possible. If you don't know bibtex, use the very nice utility "bibview"
developed at the Technical Univeristy of Munich, and avail.: ftp.informatik.tu-
muenchen.de: `/pub/comp/typesetting/tex/bibview-2.0.tar.Z'. Use of bib-
view will significantly improve your enjoyment of "ca.bib". If you don't use X-
windows (needed by bibview), then try "basetex" in the ca-faq directory, it will
prompt you for entries and write them in the right format. Use first.author.nam*
*eYEAR
(lower case) for the key, e.g. "wolfram84" for an article published by Wolfram *
*and
Packard in 1984. Ties are resolved by appending "a" "b" "c" etc.
6
2.4 What is the cellular automata mailing list?
contributions by:
Bruce M. Boghosian <b...@think.com>
This mailing-list is for the discussion of topics relating to cellular automata*
*. For
an introduction to CA, some of the more well-known references are:
[?] [?] [?]
Discussions on the list often cover topics such as practical applications of CA*
*, the
theory of CA, implementation/performance issues, and discussions of available
software packages to perform CA experiments.
The cellular automata mailing list is really made up of three parts:
o An Internet mailing-list
o A Bitnet LISTSERV-maintained mailing-list
o The Usenet newsgroup "comp.theory.cell-automata"
The three parts are coupled in all directions, so that a message on any one part
of the list is automatically forwarded to the other two parts.
2.4.1 USENET
If you are able to, I recommend that you read the Usenet newsgroup. That
way, you control your own participation, rather than depending on me as list-
maintainer. This keeps the list smaller and much easier to maintain, and if you
move to a new account, nothing needs to be done.
2.4.2 BITNET
If you are at a Bitnet site, you may prefer to use the Bitnet LISTSERV mechanism
to subscribe to the list. LISTSERV is the standard mechanism for maintaining a
mailing-list on Bitnet. This also makes the list easier for me to maintain, sin*
*ce it
is more automated.
To subscribe in this way, send a message to LISTSERV@MITVMA containing the
following line in the body of the message:
SUBSCRIBE CA-L Your RealName
You may also send a message containing the line:
HELP
to get more information about LISTSERV.
You can also subscribe to the mailing-list through the LISTSERV even if you are
not directly connected to Bitnet, by sending the message to <list...@mitvma.mi*
*t.edu>.
7
2.4.3 INTERNET
If you are not able to use either of the above methods, or if you simply would
prefer to be on the Internet side of the list for some reason, please send mail*
* to
<cellular-aut...@think.com> (or just reply to this message) specif-
ically requesting to be added to the Internet side of the CA mailing-list, usin*
*g the
format described at the beginning of this message. Again, if you don't use that
exact format, I'll assume you haven't seen this message, and send it to you aga*
*in.
2.4.4 ARCHIVES
The CA mailing-list is archived, and available via anonymous FTP to think.com
(131.239.2.1) if you are on the Internet. You can FTP to that site using a login
of "anonymous," and your e-mail address as a password. The archives are under
the "mail" directory, in the files `ca.archive*'. Previous years are kept in co*
*m-
pressed format, e.g. `ca.archive-1987.Z'. Archives for the current year are not
compressed, and kept in the file `ca.archive'.
2.5 What are some good general references for CA?
contributions by:
Mark A Biggar <m...@dst17.wdl.loral.com>
John Baez <ba...@guitar.ucr.edu>
[?] [?] [?] [?]
2.6 What is the Complex Systems Journal?
Complex Systems:
A journal devoted to the rapid publication of research on the science, mathemat*
*ics,
and engineering of systems with simple components but complex overall behavior.
Editor: Stephen Wolfram, Wolfram Research, Inc., and University of Illinois
Published six times a year by: Complex Systems Publications, Inc. P.O. Box 6149
Champaign, IL 61826 USA
Subscriptions: $45 (students), $75 (individuals), $250 (institutions), Outside *
*North
America, add $15 (surface) or $65 (air).
3 Where can I get a CA Simulator?
contributions by:
Russell Inman <in...@ceti.csustan.edu>
H.H. Chou <hhc...@cs.umd.edu>
Dana Eckart <da...@rucs.santafe.edu>
Andy Wakelin <mct...@uk.ac.dct>
8
Harold McIntosh <mcin...@redvax1.dgsca.unam.mx>
Rudy Rucker <ruc...@sjsumcs.SJSU.EDU>
Ken Karakotsios <kara...@apple.com>
Simone Maggi <ma...@c700-2.sm.dsi.unimi.it>
3.1 General-Purpose CA Simulators
General Reference: [?].
3.1.1 automata
author: <cs8...@brunel.ac.uk> (Sunil Gupta)
description: Runs various two-D CA. Written in C, Based on SUIT. SUIT is a
library of interface tools developed at the University of Virginia to help C pr*
*o-
grammers create sophisticated mouse based interfaces.
requirements: Also central to SUIT design is portability. SUIT programs current*
*ly
run without changes to the source code on the following platforms: IBM PC,
Macintosh, Sun3, Sun4 (SparcStation), SGI (Silicon Graphics IRIS workstations),
DECstation, HP. The program will not run very well (if at all) on a monochrome
system. it was designed for color. The program is operated entirely through a
graphics interface.
availability: anonymous ftp ftp.cs.umd.edu: `/pub/dtr.tar.Z'
3.1.2 CALAB
Autodesk has two free CA programs for the PC compatible machine on Com-
puserve. If you can get on Compuserve, enter GO ADESK and go into Li-
brary 4 - CA Lab/CHAOS of the Autodesk Software Forum. The CA files are
CALAB1.COM (7K) and CALAB2.EXE (200K). These files are self-extracting
archives. CALAB1.COM will give you a version of the RC program that comes
with CA LAB and runs a diffusion CA, Life, Brain, Vote, and some Langton
style CAs. CALAB2.EXE will give you a version of the CADEMO program that
comes with CA LAB and runs a variety (I think about 15) different CAs in demo
mode. The CALAB1.COM program RC is interactive and runs in low resolution,
the CALAB2.EXE program CADEMO is not interactive, and runs in a higher
(320x200) resolution.
3.1.3 CAMEX
CAMEX is an exerciser for the CAM/PC, which is a special video controller sold
by Automatrix; it is also applicable to the CAM-6 but we don't know much about
people's experience with that board. The program is written in C, and requires
minimal equipment for a PC or PC/clone which is capable of accepting one of
the boards. The program covers an extensive collection of one, two, and three
dimensional automata, and can be had on request. The CAM/PC is sold with a
9
copy of the Toffoli-Margolus book, the FORTH program described in the book,
and a substantial collection of examples. Those examples are heavily oriented
toward diffusion and reaction-diffusion rules, and rules depending on the Margo*
*lus
neighborhood. The orientation of CAMEX is different, leaning toward very general
classes of (non-Margolus) rules, and includes many of the same rules as LCAU, as
well as such features as the calculation of de Bruijn diagrams, mean field curv*
*es,
and return maps.
availability: Harold V. McIntosh <mcin...@redvax1.dgsca.unam.mx>
3.1.4 CAM-PC
description: A general purpose cellular automata simulation program, called CAM-
PC, based on CAM-6 (Toffoli and Margolus), has been uploaded to the Alife
archives. The simulator extends the possibilities of CAM-6, but (at least this *
*first
version) is not fully downwards compatible with the original.
Authors: Zoltan Belso and Miklos Vargyas ELTE University, Budapest, Hungary
requirements: The program requires an IBM compatible computer, MCGA or
VGA display and about 188 kB-s of free memory to run. It requires 100 kB-s to
install.
availability: ftp.cognet.ucla.edu ` pub/alife/public/cam.zip ' (An alterna-
tive site is cogsci.elte.hu `cogsci/alife/CA')
3.1.5 CART
description: see [?].
requirements: ??
availability: ??
3.1.6 CELIP
description: see [?].
requirements: ??
availability: ??
3.1.7 Cellsim
description: built on top of C, also can use parallel processing power of a CM-?
machine
requirements: UNIX, sunview or X11 (see section 3.3 )
availability: plaza.aarnet.edu.au life.anu.edu.au think.com sun.soe.clarkson.e*
*du
sparc01.cc.ncsu.edu iear.arts.rpi.edu uceng.uc.edu bikini.cis.ufl.edu isy.liu.s*
*e nc-
10
3.1.8 CELLULAR-3.0
Description: The system consists of: a programming language, Cellang 3.0, and
associated compiler, cellc; an "abstract" virtual machine, for execution, pe-sc*
*am;
and a viewer, cellview. Compiled Cellang 3.0 programs can be run with input
provided at any specified time during the execution. The results of an execution
can either be viewed directly or output as a stream of cell locations and value*
*s.
This stream of output data can then be fed into cellview for viewing, or it may*
* be
passed through a filter that compiles statistics, massages the data, or merely *
*acts
as a valve to control the flow of data from the cellular automata program to the
viewer. This simple UNIX toolkit view of the simulation process provides greater
control than systems which combine the language and viewer. Cellang 3.0 also
provides greater flexibility, particularly in the formation of neighborhoods, t*
*han
do many other systems.
Requirements: The current system supports both the X11 and Iris Graphics Li-
brary windowing systems and can generate shared memory multi-threaded code
for multi-processor Sun and SGI (Sequent?) machines.
availability: J Dana Eckart <da...@rucs.faculty.cs.runet.edu>
Also:
plaza.aarnet.edu.au (2.0) brolga.cc.uq.oz.au (2.0) gatekeeper.dec.com (2.0) res*
*eq.regent.e-
technik.tu-muenchen.de (2.0) athene.uni-paderborn.de (2.0) inf.informatik.uni-s*
*tuttgart.de
(2.0) usc.edu (2.0) keos.helsinki.fi (2.0) irisa.irisa.fr (2.0) walton.maths.tc*
*d.ie (2.0)
ftp.cfi.waseda.ac.jp (2.0) lth.se (2.0) nctuccca.edu.tw (2.0) unix.hensa.ac.uk *
*(2.0)
3.1.9 CEPROL
description: see [?]
requirements: ?? availability: ??
3.1.10 LCAU
Description: These programs are substantially one-dimensional, one each for sma*
*ll
integer (and half-integer) combinations of Wolfram's k and r. Each program cov-
ers evolution, probability, de Bruijn diagrams, and the calculation of ancestor*
*s.
Copies of the programs and literature will be sent in response to requests bear*
*ing
a complete mailing address, including city, country, and Zip Code. What will
actually be sent depends on what is requested and what literature is 'in print'*
* at
the moment. The usual reply includes .EXE for some of the most popular combi-
nations, a programming manual, and the complete C source for LCAU23, which
can be used to study the Chat'e-Manneville automata.
requirements:
IBM/PC or clone with a minimum of equipment, namely CGA color and a recent
DOS (neither Windows nor VGA is required, but can be used).
availability: Harold V. McIntosh <mcin...@redvax1.dgsca.unam.mx>
11
3.1.11 Mathematica
description: a notebook showing an array of Cellular Automata
requirements: Mathematica
availability: swdsrv.edvz.univie.ac.at ra.nrl.navy.mil
3.1.12 scamper
description: provides its own language and has a nice GUI
requirements: UNIX, X11
availability: plaza.aarnet.edu.au brolga.cc.uq.oz.au liasun3.epfl.ch gatekeeper*
*.dec.com
qiclab.scn.rain.com reseq.regent.e-technik.tu-muenchen.de athene.uni-paderborn.*
*de
inf.informatik.uni-stuttgart.de nuri.inria.fr walton.maths.tcd.ie relay.iunet.i*
*t isfs.kuis.kyoto-
u.ac.jp walhalla.germany.eu.net lth.se nctuccca.edu.tw unix.hensa.ac.uk
3.1.13 Self-Directed Replicator (?)
author: Hui-Hsien Chou <hhc...@eng.umd.edu>.
description:
Simple Systems Exhibiting Self-Directed Replication: Transition Functions, Soft-
ware, and Documentation March, 1993
We have recently developed and studied cellular automata models of self-replica*
*ting
systems [Science, 259, 1993, pp. 1282-1288]. Files containing a version of the *
*vari-
ous transition functions are now available via ftp. The cellular automata softw*
*are
is actually fairly general and could also serve as an application-independent s*
*im-
ulator. For further details please refer to the paper cited above. availabili*
*ty:
ftp.cs.umd.edu `pub/dtr.tar.Z'
3.1.14 SimLife
description: GUI
requirements: UNIX(?) or mac or amiga or PC availability: in local software sto*
*re
3.1.15 SLANG
description: see [?]
requirements: ??
availability: ??
3.1.16 Wautom
description: 1-Dimensional elementary binary cellular automata, with Wolfram's
rules 0 to 255. WAUTOM features: intuitive "Windows"-like user interface, cus-
tom window size for the evolution space, custom number of iteration to compute,*
* a
button to activate/deactivate the cyclic modality, (i.e.: hyperplane space on/o*
*ff),
live-cell diagram.
12
availability: ghost.dsi.unimi.it ` /pub2/papers/magi/wautom.zip'
requirements: 286 machine, VGA, necessarily the MOUSE (or equivalent pointer);
Ms-Dos 3.10 or later. Ms-Windows NOT required!
3.2 Simulators for the Game of Life
3.2.1 bugglings
requirements: mac
availability: ??
3.2.2 Life
requirements: amiga
availability: plaza.aarnet.edu.au amiga.physik.unizh.ch rs3.hrz.th-darmstadt.de*
* reseq.regent.e-
technik.tu-muenchen.de ux1.cso.uiuc.edu ftp.luth.se nctuccca.edu.tw
3.2.3 lifelab
requirements: mac
availability: akiu.gw.tohoku.ac.jp ftp.EU.net mcsun.eu.net fastlife-2.2
requirements: amiga, Kickstart 2.04+,
availability: plaza.aarnet.edu.au reseq.regent.e-technik.tu-muenchen.de minnie.*
*zdv.uni-
mainz.de amiga.physik.unizh.ch ftp.luth.se nctuccca.edu.tw
3.2.4 Mac-CA
description: I've written a CA Simulator for the Mac which, although not public
domain, is fairly inexpensive ($30). availability: Send email to karakots@apple*
*.com.
3.2.5 Plife
requirements: Microsoft Windows on a PC
availability: In the UK at a JANET (Joint Academic NETwork) site. The file you
want is `micros/ibmpc/win/a/a035/a035plife.boo'
3.2.6 3dlife
availability: life.anu.edu.au:
file/pub/complex_systems/alife/3DLIFE.ZIP
3.2.7 xlife-2.0
requirements: UNIX, X11
availability: iacrs1.unibe.ch alice.fmi.uni-passau.de uxc.cso.uiuc.edu life.c
requirements: UNIX(?), curses
13
availability: rs3.hrz.th-darmstadt.de agate.berkeley.edu ocf.berkeley.edu ux1.c*
*so.uiuc.edu
f.ms.uky.edu bongo.cc.utexas.edu watserv1.waterloo.edu relay.iunet.it isfs.kuis*
*.kyoto-
u.ac.jp toklab.ics.es.osaka-u.ac.jp ftp.cfi.waseda.ac.jp ugle.unit.no kth.se su*
*ne.stacken.kth.se
colonsay.dcs.ed.ac.uk
3.3 Does Cellsim for X exist?
contributions by:
Dave Hiebeler <hieb...@think.com>
Felicity George <fa...@uk.ac.ed.epcc>
Hiebeler: Quite some time ago, I started trying to do an X11 version in my rare
spare time. I got as far as having the very simple basics working, so I could d*
*isplay
a 2-D image in black&white, load a rule and image, and run. But very little else
was in there, and I never get time to work on it any more. Also, I don't know
anything about doing colors in X11. So I can't really say whether an X11 version
will ever be released.
George: In case anyone is interested, I have written an X11 version of Cellsim,
which runs in black and white. It has not been extensively tested, as I have not
had time to work on it, but if anyone wants a copy, I'll fix bugs as they come *
*up.
3.4 What is 3D-Life?
contributions by:
Anthony Wesley <awe...@canb.auug.org.au>
Harold V. McIntosh <MCIN...@unamvm1.dgsca.unam.mx>
John Pedersen <j...@GOEDEL.MATH.USF.EDU.>
Carter Bays gives a new rule for 3D Life in [?].
The 3dlife program is available for ftp from life.anu.edu.au: `/pub/complex_sys*
*tems/alife/3DLIFE.ZIP'
References
[?] [?]
3.5 How can I make CA simulations run fast?
contributions by:
Rudy Rucker <ruc...@sjsumcs.SJSU.EDU>
Richard Ottolini <stg...@st.unocal.COM>
I can think of four main tricks for making a CA program run fast.
1. Lookup table. Generally a cell takes on a NewC value which is computed
on the basis of info in the cell's neighborhood. Try to find a way to pack
the neighborhood info bitwise into a nabecode number. Then use nabecode
as an index into a lookup table. Thus NewC = lookup[nabecode]. You
14
precompute the lookup values for all possible nabecodes before running the
CA. Lookups can be saved, as Walker and I did in CA LAB.
2. Pointer swap. To run a CA, you need two buffers, one for the current world
of cells, and one for the updated world of cells. After the update, *don'*
*t*
copy the updated world onto the current world. Just swap the pointers to
world and new world.
3. The flywheel. In stepping through the cells of the CA, you repeatedly com-
pute a cell's nabecode, then compute the nabecode of the next cell over, a*
*nd
so on. Because the neighborhoods overlap, a lot of the info in the next ce*
*ll's
nabecode is the same as in the old cell's nabecode. Try to arrange nabecode
so that you can left shift out the old info and OR in the new info.
4. Assembly language. A 2D VGA CA is going to have about 300K cells.
That means you are going to assemble nabecodes and lookup the NewC
values about 300K times per screen. This means that your inner loop for
flywheeling the nabecode must be as efficient as possible. If you can writ*
*e this
in assembly language, and keep an eye on the listed "clocks" per instructi*
*on,
you can shave off a few clocks here and there, which really adds up when
done 300K times.
If the rule set is known to lead to sparse configurations, e.g. Life Game with *
*a small
initial pattern, then one can use sparse matrix tricks. That is, to just comput*
*e in
the vicinity of occupied cells. Generally these do not compile as efficiently a*
*s a full
matrix method, because there is more indirect address and branches. However,
one could include both a sparse and full matrix method in the same program, then
convert when the cross-over density is reached.
3.6 What hardware implementations exist for CA?
contributions by:
Dr R W Taylor <r...@ohm.york.ac.uk>
See [?]
The "trick" of the CAM-6 was to encode the rules as a lookup table accessed
by an "address" formed of the states of the neighborhood. For example, one bit
states of cell plus eight neighboors is a 512 possible results. There was also *
*a "rule
compiler" that built the transition table and other computations from a special
programming language.
You might also want to look at [?] which describes a 3D automata engine, com-
putation is performed through the reconfiguration (at a very low level) of the
hardware.
15
3.7 Are there any simulators for CAM?
contributions by:
Don Hopkins <hop...@turing.ac.uk>
Hopkins: I've written a recreational CAM-6 simulator (Toffoli & Margolus's Cel-
lular Automata Machine) and ported it to HyperLook (the user interface develop-
ment system I'm working on at Turing). It displays animated cellular automata
that you can edit in real time with the mouse! And it comes with a free Lava
Lamp!
The Cellular Automata Machine simulator (a SPARC binary with a bunch of
PostScript and data files) and the HyperLook runtime system are now avail-
able for anonymous ftp! HyperLook and the CAM simulator run under Open-
Windows Version 3 on color SPARC workstations. They're available for anony-
mous ftp from turing.com, in the file `pub/CAM.tar.Z', or ftp.uu.net, in the fi*
*le
`packages/NeWS/CAM.tar.Z'. You will also need to retrieve the HyperLook run-
time environment, from the same directory, with the name `HyperLook1.5-runtime.*
*tar.Z'.
There are several text and PostScript files explaining HyperLook, and other Hy-
perLook demos and applications (including SimCity, which I've also ported to
HyperLook). Install and run HyperLook (set your $HLHOME environment vari-
able), uncompress and un-tar `CAM.tar.Z' into a directory, go there, and type
"cam". Press the "Help" key at the buttons and graphics to learn how to work
the user interface.
See also CAM-PC and CAMEX in section 3.
3.8 Are there simulators for self-criticality?
contributions by:
Richard J. Gaylord <gay...@ux1.cso.uiuc.edu>
I have written a program, in Mathematica, for a cellular automaton simulation of
earthquakes, mudslides, avalanches and other `'self-critical" phenomena.
The full article (with words) will be published in my column "Simulating Experi-
ences: Excursions in Programming" in "Mathematica in Education," an outstand-
ing (and inexpensive) newsletter [contact Paul Wellin at <wel...@Sonoma.edu>
for details].
3.9 What about running CA's on parallel or distributed
machines?
contributions by:
Dave Hiebeler <hieb...@Think.COM>
Yes, CA are pretty trivial on massively parallel computers. Especially if you h*
*ave
data parallel software (e.g. CM-Fortran or C* on the Connection Machine), then
16
you just create a virtual processor for each cell, and then have each cell fetc*
*h its
neighbors and do a table-lookup or computation.
If you are not using data parallel software, but instead are using message-pass*
*ing, it
is still pretty simple. I typically partition the 2-D array into a set of "stri*
*pes". E.g.
on a 128-node machine, if I want to run a 1024x1024 array, I give each processor
a 128x8 patch of cells (plus one extra row of boundary condition at the top and
bottom, so actually 128x10 with some redundancy). Each processor updates its
local array, and then exchanges its top and bottom row with its neighbors. So y*
*ou
alternate between a step of computation where you loop over your patch of cells
(lots of work if you have a big patch), and doing 2 sends and 2 receives (hopef*
*ully
pretty quick). Imagine the processors are connected as a ring; you don't need a*
*ny
more connectivity than that (although it's good to have some nice way to dump
data out to disk or a machine for analysis).
Partitioning the array into stripes minimizes the "surface area" of the cell pa*
*tches,
and so minimizes the communication you have to do (if you partitioned it as a
"checkerboard," you'd have more data to exchange with more neighbors). It also
makes your inner loops more efficient, because you have really wide rows to loop
over, instead of a bunch of short rows. It also makes each boundary a contiguous
block of memory, so it's easy to send to its neighbor.
If you have a high overhead for sending, you may want to consider having 2
boundary-rows, and doing a little bit of redundant computation, so that you only
do communication every other step.
In fact, I implemented a CA simulation using a network of Sun workstations using
the above layout, and BSD sockets. Using 16 Suns, I think I had CA code running
about 10-12 times faster than a single Sun. This was a few years ago on Sun
3/50's at RPI. I had grand visions of turning the whole campus into a monster
CA simulation environment, but shortly after that, I got access to a CM-2 and
forgot about the Suns. :-) Actually, there's no need to stay on Suns only - you
could have some other machines in there as well, as long as they can do socket
communication to exchange data with the neighbors.
4 Applications
4.1 What computations can CA do?
contributions by:
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.
17
4.2 How do you do computations with the Game of Life?
contributions by:
Chris Langton <c...@t13.lanl.gov>
The constructive proof that the game of life is capable of supporting universal
computation is built around colliding glider streams into one another. collidi*
*ng
glider streams form the basic AND, OR, and NOT gates, out of which one then
goes on to engineer a general purpose computer. However, one need not construct
a general purpose computer, one could arrange the same computational primitives
into a device that computes only a specific function.
One example, computing the logical NOT of a byte, is straightforward. Arrange
for a stream of gliders (the input stream) to collide with the output of a glid*
*er
gun at right-angles in such a way that the gliders in the input stream occur wi*
*th
the same spacing as the gliders coming from the glider gun. Furthermore, time
the arrival of gliders in the input stream so that they collide with gliders in*
* the
output of the glider gun and annihilate each other. Then, encode the byte you
want to compute the logical NOT of in the following way: For every 0 in the inp*
*ut
byte, remove a glider from the input stream, for every 1, leave a glider. Thus,*
* the
input byte 10110010 will be represented by the glider stream:
glider noglider glider glider noglider noglider glider noglider
where the "nogliders" are spots where gliders in a regular periodic stream of g*
*liders
have been removed.
When this stream is collided into the regular stream of gliders coming out of a
glider gun, observe what happens. For every 0 in the input byte, the missing gl*
*ider
in the input stream allows a glider from the glider gun to pass, whereas for ev*
*ery
1 in the input byte, a glider in the input stream annihilates the corresponding
glider coming from the glider gun. Thus, looking at the output stream from the
glider-gun DOWNSTREAM of the collision site, there is a glider (a 1) for every
"hole" in the input stream (a 0) and there is a hole (a 0) for every glider (1)*
* in
the input stream. Thus, the filtered output of the glider-gun is the logical NOT
of the encoded input stream.
And not a universal computer in sight!
By colliding this output stream (call it NOT A if the input steam is A) with
another input stream, B, one gets A AND B in the continuation of the input
stream B after the collision site. If one collides the downstream portion of t*
*he
NOT A stream from this latter gate with the output of another glider gun, one
obtains A OR B as the continuation of the second glider gun output downstream
of the collision.
By hooking up a sequence of AND, OR, and NOT gates built in this way, one can
compute any function that can be expressed by these logical operations (a great
many functions indeed....;-)
For complex functions, involving many gates, one needs to cross glider streams,
redirect glider streams, and so forth. This leads to more complication. However,
18
the basic idea is as sketched out above.
For details, see the classic [?] which contains the proof that the game of Lif*
*e is
computation universal.
4.3 Can CA be used to model ecological systems?
contributions by:
Matthew Burke <bu...@delta.math.wsu.edu>
Recently there has been a significant increase in the number of articles that d*
*eal
with cellular automata (CA) and ecological modeling. There are also several
questions on how various aspects of CA affect their usefulness in ecological mo*
*dels.
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. [?*
*],
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 sh*
*own
that changing the definition of a CA to allow for asynchronous updating of cells
can dramatically alter the behavior of the CA [?] [?]. In particular, frequen*
*tly
the interesting structure seen in the evolution of a CA is, in fact, an artifac*
*t of
the synchronous updating.
What needs to be addressed is whether or not there are ecological systems for w*
*hich
universal updating is not an unwarranted assumption. For example, [?] 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 inconceiv*
*able 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, [?] 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 t*
*hat
synchronous updating is reasonable in this situation.
Another issue that needs to be investigated is the problems associated with mul-
tiple scales, both spatial and temporal. Typically CA models are developed with
the assumption that a cell is a physical region of the right size for one (or, *
*per-
haps, a few) individuals. Consider a model of plankton in the Celtic Sea (I hav*
*e,
which is why I bring it up). If we assume that over a certain horizontal distan*
*ce,
conditions are homogeneous, it suffices to limit ourselves to a water column, i*
*.e.
we only need one spatial dimension. At typical concentrations (private commu-
nication 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 diffus*
*ion
of plankton nutrients (such as nitrate) is even smaller. Also, consider three t*
*yp-
ical organisms: cyanobacteria, flagellates, diatoms, and copepods. The ratio *
*of
the fastest sinking rate to the slowest is 200:1. Thus, if we use this informa*
*tion
19
to scale spatially or temporally, we also run into difficulties (again, the tem*
*poral
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.
References
[?] [?] [?] [?] [?] [?] [?] [?] [?] [?]
4.4 The Universe as a Cellular Automata?
contributions by:
Chris Langton c...@t13.Lanl.GOV
There is a great collection of papers [?]. These are the proceedings of a confe*
*rence
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 (oscillator*
*s)
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 asp*
*ects
of the physical universe or in the physics of computation.
4.5 Can CA be used to encrypt messages?
Yes. For a review see: [?].
References
[?] [?] [?] [?] [?] [?] [?] [?]
5 Special Types of CA
5.1 What are Lattice Gas Automata?
contributions by:
20
Paul Larson <pala...@dal.mobil.com>
Bruce Boghosian <b...@Think.COM>
References: [?] [?] [?] [?] [?] [?]
5.1.1 Does the lack of symmetry in the HPP model have any obvious
bad effect, other than to remove the inertial term?
contributions by:
Bruce Boghosian <b...@Think.COM>
I don't think it removes the inertial term. There is still a form of the inerti*
*al term
with HPP, though it is not isotropic. And, yes, it does have another effect on *
*the
equation: The viscous term, like the inertial term, is present but anisotropic.
5.1.2 Are there unphysical conservation laws with HPP?
contributions by:
Bruce Boghosian <b...@Think.COM>
Yes, HPP has several unphysical conservation laws. First, if you color the sit*
*es
white and black, like a checkerboard, you can convince yourself that the dynami*
*cs
on the white squares are completely independent of the dynamics on the black
squares. Thus, all conserved quantities (mass and momentum) are conserved
*separately* on the two checkerboard sublattices. More seriously, y-momentum
is conserved separately within each column, and x-momentum is conserved sepa-
rately within each row (assuming periodic b.c.'s).
5.1.3 What are the physical manifestations of anisotropy?
contributions by:
Bruce Boghosian <b...@Think.COM>
Here is a physical manifestation of the problem of anisotropy: If you tried to *
*do a
Poiseuille flow simulation with HPP, you would find that the drag on the plates
depended on the angle of orientation of the plates with respect to the underlyi*
*ng
lattice. This problem would be present even at low Reynolds number. With FHP,
on the other hand, the drag would be independent of this orientation.
5.2 What are continuous spatial CA?
contributions by:
Bruce MacLennan <macl...@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 in*
*formal
21
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
5.3 Where can I read about the Gacs rule?
contributions by:
Lenore Levine <lev...@symcom.math.uiuc.edu>
The first paper on the Gacs rule was published in Problems of Transmission of
Information, in 1978. The Russian journal has been translated into English. The*
*re
are two co-authors, Kurdyumov and Levin.
Here are a few later papers that are probably related: [?] [?] [?] [?] [?]
One piece of further work is this: [?]
Some related papers:
[?]; this is Gray's proof of ergodicity for continuous-time monotonic nearest-
neighbor rules.
[?]; this is Gray's proof for discrete time.
[?] This is a relatively simple proof of Toom's rule.
[?] This is my Gacs' 1 dimensional construction.
[?] This is a 2-dimensional construction which may help understanding the diffi*
*cult
1-dimensional paper and has a little more general discussion.
5.4 What's the Hodge Rule?
contributions by:
J"org Heitk"otter <jo...@ls11.informatik.uni-dortmund.de>
HODGE-C is a (`mostly ANSI') C language implementation of Gerhard & Schus-
ter's hodge-podge machine. It implements a class of cellular automata, that res*
*em-
ble very closely autocatalytic chemical reactions, like for example, the Belous*
*ov-
Zhabotinskii (BZ) reaction. It's available via anonymous ftp from lumpi.informa*
*tik.uni-
dortmunde.de:`/pub/CA/src/hodge-c-0.98j.tar.Z'
References
BZ specific publications:
[?] [?] [?]
General CA: [?] [?]
Introductory books: [?] [?]
5.5 What are some good references on Eater Rules?
contributions by:
22
Harold McIntosh <mcin...@redvax1.dgsca.unam.mx>
[?] [?] [?] [?] [?] [?] [?] [?] [?]
5.6 What are Vants?
contributions by:
John N. Rachlin <rac...@cs.jhu.edu>
Charles F. Wells <cf...@po.CWRU.Edu>
A Fraser <A.Fr...@eee.salford.ac.uk>
The Vant rule, by Chris Langton, describes the path of an ant who starts pointi*
*ng
in a certain direction. If the ant is on a non-white square it turns the square*
* red,
rotates 90 degrees clockwise and moves one pixel in the direction it is pointin*
*g. If
it is on a red square it turns the square white, rotates 90 degrees countercloc*
*kwise
and moves one pixel in the direction it is pointing.
See: [?]
5.6.1 some vant simulators
Langtons_Ants by John N. Rachlin <rac...@cs.jhu.edu>
description: This program is based on "Langton's Automaton" and demonstrates
the complex patterns of one or more "ants" moving according to simple user-
defined rules.
requirements: This Program was written in Turbo Pascal, ver. 6.0 It requires
EGA or VGA graphics.
Quick Basic Vants Description: This program implements Chris Langton's
cellular automaton [?]
requirements: This is a QBasic program that can be run on any DOS machine with
VGA graphics. It was written by Charles Wells, Department of Mathematics, Case
Western Reserve University, Cleveland, OH 44106-7058, USA. <cf...@po.cwru.edu.>
Virtual Ants in C Borland C port of above by <A.Fr...@eee.salford.ac.uk>.
6 Properties of CA
6.1 What is Flocking Behavior in CA?
contributions by:
Rudy Rucker ruc...@sjsumcs.SJSU.EDU
The canonical flocking paper is [?]
23
6.2 What about basins of attraction for CA?
contributions by:
Harold McIntosh <mcin...@redvax1.dgsca.unam.mx>
References
[?]
[?] [?] [?] [?] [?] [?] [?] [?] [?] [?] [?]
6.3 What are "inhomogeneous" CA?
contributions by:
Ron Bartlett bart...@memstvx1.memst.edu
Paulo Sergio Panse Silveira <silv...@fox.cce.usp.br>
Andrew Wuensche <10002...@compuserve.com>
When each cell has a different rule, the resulting CA is called "inhomogeneous".
Kauffman's "random Boolean network" model allows different rules AND connec-
tions, with applications in theoretical biology.
[?] discusses intermediate architectures between CA and random Boolean net-
works. Homogeneous rules - varying degrees of random wiring, homogeneous
wiring template - various degrees of rule mix.
[?]: structurally dynamic CA.
References
[?] [?] [?] [?]. [?] [?] [?]
6.4 How important is Synchronicity in CA?
contributions by:
Bill Tozier <wto...@mail.sas.upenn.edu>
Shan Duncan <dun...@loris.cisab.indiana.edu>
Joel Rahn <RA...@vm1.ulaval.ca>
Erik Winfree <win...@druggist.gg.caltech.edu>
Jordan B Pollack <pol...@dendrite.cis.ohio-state.edu>
Cellular automata are discrete, regular, and synchronous. Those interested in
cellular automata as such begin with the CA definition and work to discover the
implications of these properties. Those interested in using CA as models in the
natural sciences, on the other hand, begin with a natural system in mind and
work to discover how well the behavior of their system can be approximated by
a CA model. Both those interested in abstract properties of CA and those inter-
ested in applications find discreteness and regularity uncontroversial compared*
* to
synchronicity. Many of the unique features of cellular automaton dynamics can
24
be traced to the synchronous update of cell-states. An abstract of some of the
discussion on this matters follows.
An example of the importance of synchronicity in CA dynamics is the work of
Chate and Manneville [?] on collective behavior in CA and coupled-map lattices.
This behavior is of major importance in the field of dynamical systems. Indeed,
before this work appeared, some had "proved" (in the physicists sense of proof)
that such behavior was impossible. Collective behavior seems to be stable to all
sorts of perturbations of the model except giving up on synchronous updates.
The paper by Huberman and Glance [?] supports the opinion that the organization
of the subunits in a model must approximate the organization of the subunits
in the system to be modeled, and the dynamics of the model must be a good
approximation of the dynamics in the real world. [not always the case for CA]
For some examples of CA models in the natural sciences which "work" see Ermen-
trout and Leah Edelstein-Keshet [?] and the section on lattice-gas automata.
An early reference: [?] They investigate Wolfram's CA rules using a probabilist*
*ic
method for updating cells. Some of the rules give patterns, some don't. From the
Abstract: "...some of the apparent self-organization of (CA) is an artifact of *
*the
synchronization of the clocks."
Greenberg-Hastings type models of reaction-diffusion systems do a decent job of
arriving at the same qualitative spatial structure as the real phenomenon (e.g.
Zhabotinsky reaction), in this case stable rotating spirals of activity. Howev*
*er,
if the Greenberg-Hastings model is executed with asynchronous update, mayhem
breaks loose; rather than, say, one stable spiral, the spiral fractures into a *
*thousand
jumbly pieces.
Thus, synchronous and asynchronous update schemes may lead to vastly different
results, and a modeler must be careful in using either one. But the real issue*
* is
is not at all new - modelers must be explicit about what assumptions they make
when designing a model. In CA, conserved quantities and conserved properties
of the system have vast consequences on its subsequent evolution, and must be
carefully analyzed.
For example, in the Greenberg-Hastings model, a conserved quantity is that the
winding number of every closed path remains unchanged over the course of the
evolution. This property is also true for simple PDE models of excitable media.
(In more complicated versions of both models, unfortunately, this breaks down in
some cases.) But the point is that the CA model is decent because the conserved
properties of its evolution are right. For G-H, single local applications of th*
*e CA
rule may not preserve the conservation law, and thus a radically different stea*
*dy-
state is seen in asynchronous simulations.
In the neural network community there is the same sort of concerns with regard *
*to
synchronicity of updates. People implementing parallel machines are interested *
*in
synchronized systems, while others whose models depend on a sequential update
rule will argue from the biological plausibility of asynchronousness.
A typical "biological plausibility" statement is found in Daniel Amit's book mo*
*d-
25
eling brain function (p. 80):
to reiterate, the asymptotic behavior of the network, on which we focus
our interest, may depend on the dynamical procedure, but such de-
pendence is unwarranted because no particular procedure is a faithful
representation of the activity in the biological network. We therefore
look for asymptotic properties which are insensitive to the updating
procedures
6.5 Which computations can 1D CA perform?
contributions by:
Peter Ruff <rzu...@rz.uni-wuerzburg.de>
Ruff: I have set up a 1d2n22s CA which performs binary multiplication by 79
transition rules. Result of n * m digits is available after maximal n + m + 2 s*
*teps.
6.6 Is there is universal 1D CA?
contributions by:
Mark A Biggar <m...@wdl39.wdl.loral.com>
Rudy Rucker <ru...@autodesk.com>
Biggar: Sure if you allow for more then 2 states and/or neighborhoods greater
then 3 wide.
First I work with more then 2 states and then with wide neighbor hoods.
Suppose that you have a N state M symbol Turning machine, this maps to a
1D (N+1)*M state 3 wide neighbor hood as follows: M of the states correspond
to tape squares were thr turning machine read/write head is not located and are
direct mapping of the turning machine's tape. The other N*M states represent the
tape square where where the read/write head is located. A state at that position
represents the tape has one of the allowed symbols and the machine is in a given
state giving N*M possibilities. Using a width 3 neighborhood then most cells are
quiescent and don't change only the three cells with on of the M*N states in th*
*eir
neighborhood can change in a given time. Defining the rules based on the origin*
*al
turning machine is obvious.
Now if you start with a Universial Turning machine you end with a Universal
Automata.
w to go back to a Binary Automata. If I have N states in the above Automata
it can be easily mapped to a binary automata with a neighbor hood of width
4*N+11 as follows: For now assume that there are only 4 state (to make the cases
to be examined small) the each cell in the 4 state 1D automata will map to a row
of 9 cells like so:
26
state 10 cell pattern
0 110000011
1 110100011
2 110010011
3 110001011
These patterns will overlap 1 cel on each end so the turning tape : :1:02 : :w:*
*ould
be represented as:
: :1:11010001110000011100100111 : : :
Using a 27 cell neighborhood it is easy to define rules that correspond to the
original 4 state automata. the 111's in the pattern act as registration marks
the other cells can determine which position they are in. The original set up *
*of
the 1D automata does not need the registration marks already in place out to
infinity they can propogte themselves out automatically and keep ahead of the
non-empty part of the tape with ease. More compact coding are possible, but this
one is wasly to explain and gives a automata that runs at the same speed as the
original.
There is a 4 symbol 7 state Univ Turing machine described in "Computation:
Finite and Infinite Machines" by Minsky.
Rucker: It is pretty simple to model a standard turing machine as a 1d CA. If
the TM uses k symbols and n states, then you can make a 1d CA with k * (n + 1)
states per cell. Most cells are in the state i,0 for some i < k. The cell where*
* the
"head" resides is in the state i,j for some i < k and 1 < j <= n. The update ru*
*le
is for each cell to stay the same unless the cell is where the "head" is or is *
*a cell
that the "head" is about to move into.
References
[?] [?]
6.7 How to perform computations in the Game of Life?
contributions by:
Wentian Li <w...@cshl.org>
McIntosh Harold V.-UAP <mcin...@redvax1.dgsca.unam.mx>
Using the interaction of glider streams, the Game of Life can be programmed to
perform computations. Indeed, it is a universal computer.
References
[?] [?]
27
6.7.1 Must one use all of the logical gates to perform computations in
the Game of Life?
See: [?]
the three logical gates AND, OR, NOT are sufficient for all logical functions,
but not necessary. not only two basic gates are enough, one basic gate is also
enough! for example, gate NAND, which is "negation of AND," can lead to all
three previously considered "basic" gates:
NOT(a) = (a NAND a)
AND(a,b) = (a NAND b) NAND (a NAND b)
OR(a,b) = (a NAND a) NAND (b NAND b)
another example is the NOR (negation of OR):
NOT(a) = (a NOR a)
OR(a,b) = (a NOR b) NOR (a NOR b)
AND(a,b) = (a NOR a) NOR (b NOR b)
the relevance to CA/Game of Life is that the requirement for having three logic*
*al
gates in a CA rule so that it can do all computations can be (two) too much. at
least in principle, having one NAND should be enough for constructing all logic*
*al
functions.
6.8 Where can I learn about Spaceships in the Game of
Life?
contributions by:
Bruce Stangeland <tb...@rrc.chevron.com>
See "Spaceships in Conway's Life" by David I. Bell <db...@pdact.pd.necisa.oz.au*
*>.
Texinfo version of above by J"org Heitk"otter <jo...@ls11.informatik.uni-dortmun*
*d.de>
in the CA archives at think.com.
There have also been a series of articles on CA that have appeared in Scientific
American, in the Computer Recreations section. See, for example: 10/70, 8/88,
8/89, 9/89, and 1/90.
6.9 What about running a CA backwards?
contributions by:
Lyman Hurd <hu...@math.gatech.edu>
6.9.1 The General Case
I will assume that a "configuration" comprises a N x N square of symbols 0,1 wi*
*th
the sites outside of this square assumed 0 (this is what I would term a "finite"
configuration.
One can ask:
28
1. Is there a configuration which maps onto this configuration?
2. Is there a finite configuration which maps onto this configuration?
In one-dimension there are much-explored algorithms which answer to both ques-
tions. Fundamental to the algorithm is the existence of bounds based on the
parameters of the CA rule (specifically the states per site and number of sites
distant the rule takes into account, Wolfram's k and r). Based on these one fin*
*ds
a bound phi(N) (recaall N is the initial size of our finite neighborhood) for w*
*hich
if there is any finite predecessor, there must be one of length at most phi(N).*
* The
first question is slightly more complicated, but the procedure is similar.
In two dimensions both questions are undecidable. This means that the function
phi while it still exists abstractly (there are still a finite number of rules *
*with a
given k and r), grows faster than any recursive function.
The proofs of the above statements are not difficult, and relate to the undecid-
ability of the tiling problem for Wang tiles.
Note that none of the above discussion means that the problem cannot be solved
in the specific case of the game of Life. It would be impressive to demonstrate*
* such
a technique, as Life is sufficiently complicated to be computationally universa*
*l.
6.10 What are some reversible rules?
contributions by:
Bruno Durand <bdu...@ens-lyon.fr>
The following reversible cellular automaton has been presented by Jarkko Kari.
It has 2 neighbors (the cell itself and its right neighbor). The set of states*
* is
1,2,: :,:n. The local transition rule f:
f(a; b)= a ifb <= a
1 ifb = a + 1
a + 1 ifb > a + 1
6.11 What is known about periodic orbits in CA?
contributions by:
Lyman Hurd <hu...@math.gatech.edu>
John Pedersen <j...@goedel.math.usf.edu>
Hurd: In a recent paper I used the terms temporally and spatially periodic, but
informally I sometimes just say horizontally or vertically periodic. Here is a*
*n (I
think) interesting result:
Assume that a 1-d CA has a quiescent state. I will (informally) call a configur*
*ation
"trivial" if it evolves to the all-quiescent state which I will assume is a fix*
*ed point.
A CA for which ALL configurations are trivial, will be called nilpotent.
29
1) A CA has a non-trivial temporally periodic orbit if and only if it has a non-
trivial spatially periodic orbit (one half of this proof is easy).
2) There exists a cellular automaton for which EVERY periodic (spatially or tem-
porally, equivalent by (1)) orbit is trivial BUT for which not every configurat*
*ion
is trivial.
This example (OK I did not give an example I just stated it exists_in fact Kari,
Culik and I have a specific example with 17 states) means that there can be
dynamics missed entirely by the restriction to spatially periodic configuration*
*s no
matter what the finite lattice size.
PART II:
The following proof is due to K. Culik. To show that a finite configuration must
have an (eventually) periodic predecessor, if it has a predecessor at all, cons*
*ider
the following state:
Assume that the rule has radius one (the proof goes through in general with
obvious modifications). Denote by k the number of states per site.
c = : :0:00c0c1: :c:N0000 : : :
has a predecessor:
d = : :d:-2d-1d0d1d2: : :
Lining them up:
d = : :d:-2d-1d0d1d2: :d:NdN + 1 : : :
c = : :0:0c0c1c2: :c:N0000 : : :
Consider a window which is two high and three wide (if R is the radius, 2R+1),
sliding over the pair of configurations. Start with:
dN+1 dN+2 dN+3
0 0 0
and continue to the right. There are only k3 possible values so at SOME point
the list must have a duplicate, i.e.,
dN+idN+i+1dN+i+2 = dN+j dN+j+1 dN+j+2
0 0 0 0 0 0
Now we can replace d with a configuration periodic on the right by defining:
d0n= dn if n < dN+j ;
and otherwise
d0n= d0n-(j-i)
A similar trick works on the left and QED. The same technique shows the stronger
result (of Golze) that periodic configurations must have periodic predecessors.
See also: [?] which derives algebraic conditions for all orbits a CA being peri*
*odic.
6.12 What are Subshifts of Finite Type/Sophic Systems?
contributions by:
Mike Boyle <bo...@msri.org>
Historically the study of SFT's got a lot of impetus from hyperbolic dynamics,
where SFT's are the natural symbolic dynamics for making use of Markov parti-
30
tions. You can do a lot of your analysis of equilibrium states and periodic poi*
*nts
on the SFT. (The analysis of equilibrium states on sofic shifts is much harder.)
This is an historical reason for the focus on SFT's but it is also a mathematic*
*al
one. It is completely reasonable on mathematical grounds that SFT's should be
distinguished as the most important subclass of sofic systems. It is for SFT's *
*that
finiteness conditions, coding constructions and algebraic invariants are most t*
*rans-
parent; and one key to studying a sofic system is to understand how its propert*
*ies
relate to those of the SFT underlying the minimal deterministic finite automaton
for the regular language of the sofic system.
But: I think Prof. McIntosh's consideration of sofic systems as a fundamental c*
*lass
is absolutely correct. It is in various ways a more natural class than the clas*
*s of
SFT's. For example, it is closed under quotients and unions. More fundamentally,
it is much more naturally "the" class of subshifts with a finite presentation t*
*han are
SFT's. I think this represents the consensus among workers in symbolic dynamics.
Prof. McIntosh's interest in sofic systems is especially gratifying to me, as I*
* work
in symbolic dynamics myself and have formed the impression that most workers
in cellular automata regard even SFT's which are not full shifts as esoterica. *
* It
seems to me that symbolic dynamics provides at the least tools and a perspective
useful for some problems about automata, but these have not been much used in
c.a.
Just one example: from the symbolic viewpoint the c.a. insistence that its au-
tomata be block codes on full shifts (versus block codes on SFT's or other sub-
shifts) seems unnatural. The latter viewpoint finds some justification in the r*
*ecent
work of Alejandro Maass <a...@lumimath.univ-mrs.fr>. He uses techniques of
symbolic dynamics to show that any endomorphism f of a mixing SFT S is the
restriction of some c.a. map which has image S, under the necessary assumption
that S has a fixed point. (He also has more sophisticated and less easily stat*
*ed
results about c.a. limit sets and dynamics.) In other words, to understand the
limit dynamics of c.a., you must understand the limit dynamics of endomorphisms
of SFT's.
This is not just a problem, it is also an opportunity, because tools for studyi*
*ng
SFT's can contribute some understanding.
6.13 What is the mean field theory?
The mean field theory is a way of approximating the action of a CA by a map
with continuous parameters. The approximation is derived by assuming that the
states of cells at different locations in space are not correlated. A simple ve*
*rsion
of the mean field theory is the ~ parameter of Langton, more general versions,
which take into acount spatial correlations, have also been developed.
references
[?] [?] [?] [?] [?]
31
6.14 When is a CA injective, surjective?
contributions by:
Lyman Hurd <hu...@math.gatech.edu>
A CA is injective if its global function F satisfies F (x) = F (y) implies x = *
*y. This,
of course, is the general definition for functions. In the case of CA a stronge*
*r result
holds (reference?).
Theorem A CA is injective if and only if it is reversible (i.e., bijective).
Surjectivity for cellular automata (although not in general) is a strictly weak*
*er
condition that for all y there exists x such that F (x) = y.
For 1-dimensional CA there exist well-known algorithms to determine surjectiv-
ity and injectivity (by an algorithm is meant, you hand it a rule table and in
guaranteed finite time the answer comes back for all possible 1D CA).
In 2 and more dimensions a highly non-trivial result of Jarkko Kari shows that
the question is undecidable. The question is linked in a deep way with Berger's
Theorem about the undecidability of tiling by Wang tiles.
It is trivially verifiable when two rules invert each other. Kari's Theorem th*
*en
implies that there must exist 2D rules for which the complexity of describing i*
*ts
inverse vastly exceeds the complexity of the rule itself. If we take r (the rad*
*ius)
and a rough determinant of complexity, for any recursive function phi, there mu*
*st
exist a rule with radius r whose inverse rule has radius greater than phi(r).
6.15 Can one decide if a 2D rule is reversible/surjective?
contributions by:
Lyman Hurd <hu...@math.gatech.edu>
Jarkko Kari has proven that the reversibility question for 2D or higher CA is
undecidable. It is true in all dimesions that a rule is reversible if and only*
* if it
is injective. Kari also has proven that the surjectivity problem is undecidable*
* (a
necessary but not sufficient condition for reversibility).
As he points out, the two questions are somewhat different. In the case of surj*
*ec-
tivity one can demonstrate its lack by giving a finite configuration which one *
*can
test exhaustively cannot be reached. This provides a semi-procedure even though
no corresponding semi-procedure can be found in the other case. On the other
hand, it can be finitely demonstrated that two rules indeed invert one another,*
* so
there is a semi-procedure to show that a CA IS reversible.
One way to show decidability in the 1D case for both questions consists of prov*
*ing
recursive bounds on how big a string one would need to find to show a counterex-
ample to surjectivity or how large a radius rule one needs to examine to prove
reversibility. In both cases such a bound (as a function of the number of stat*
*es
per site and radius) exist, although I do not recall their exact form (I used to
know, step in anyone who remembers). Kari's proffs suffice to say that there is*
* no
such recursive bound for 2 or more dimensions.
32
6.16 Where do I read about reversible cellular automata?
contributions by:
Harold V. McIntosh <mcin...@uapnx1.dgsca.unam.mx>
The name most prominently associated with reversible cellular automata seems to
be Tommaso Toffoli; his most accessible work is probably [?]. Whereas the book
describes a number of reversible rules for the CAM-6, Edward Fredkin's analogy
with second order differential equations is the only background theory mentione*
*d,
in section 14.2. The Margolus neighborhood, strongly featured in the book, was
evidently created to facilitate reversibility.
In turn, Fredkin has acquired widespread fame for the replication properties of
the <exclusive or> when taken as a rule of evolution. However, it is difficult*
* to
encounter a single reference which can be cited, for either Toffoli or Fredkin,*
* that
can be fairly said to present their own views. Martin Gardner reported Fredkin's
replication in his second article on Life in 1971, reprinted in [?] thereby giv*
*ing the
idea worldwide publicity.
Perhaps the computer science community's outstanding early contact with re-
versible automata was [?]. Non-reversibility, in the form of the Garden of Eden,
seems to go back to [?]. What seems to be quite remarkable is the degree to whi*
*ch
such issues were worked out by mathematicians, within the context of symbolic
dynamics, during the 1950's and 1960's. The fundamental paper in this respect is
[?].
It is in fact a summary of quite a bit of work, carried out by Hedlund himself
and others. One of their important concepts is a "subshift of finite type" which
is a biinfinite string of symbols from which a certain finite set of words has *
*been
excluded. Sort of like excluding all the 1's from trinary (i.e., 0, 1, 2) decim*
*als to
get the Cantor set. Shifting the decimal point in one such number gives another.
Topology figures very strongly in symbolic dynamics, which may have restricted
its appreciation; on the other hand it facilitates talking about limits and lea*
*ds to
a useful measure theory and probabilities. The topology is such that two strings
are closer, the longer their central segments which match up; it turns out that
those continuous functions which commute with the shift are each generated by
the transition rule for some linear cellular automaton. Thus symbolic dynamics
is an application of automata theory, or vice versa. The two theories overlap, *
*but
have tended to emphasize different features. Would a symbolic dynamicist have
discovered Wolfram's class iv on his/her own?
Subshifts of finite type arise from graphs whose nodes are symbols and whose
arrows show admissible sequences; missing arrows result from the operative excl*
*u-
sions. Someone realized that a much more interesting model resulted from using
the symbols as links among arbitrary nodes; the publication generally credited *
*for
this is [?]. It should be noted that the language of his presentation is semigr*
*oup
theory, not graph theory.
Three papers by Ethan M. Coven and Michael E. Paul come from the same time
33
period: [?] [?] [?].
Several articles by Masakazu Nasu, written in the spirit of Hedlund's symbolic
dynamics, appeared in the late 70's and early 80's; perhaps the most relevant i*
*s:
[[?]. Somewhat later the ideas were generalized to apply to flows through graph*
*s:
[?].
An early attempt to relate reversibility and Gardens of Eden and to use the int*
*er-
play between global and local mappings was [?].
A somewhat later paper [?] works out in considerable detail the relationships
between injectivity, surjectivity, and several other properties of cellular aut*
*omata.
Slightly earlier, [?] appeared.
The reasons for interest in reversible automata seem to have been varied. A for*
*mal
theory such as Hedlund's would naturally have been concerned with the kind of
details represented by surjectivity, injectivity, continuity, the existence of *
*limits,
and so on; all of his results may well have been worked out simply for the sake
of presenting a thorough and complete theory. One would have to ask him, or
someone who was very familiar with his work.
Garden of Eden theorems seem to have resulted more as a counterbalance to
von Neumann's universal constructor; the reversible machines which they imply
seem to have been less of an issue than the fact that some specific automata we*
*re
<<not>> reversible, and the momentary confusion between the implications of the
two concepts. Consequently Toffoli seems to be a plausible candidate to have be*
*en
the first proponent of reversible automata as such.
His publications are not all that easy to track down, consisting of his thesis,*
* lab-
oratory reports, contributions to conference proceedings, and so on. However, [*
*?]
states that "an arbitrary d-dimensional cellular automaton can be constructively
embedded in a reversible one having d + 1 dimensions," and precedes to show how
to do so. This approach is different from Fredkin's, which merely uses an arbit*
*rary
cellular automaton to construct another which is reversible, without pretending
to embed the original; indeed it usually does not. There is also a joint paper,*
* [?]
which goes into some of their mutual ideas.
34