ca-faq.tex
Howard GUTOWITZ
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
\documentstyle[12pt,paper]{article}
\parindent=0pt
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%% MACROS
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
%% some LaTeX macros that make life easier, and look just ``beautiful'' (-joke)
%%
\def\host#1{%
{\bf #1}%
}
\def\file#1{%
{`{\tt #1}'}%
}
%% cf Internet RFC 822 for ``typographical'' e-mail conventions
\def\email#1{%
{\tt <#1>}%
}
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%% THE FAQ
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\begin{document}
\title{Frequently Asked Questions \\
About Cellular Automata}
\author{Contributions \\
from the CA community \\
edited by \\
{\em Howard Gutowitz} \\
\email{h...@santafe.edu}
}
\date{December 8, 1993}
\maketitle
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%% ABSTRACT
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\begin{abstract}
The FAQ has taken a great leap forward thanks to
the contributions of many individuals.
Special thanks due to
J\"org Heitk\"otter
\email{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 \ref{sec:biblio}).
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 \email{h...@santafe.edu}.
\end{abstract}
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%% TABLE OF CONTENTS
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\newpage
\tableofcontents
%%\parskip=0.5\baselineskip %% -joke 28/10/93
\newpage
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%% HERE WE GO!
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\newpage
\section{What are Cellular Automata (CA)?}
\centerline{contributions by:}
\centerline{Lyman Hurd \email{hu...@math.gatech.edu}}
\bigskip
Here is one physicist's view of the relevant definitions:
\bigskip
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 lattice 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 updated synchronously. Thus the
state of the entire lattice advances in discrete time steps.
\bigskip
Here is one mathematician's view of the relevant definitions:
\bigskip
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 $S^Z$ (Z=integers, infinite in both positive and negative
directions) where S is a finite set of k elements. The dynamics are
determined by a global function
\begin{equation}
F: S^Z \longrightarrow S^Z
\end{equation}
whose dynamics are determined ``locally'' as defined below.
A ``local (or neighborhood) function'' f is defined on a finite region
\begin{equation}
f: S^{2r+1} \longrightarrow S.
\end{equation}
The all-important property of cellular automata, is that this function
is determined by a finite lookup table. Both the domain and range of
f are finite.
The global function F arises from f by defining:
\begin{equation}
F(c)_i = f(c_{i-r},\dots,c_{i+r}).
\end{equation}
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 its two neighbors (Wolfram's elementary rule 90).
Some relevant facts from a topological standpoint are:
\begin{enumerate}
\item
The base space $S^Z$ is compact and the global function F is
continuous.
To insert an editorial comment, this makes CA an ideal meeting point
between continuous dynamics and complexity theory, since they are
discretely defined but exhibit continuous dynamics.
\item
The map F commutes with the shift operator which takes $c_i$ to
$c_{i+1}$.
\end{enumerate}
In fact cellular automata are characterized completely by properties
1) and 2) (Hedlund).
The transition to more dimensions is straightforward. The only
difference is that the global function F is defined over $S^{Z^d}$
(functions from a d-dimensional lattice to S) and the local function f
is determined by enumerating the image of all patches of size
$2^{{r+1}^d}$.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\section{General Information}
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsection{How can I get the latest FAQ?}
\centerline{contributions by:}
\centerline{Bruce Boghosian \email{b...@Think.COM}}
\bigskip
The FAQ will be available by anonymous FTP at \host{think.com}.
It will be cross-posted to comp.answers, and santafe.edu will
serve as a mirror site.
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
\subsection{How do I process the CA FAQ?}
\centerline{contributions by:}
\centerline{Joerg Heitkoetter \email{heit...@lusty.informatik.uni-dortmund.de}}
\centerline{James Kennedy CSMR x6238 \email{JI...@RCC.RTI.ORG}}
\bigskip
The CA FAQ is configurable for US letter size and standard A4 paper sizes;
it also comes with a Makefile included. All there is to do, is
(1) unpack the ca-faq.tar :
(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 default);
The makefile will take care of bibtex'ing, and will strip off
the latex commands, if you so desire.
\subsection{How do I contribute bibliographic material to the FAQ?}
\label{sec:biblio}
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.:
\host{ftp.informatik.tu-muenchen.de}:
\file{/pub/comp/typesetting/tex/bibview-2.0.tar.Z}. Use
of bibview 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.nameYEAR (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.
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsection{What is the cellular automata mailing list?}
\centerline{contributions by:}
\centerline{Bruce M. Boghosian \email{b...@think.com}}
\bigskip
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:
\cite{wolfram86} \cite{toffoli87} \cite{gutowitz91}
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:
\begin{itemize}
\item
An Internet mailing-list
\item
A Bitnet LISTSERV-maintained mailing-list
\item
The Usenet newsgroup ``comp.theory.cell-automata''
\end{itemize}
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.
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsubsection{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.
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsubsection{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, since 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:
\begin{verbatim}
SUBSCRIBE CA-L Your RealName
\end{verbatim}
You may also send a message containing the line:
\begin{verbatim}
HELP
\end{verbatim}
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
\email{list...@mitvma.mit.edu}.
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsubsection{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 \email{cellular-aut...@think.com} (or
just reply to this message) specifically requesting to be added to the
Internet side of the CA mailing-list, using 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
again.
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsubsection{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
\file{ca.archive*}. Previous years are kept in compressed format, e.g.
\file{ca.archive-1987.Z}. Archives for the current year are not
compressed, and kept in the file \file{ca.archive}.
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsection{What are some good general references for CA?}
\centerline{contributions by:}
\centerline{Mark A Biggar \email{m...@dst17.wdl.loral.com}}
\centerline{John Baez \email{ba...@guitar.ucr.edu}}
\bigskip
\cite{toffoli87} \cite{farmer84} \cite{gutowitz91}
\cite{wuensche92}
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsection{What is the Complex Systems Journal?}
Complex Systems:
A journal devoted to the rapid publication of research on the
science, mathematics, 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).
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\section{Where can I get a CA Simulator?}
\label{sec:simulators}
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\centerline{contributions by:}
\centerline{Russell Inman \email{in...@ceti.csustan.edu}}
\centerline{H.H. Chou \email{hhc...@cs.umd.edu}}
\centerline{ Dana Eckart \email{da...@rucs.santafe.edu}}
\centerline{ Andy Wakelin \email{mct...@uk.ac.dct}}
\centerline{ Harold McIntosh \email{mcin...@redvax1.dgsca.unam.mx}}
\centerline{Rudy Rucker \email{ruc...@sjsumcs.SJSU.EDU}}
\centerline{ Ken Karakotsios \email{kara...@apple.com}}
\centerline{Simone Maggi \email{ma...@c700-2.sm.dsi.unimi.it}}
\bigskip
\subsection{General-Purpose CA Simulators}
General Reference: \cite{hiebeler90}.
\subsubsection{automata}
author: \email{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 programmers create
sophisticated mouse based interfaces.
requirements:
Also central to SUIT design is portability. SUIT programs
currently 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 \host{ftp.cs.umd.edu}: \file{/pub/dtr.tar.Z}
\subsubsection{CALAB}
Autodesk has two free CA programs for the PC compatible machine on
Compuserve. If you can get on Compuserve, enter GO ADESK and go
into Library 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.
\subsubsection{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 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 Margolus 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 curves, and return maps.
availability: Harold V. McIntosh \email{mcin...@redvax1.dgsca.unam.mx}
\subsubsection{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: \host{ftp.cognet.ucla.edu}
\file{ pub/alife/public/cam.zip }
(An alternative site is \host{cogsci.elte.hu} \file{cogsci/alife/CA})
\subsubsection{CART}
description: see
\cite{allinson92}.
requirements: ??
availability: ??
\subsubsection{CELIP}
description: see
\cite{hasselbring90}.
requirements: ??
availability: ??
\subsubsection{Cellsim}
description: built on top of C, also
can use parallel processing
power of a CM-? machine
requirements: UNIX, sunview or X11 (see section \ref{sec:cellsimX} )
availability: plaza.aarnet.edu.au
life.anu.edu.au
think.com
sun.soe.clarkson.edu
sparc01.cc.ncsu.edu
iear.arts.rpi.edu
uceng.uc.edu
bikini.cis.ufl.edu
isy.liu.se
nctuccca.edu.tw
\subsubsection{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-scam; 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 values. 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, than do many other systems.
Requirements:
The current system supports both the X11 and Iris Graphics Library windowing
systems and can generate shared memory multi-threaded code for multi-processor
Sun and SGI (Sequent?) machines.
availability: J Dana Eckart \email{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)
reseq.regent.e-technik.tu-muenchen.de (2.0)
athene.uni-paderborn.de (2.0)
inf.informatik.uni-stuttgart.de (2.0)
usc.edu (2.0)
keos.helsinki.fi (2.0)
irisa.irisa.fr (2.0)
walton.maths.tcd.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)
\subsubsection{CEPROL}
description: see
\cite{seutter85}
requirements: ??
availability: ??
\subsubsection{LCAU}
Description: These programs are
substantially one-dimensional, one each for small integer (and half-integer)
combinations of Wolfram's k and r. Each program covers evolution, probability,
de Bruijn diagrams, and the calculation of ancestors. Copies of the programs
and literature will be sent in response to requests bearing 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 combinations, 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 \email{mcin...@redvax1.dgsca.unam.mx}
\subsubsection{Mathematica}
description: a notebook showing an
array of Cellular Automata
requirements: Mathematica
availability: swdsrv.edvz.univie.ac.at
ra.nrl.navy.mil
\subsubsection{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.it
isfs.kuis.kyoto-u.ac.jp
walhalla.germany.eu.net
lth.se
nctuccca.edu.tw
unix.hensa.ac.uk
\subsubsection{Self-Directed Replicator (?)}
author: Hui-Hsien Chou \email{hhc...@eng.umd.edu}.
description:
{\em Simple Systems Exhibiting Self-Directed Replication:
Transition Functions, Software, and Documentation
March, 1993}
We have recently developed and studied cellular automata models of
self-replicating systems [Science, 259, 1993, pp. 1282-1288].
Files containing a version of the various transition functions
are now available via ftp. The cellular automata software is actually
fairly general and could also serve as an application-independent
simulator. For further details please refer to the paper cited above.
availability: \host{ftp.cs.umd.edu} \file{pub/dtr.tar.Z}
\subsubsection{SimLife}
description: GUI
requirements: UNIX(?) or mac or amiga or PC
availability: in local software store
\subsubsection{SLANG}
description: see
\cite{sieburg91}
requirements: ??
availability: ??
\subsubsection{Wautom}
description: 1-Dimensional elementary binary cellular
automata, with Wolfram's rules 0 to 255.
WAUTOM features: intuitive "Windows"-like user interface,
custom 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/off),
live-cell diagram.
availability: \host{ ghost.dsi.unimi.it}
\file{ /pub2/papers/magi/wautom.zip}
requirements: 286 machine, VGA, {\em necessarily} the MOUSE (or
equivalent pointer); Ms-Dos 3.10 or later.
Ms-Windows NOT required!
\subsection{Simulators for the Game of Life }
\subsubsection{bugglings}
requirements: mac
availability: ??
\subsubsection{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
\subsubsection{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
\subsubsection{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 kara...@apple.com.
\subsubsection{Plife}
requirements: Microsoft Windows on a PC
availability: In the UK at a JANET (Joint Academic NETwork) site.
The file you want is \file{micros/ibmpc/win/a/a035/a035plife.boo}
\subsubsection{3dlife}
availability: \host{life.anu.edu.au}: \
file{/pub/complex\_systems/alife/3DLIFE.ZIP}
\subsubsection{xlife-2.0}
requirements: UNIX, X11
availability: iacrs1.unibe.ch
alice.fmi.uni-passau.de
uxc.cso.uiuc.edu
life.c
requirements: UNIX(?), curses
availability: rs3.hrz.th-darmstadt.de
agate.berkeley.edu
ocf.berkeley.edu
ux1.cso.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
sune.stacken.kth.se
colonsay.dcs.ed.ac.uk
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{Does Cellsim for X exist?}
\label{sec:cellsimX}
\centerline{contributions by:}
\centerline{Dave Hiebeler \email{hieb...@think.com}}
\centerline{Felicity George \email{fa...@uk.ac.ed.epcc}}
\bigskip
{\bf 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 display 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.
{\bf 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.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{What is 3D-Life?}
\centerline{contributions by:}
\centerline{Anthony Wesley \email{awe...@canb.auug.org.au}}
\centerline{Harold V. McIntosh \email{MCIN...@unamvm1.dgsca.unam.mx}}
\centerline{John Pedersen \email{j...@GOEDEL.MATH.USF.EDU.}}
\bigskip
Carter Bays gives a new rule for 3D Life in \cite{bays92}.
The 3dlife program is available for ftp from
\host{life.anu.edu.au}: \file{/pub/complex\_systems/alife/3DLIFE.ZIP}
{\bf References}
\cite{dewdney87} \cite{dewdney88a}
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{How can I make CA simulations run fast?}
\centerline{contributions by:}
\centerline{Rudy Rucker \email{ruc...@sjsumcs.SJSU.EDU}}
\centerline{Richard Ottolini \email{stg...@st.unocal.COM}}
\bigskip
I can think of four main tricks for making a CA program run fast.
\begin{enumerate}
\item
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 precompute the lookup values for all possible
nabecodes before running the CA. Lookups can be saved, as Walker and
I did in CA LAB.
\item
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.
\item
The flywheel. In stepping through the cells of the CA, you repeatedly
compute a cell's nabecode, then compute the nabecode of the next cell
over, and so on. Because the neighborhoods overlap, a lot of the info
in the next cell'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.
\item
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 write this in assembly language, and keep an eye on the listed
``clocks'' per instruction, you can shave off a few clocks here and there,
which really adds up when done 300K times.
\end{enumerate}
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 compute in the vicinity of occupied cells. Generally these
do not compile as efficiently as 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.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{What hardware implementations exist for CA?}
\centerline{contributions by:}
\centerline{ Dr R W Taylor \email{r...@ohm.york.ac.uk}}
\bigskip
See \cite{toffoli87}
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
\cite{howard92}
which describes a 3D automata engine, computation is performed
through the reconfiguration (at a very low level) of the hardware.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{Are there any simulators for CAM?}
\centerline{contributions by:}
\centerline{Don Hopkins \email{hop...@turing.ac.uk}}
\bigskip
{\bf Hopkins:} I've written a recreational CAM-6 simulator
(Toffoli \& Margolus's Cellular Automata Machine)
and ported it to HyperLook (the user
interface development 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
available for anonymous ftp! HyperLook and the CAM simulator run
under OpenWindows Version 3 on color SPARC workstations. They're
available for anonymous ftp from turing.com, in the file
\file{pub/CAM.tar.Z}, or \host{ftp.uu.net}, in the file
\file{packages/NeWS/CAM.tar.Z}.
You will also need to retrieve the HyperLook runtime environment, from
the same directory, with the name \file{HyperLook1.5-runtime.tar.Z}. There
are several text and PostScript files explaining HyperLook, and other
HyperLook demos and applications (including SimCity, which I've also
ported to HyperLook). Install and run HyperLook (set your \$HLHOME
environment variable), uncompress and un-tar \file{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 \ref{sec:simulators}.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{Are there simulators for self-criticality?}
\centerline{contributions by:}
\centerline{Richard J. Gaylord \email{gay...@ux1.cso.uiuc.edu}}
\bigskip
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
Experiences: Excursions in Programming'' in ``Mathematica in Education,'' an
outstanding (and inexpensive) newsletter [contact Paul Wellin at
\email{wel...@Sonoma.edu} for details].
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{What about running CA's on parallel or distributed machines?}
\centerline{contributions by:}
\centerline{Dave Hiebeler \email{hieb...@Think.COM}}
\bigskip
Yes, CA are pretty trivial on massively parallel computers.
Especially if you have data parallel software (e.g. CM-Fortran or C*
on the Connection Machine), then you just create a virtual processor
for each cell, and then have each cell fetch its neighbors and do a
table-lookup or computation.
If you are not using data parallel software, but instead are using
message-passing, it is still pretty simple. I typically partition the
2-D array into a set of ``stripes''. 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 you 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 (hopefully pretty quick). Imagine
the processors are connected as a ring; you don't need any 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 patches, 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.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\section{Applications}
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsection{What computations can CA do?}
\centerline{contributions by:}
\centerline{{\tt Benedict....@cm.cf.ac.uk}}
\bigskip
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.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{How do you do computations with the Game of Life?}
\centerline{contributions by:}
\centerline{ Chris Langton \email{c...@t13.lanl.gov}}
\bigskip
The constructive proof that the game of life is capable of supporting
universal computation is built around colliding glider streams
into one another. colliding 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 glider
gun at right-angles in such a way that the gliders in the input
stream occur with 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 input 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 gliders 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 glider in the input stream
allows a glider from the glider gun to pass, whereas for every
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 the 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, the basic idea
is as sketched out above.
For details, see the classic \cite{berlekamp82}
which contains the proof that the game of Life
is computation universal.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{Can CA be used to model ecological systems?}
\centerline{contributions by:}
\centerline{Matthew Burke \email{bu...@delta.math.wsu.edu}}
\bigskip
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. \cite{hogeweg88}, 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 \cite{hogeweg88}
\cite{huberman93}. 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, \cite{silvertown92} 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, \cite{green90} 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 physical
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.
\subsubsection*{References}
\cite{dytham92} \cite{ermentrout93}
\cite{green85} \cite{green82} \cite{green90}
\cite{hogeweg88} \cite{hogeweg90} \cite{huberman93}
\cite{nowak92} \cite{silvertown92}
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{The Universe as a Cellular Automata?}
\centerline{contributions by:}
\centerline{ Chris Langton {\tt c...@t13.Lanl.GOV}}
\bigskip
There is a great collection of papers \cite{IJP82}.
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.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{Can CA be used to encrypt messages?}
Yes. For a review see: \cite{gutowitz93}.
\subsubsection*{References}
\cite{wolfram85a} \cite{kari92} \cite{guan87}
\cite{gutowitz93} \cite{gutowitz92} \cite{gutowitz93b}
\cite{wolfram84a} \cite{meier91}
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\section{Special Types of CA}
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsection{ What are Lattice Gas Automata?}
\centerline{contributions by:}
\centerline{Paul Larson \email{pala...@dal.mobil.com}}
\centerline{ Bruce Boghosian \email{b...@Think.COM}}
\bigskip
{\bf References:}
\cite{boon92} \cite{doolen90} \cite{doolen91}
\cite{monaco89} \cite{manneville89}
\cite{alves91}
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
\subsubsection{Does the lack of symmetry in the HPP model
have any obvious bad effect, other than to remove the inertial term?}
\centerline{contributions by:}
\centerline{ Bruce Boghosian \email{b...@Think.COM}}
\bigskip
I don't think it removes the inertial term. There is still a form of
the inertial 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.
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
\subsubsection{Are there unphysical conservation laws with HPP?}
\centerline{contributions by:}
\centerline{ Bruce Boghosian \email{b...@Think.COM}}
\bigskip
Yes, HPP has several unphysical conservation laws. First, if you color
the sites white and black, like a checkerboard, you can convince
yourself that the dynamics 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 separately
within each row (assuming periodic b.c.'s).
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
\subsubsection{What are the physical manifestations of anisotropy?}
\centerline{contributions by:}
\centerline{ Bruce Boghosian \email{b...@Think.COM}}
\bigskip
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 underlying 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.
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
\subsection{What are continuous spatial CA?}
\centerline{contributions by:}
\centerline{Bruce MacLennan \email{macl...@cs.utk.edu}}
\bigskip
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
\subsection{Where can I read about the Gacs rule?}
\centerline{contributions by:}
\centerline{Lenore Levine \email{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. There are two co-authors, Kurdyumov and Levin.
Here are a few later papers that are probably related:
\cite{gacs83} \cite{gacs85} \cite{gacs86} \cite{gacs88} \cite{gacs89}
One piece of further work is this:
\cite{desa92}
Some related papers:
\cite{gray82}; this is Gray's proof of ergodicity for continuous-time monotonic
nearest-neighbor rules.
\cite{gray87}; this is Gray's proof for discrete time.
\cite{berman88} This is a relatively simple proof of Toom's rule.
\cite{gacs86} This is my Gacs' 1 dimensional construction.
\cite{gacs89}
This is a 2-dimensional construction which may help understanding the
difficult 1-dimensional paper and has a little more general
discussion.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{What's the Hodge Rule?}
\centerline{contributions by:}
\centerline{J\"org Heitk\"otter \email{jo...@ls11.informatik.uni-dortmund.de}}
\bigskip
HODGE-C is a (`mostly ANSI') C language implementation of
Gerhard \& Schuster's hodge-podge machine. It implements a class
of cellular automata, that resemble very closely autocatalytic
chemical reactions, like for example, the Belousov-Zhabotinskii (BZ)
reaction. It's available via anonymous ftp from \host{lumpi.informatik.uni-dortmunde.de}:\file{/pub/CA/src/hodge-c-0.98j.tar.Z}
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsubsection*{References}
BZ specific publications:
\cite{dewdney88b}
\cite{muller85}
\cite{muller87}
General CA:
\cite{langton89}
\cite{langton90b}
Introductory books:
\cite{davies88} \cite{briggs89}
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{What are some good references on Eater Rules?}
\centerline{contributions by:}
\centerline{ Harold McIntosh \email{mcin...@redvax1.dgsca.unam.mx}}
\bigskip
\cite{durrett91}
\cite{epstein91}
\cite{greenberg78a}
\cite{greenberg78b}
\cite{greenberg80}
\cite{madore83}
\cite{murray88}
\cite{winfree74}
\cite{winfree85}
\subsection{What are Vants?}
\centerline{contributions by:}
\centerline{John N. Rachlin \email{rac...@cs.jhu.edu}}
\centerline{ Charles F. Wells \email{cf...@po.CWRU.Edu}}
\centerline{ A Fraser \email{A.Fr...@eee.salford.ac.uk}}
\bigskip
The Vant rule, by Chris Langton, describes the path of an ant who
starts pointing 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 pointing.
If it is on a red square it turns the square white, rotates 90
degrees counterclockwise and moves one pixel in the direction it
is pointing.
See:
\cite{langton86}
\subsubsection{some vant simulators}
\paragraph{Langtons\_Ants} by John N. Rachlin
\email{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.
\paragraph{Quick Basic Vants}
Description: This program implements Chris Langton's cellular automaton
\cite{unknown93}
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. \email{cf...@po.cwru.edu.}
\paragraph{Virtual Ants in C} Borland C port of above by
\email{A.Fr...@eee.salford.ac.uk}.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\section{Properties of CA}
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsection{What is Flocking Behavior in CA?}
\centerline{contributions by:}
\centerline{ Rudy Rucker {\tt ruc...@sjsumcs.SJSU.EDU}}
\bigskip
The canonical flocking paper is
\cite{reynolds87}
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsection{What about basins of attraction for CA?}
\centerline{contributions by:}
\centerline{ Harold McIntosh \email{mcin...@redvax1.dgsca.unam.mx}}
\bigskip
\subsubsection*{References}
\cite{backhouse75}
\cite{jen88a}
\cite{jen88b}
\cite{li87}
\cite{nasu78}
\cite{mcintosh91a}
\cite{mcintosh91b}
\cite{wolfram83}
\cite{wolfram84a}
\cite{wolfram84b}
\cite{wolfram86}
\cite{gutowitz91b}
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{What are ``inhomogeneous'' CA?}
\centerline{contributions by:}
\centerline{ Ron Bartlett {\tt bart...@memstvx1.memst.edu}}
\centerline{Paulo Sergio Panse Silveira \email{silv...@fox.cce.usp.br}}
\centerline{Andrew Wuensche \email{10002...@compuserve.com}}
\bigskip
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.
\cite{wuensche93} discusses intermediate architectures between CA and
random Boolean networks. Homogeneous rules - varying degrees of random
wiring, homogeneous wiring template - various degrees of rule mix.
\cite{halpern89}: structurally dynamic CA.
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsubsection*{References}
\cite{vichniac86}
\cite{hartman00}
\cite{kauffman69} \cite{kauffman84}.
\cite{wuensche93}
\cite{halpern89}
\cite{aleksic93}
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{How important is Synchronicity in CA?}
\centerline{contributions by:}
\centerline{ Bill Tozier \email{wto...@mail.sas.upenn.edu}}
\centerline{ Shan Duncan \email{dun...@loris.cisab.indiana.edu}}
\centerline{ Joel Rahn \email{RA...@vm1.ulaval.ca}}
\centerline{Erik Winfree \email{win...@druggist.gg.caltech.edu}}
\centerline{ Jordan B Pollack \email{pol...@dendrite.cis.ohio-state.edu}}
\bigskip
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 interested in
applications find discreteness and regularity uncontroversial
compared to synchronicity. Many of the unique features of
cellular automaton dynamics can 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 \cite{chate91} 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 {\em except} giving up on synchronous updates.
The paper by Huberman and Glance \cite{huberman93}
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 Ermentrout and Leah Edelstein-Keshet
\cite{ermentrout93} and the section on lattice-gas automata.
An early reference: \cite{ingerson84}
They investigate Wolfram's CA rules using a probabilistic 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. However, 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 the CA
rule may not preserve the conservation law, and thus a radically
different steady-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 {\em modeling brain function}
(p. 80):
\begin{quote}
to reiterate, the asymptotic behavior of the network, on which we
focus our interest, may depend on the dynamical procedure, but such
dependence 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
\end{quote}
\subsection{ Which computations can 1D CA perform?}
\centerline{contributions by:}
\centerline{Peter Ruff \email{rzu...@rz.uni-wuerzburg.de}}
\bigskip
{\bf 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 steps.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{ Is there is universal 1D CA?}
\centerline{contributions by:}
\centerline{Mark A Biggar \email{m...@wdl39.wdl.loral.com}}
\centerline{Rudy Rucker \email{ru...@autodesk.com}}
\bigskip
{\bf 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 their neighborhood can change in a given
time. Defining the rules based on the original 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:
\begin{tabular}{cc}
state & 10 cell pattern \\
& \\
0 & 110000011 \\
1 & 110100011 \\
2 & 110010011 \\
3 & 110001011 \\
\end{tabular}
These patterns will overlap 1 cel on each end so the turning tape
$\ldots 102\ldots$
would be represented as:
$\ldots 111010001110000011100100111\ldots$
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.
{\bf 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 rule 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.
\subsubsection*{References}
\cite{smith71} \cite{lindgren90}
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{How to perform computations in the Game of Life?}
\centerline{contributions by:}
\centerline{Wentian Li \email{w...@cshl.org}}
\centerline{ McIntosh Harold V.-UAP \email{mcin...@redvax1.dgsca.unam.mx}}
\bigskip
Using the interaction of glider streams, the Game of Life
can be programmed to perform computations. Indeed, it is
a universal computer.
\subsubsection*{References}
\cite{berlekamp82} \cite{poundstone85}
\subsubsection{Must one use all of the logical gates
to perform computations in the Game of Life?}
See: \cite{jaynes}
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:
\begin{center}
\begin{tabular}{ccl}
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) \\
\end{tabular}
\end{center}
another example is the NOR (negation of OR):
\begin{center}
\begin{tabular}{ccl}
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) \\
\end{tabular}
\end{center}
the relevance to CA/Game of Life is that the
requirement for having {\em three} logical 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 logical functions.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{Where can I learn about Spaceships in the Game of Life?}
\centerline{contributions by:}
\centerline{ Bruce Stangeland \email{tb...@rrc.chevron.com}}
\bigskip
See ``Spaceships in Conway's Life'' by David I. Bell \email{db...@pdact.pd.necisa.oz.au}.
Texinfo version of above by
J\"org Heitk\"otter \email{jo...@ls11.informatik.uni-dortmund.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.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{What about running a CA backwards?}
\centerline{contributions by:}
\centerline{Lyman Hurd \email{hu...@math.gatech.edu}}
\bigskip
%% -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\subsubsection{The General Case}
I will assume that a ``configuration'' comprises a N x N square of symbols
{0,1} with the sites outside of this square assumed 0 (this is what I would
term a ``finite'' configuration.
One can ask:
\begin{enumerate}
\item
Is there a configuration which maps onto this configuration?
\item
Is there a finite configuration which maps onto this configuration?
\end{enumerate}
In one-dimension there are much-explored algorithms which answer to both
questions. 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 finds a bound phi(N) (recaall N is the initial size of
our finite neighborhood) for which 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
undecidability 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 universal.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{What are some reversible rules?}
\centerline{contributions by:}
\centerline{Bruno Durand \email{bdu...@ens-lyon.fr}}
\bigskip
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,\ldots,n}. The local transition rule f:
$$
\begin{array}{lccl}
f(a,b) & = & a & \mbox{if } b <= a \\
& & 1 & \mbox{if } b = a+1 \\
& & a+1 & \mbox{if } b > a+1 \\
\end{array}
$$
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{What is known about periodic orbits in CA?}
\centerline{contributions by:}
\centerline{Lyman Hurd \email{hu...@math.gatech.edu}}
\centerline{John Pedersen \email{j...@goedel.math.usf.edu}}
\bigskip
{\bf 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 an (I think) interesting result:
Assume that a 1-d CA has a quiescent state. I will (informally) call a
configuration ``trivial'' if it evolves to the all-quiescent state which I
will assume is a fixed point. A CA for which ALL configurations are
trivial, will be called nilpotent.
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
temporally, equivalent by (1)) orbit is trivial BUT for which not every
configuration 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 configurations 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, consider 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 = \ldots 0 0 0 c_0 c_1 \ldots c_N 0 0 0 0\ldots$
has a predecessor:
$d = \ldots d_{-2} d_{-1} d_0 d_1 d_2 \ldots$
Lining them up:
$d = \ldots d_{-2} d_{-1} d_0 d_1 d_2 \ldots d_N d_N+1 \ldots$
$c = \ldots 0 0 c_0 c_1 c_2 \ldots c_N 0 0 0 0\ldots$
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:
$d_{N+1} d_{N+2} d_{N+3}$
0 0 0
and continue to the right. There are only $k^3$ possible values so at SOME
point the list must have a duplicate, i.e.,
$d_{N+i} d_{N+i+1} d_{N+i+2} = d_{N+j} d_{N+j+1} d_{N+j+2} $
0 0 0 0 0 0
Now we can replace d with a configuration periodic on the right by
defining:
$d'_n = d_n$ if $n < d_{N+j},$
and otherwise
$d'_n = d'_{n-(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: \cite{pedersen92}
which derives algebraic conditions for all orbits a CA being periodic.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{What are Subshifts of Finite Type/Sophic Systems?}
\centerline{contributions by:}
\centerline{Mike Boyle \email{bo...@msri.org}}
\bigskip
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 partitions. You can do a lot of your analysis of equilibrium
states and periodic points 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 mathematical 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 transparent; and one key to studying
a sofic system is to understand how its properties 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 class is absolutely correct. It is in various ways
a more natural class than the class 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
than 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 automata be block codes on full shifts (versus block codes on SFT's
or other subshifts) seems unnatural. The latter viewpoint finds some
justification in the recent work of Alejandro Maass
\email{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 stated 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 studying SFT's can contribute some understanding.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{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 version of the mean field
theory is the $\lambda$ parameter of Langton,
more general versions, which take into acount spatial
correlations, have also been developed.
\subsubsection*{references}
\cite{schulman78} \cite{wolfram83} \cite{gutowitz87}
\cite{gutowitz91} \cite{mcintosh90}
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{When is a CA injective, surjective?}
\centerline{contributions by:}
\centerline{Lyman Hurd \email{hu...@math.gatech.edu}}
\bigskip
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 stronger 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 weaker condition that for all y there exists x such that
$F(x)=y$.
For 1-dimensional CA there exist well-known algorithms to determine
surjectivity 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 then implies that there must exist 2D rules for which the
complexity of describing its inverse vastly exceeds the complexity of
the rule itself. If we take r (the radius) and a rough determinant of
complexity, for any recursive function phi, there must exist a rule
with radius r whose inverse rule has radius greater than phi(r).
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\subsection{Can one decide if a 2D rule is reversible/surjective?}
\centerline{contributions by:}
\centerline{ Lyman Hurd \email{hu...@math.gatech.edu}}
\bigskip
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
surjectivity 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
proving recursive bounds on how big a string one would need to find to show
a counterexample 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 states 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.
\subsection{Where do I read about reversible cellular automata?}
\centerline{contributions by:}
\centerline{Harold V. McIntosh \email{mcin...@uapnx1.dgsca.unam.mx}}
\bigskip
The name most prominently associated with reversible cellular automata
seems to be Tommaso Toffoli; his most accessible work is probably
\cite{toffoli87}.
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 mentioned, 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
\cite{gardner83} thereby giving the idea
worldwide publicity.
Perhaps the computer science community's outstanding early contact
with reversible automata was
\cite{amoroso72}.
Non-reversibility, in the form of the Garden of Eden,
seems to go back to \cite{moore70}.
What seems to be quite remarkable is the degree to which 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 \cite{hedlund69}.
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) decimals 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 leads 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 exclusions. 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
\cite{weiss73}.
It should be noted that the language of
his presentation is semigroup theory, not graph theory.
Three papers by Ethan M. Coven and Michael E. Paul come from the same
time period: \cite{coven74} \cite{coven75} \cite{coven77}.
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 is: [\cite{nasu78}.
Somewhat later the ideas were generalized to apply to
flows through graphs: \cite{nasu82}.
An early attempt to relate reversibility and Gardens of Eden and to use
the interplay between global and local mappings was \cite{richardson72}.
A somewhat later paper \cite{sato77}
works out in considerable detail the relationships
between injectivity, surjectivity, and several other properties of
cellular automata. Slightly earlier, \cite{yaku76}
appeared.
The reasons for interest in reversible automata seem to have been
varied. A formal 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 were <<not>> reversible, and the momentary confusion
between the implications of the two concepts. Consequently Toffoli
seems to be a plausible candidate to have been the first proponent of
reversible automata as such.
His publications are not all that easy to track down, consisting of
his thesis, laboratory reports, contributions to conference proceedings,
and so on. However, \cite{toffoli77}
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
arbitrary 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, \cite{fredkin82}
which goes into some of their mutual ideas.
%%
%% -==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-
%%
\newpage
\bibliographystyle{alpha}
\bibliography{ca}
\nocite{*}
\end{document}