Frequently Asked Questions About Cellular Automata Contributions from the CA community edited by Howard Gutowitz hag@santafe.edu November 2, 1994 Abstract The CA FAQ has now moved to Santa Fe Institute/MIT Press ALife Online. The ''official'' version of the FAQ is henceforth the hypertext to be found here 1 . There is also a postscript 2 . version, and a text 3 . version. An important part of the FAQ is the bibtex format bibliography 4 . If you can't use Mosaic or equivalent, but can use ftp, then you find these files on the Alife Online's anonymous ftp server: alife.santafe.edu:`/pub/topics/cas'. Get the postscript version to find explict reference to the ftp hyperlinks in this (hypertext) version. If you can't use ftp, then we can't help you, sorry. The CA­list mail archives are available in hypertext or plain text formats (See sec 2.3.1). This FAQ features a ''loose threads'' section 2.4. A loose thread is a collection of messages to the CA distribution list which I have not yet edited down. As time permits, these threads will be woven into the main body of the FAQ. Do not make permanent links to them. http://alife.santafe.edu/alife/topics/cas/ca­faq/ca­faq.html ftp://alife.santafe.edu/pub/topics/cas/ca­faq.ps ftp://alife.santafe.edu/pub/topics/cas/ca­faq.dvi2tty ftp://alife.santafe.edu/pub/topics/cas/ca­faq.bib Contents 1 What are Cellular Automata (CA) 2 General Information 2.1 How can I get the latest FAQ 2.2 How do I contribute bibliographic material to the FAQ 2.3 What is the cellular automata mailing list? 2.3.1 Archives 2.4 What's in the ''loose threads'' section? 2.5 What are some related WWW sites? 2.6 What are some good general references for CA? 2.7 What is the Complex Systems Journal? 3 Where can I get a CA Simulator? 10 3.1 General­Purpose CA Simulators 3.1.1 automata 3.1.2 CALAB 3.1.3 CAMEX 3.1.4 CAM­PC 3.1.5 CART 3.1.6 CELIP 3.1.7 Cellsim 3.1.8 CELLULAR­3.0 3.1.9 CEPROL 3.1.10 CINC 3.1.11 LCAU 3.1.12 Mathematica 3.1.13 scamper 3.1.14 Self­Directed Replicator (?) 3.1.15 SimLife 3.1.16 SLANG 3.1.17 Wautom 3.2 Simulators for the Game of Life 3.2.1 bugglings 3.2.2 Life 3.2.3 lifelab 3.2.4 CASim 3.2.5 Plife 3.2.6 3dlife 3.2.7 xlife­2.0 3.3 Does Cellsim for X exist? 3.4 What is 3D­Life? 3.5 How can I make CA simulations run fast? 3.6 What hardware implementations exist for CA? 3.7 Are there any simulators for CAM? 3.8 Are there simulators for self­criticality? 3.9 What about running CA's on parallel or distributed machines? 4 Applications 4.1 What computations can CA do? 4.2 How do you do computations with the Game of Life? 4.3 Can CA be used to model ecological systems? 4.4 CA for reaction­diffusion? 4.5 The Universe as a Cellular Automata? 4.6 Can CA be used to encrypt messages? 5 Special Types of CA 29 5.1 What are Lattice Gas Automata? 5.1.1 Does the lack of symmetry in the HPP model have any obvious bad effect, other than to remove the inertial term? 5.1.2 Are there unphysical conservation laws with HPP? 5.1.3 What are the physical manifestations of anisotropy? 5.2 What are continuous spatial CA? 5.3 Where can I read about the Gacs rule? 5.4 What's the Hodge­Podge Rule? 5.5 What are some good references on Eater Rules? 5.6 What are Vants? 5.6.1 some vant simulators 6 Properties of CA 33 6.1 What is Flocking Behavior in CA? 6.2 What about basins of attraction for CA? 6.3 What are ``inhomogeneous'' CA? 6.4 How important is Synchronicity in CA? 6.5 What is the status on Wolfram's Class IV ? 6.6 Which computations can 1D CA perform? 6.7 Is there is universal 1D CA? 6.8 How to perform computations in the Game of Life? 6.8.1 Must one use all of the logical gates to perform computations in the Game of Life? 6.9 Where can I learn about Spaceships in the Game of Life? 6.10 What about running a CA backwards? 6.10.1 The General Case 6.11 What are some reversible rules? 6.12 What is known about periodic orbits in CA? 6.13 What are Subshifts of Finite Type/Sophic Systems? 6.14 What is the mean field theory? 6.15 When is a CA injective, surjective? 6.16 Can one decide if a 2D rule is reversible/surjective? 6.17 Where do I read about reversible cellular automata? 1 What are Cellular Automata (CA)? contributions by: Lyman Hurd 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 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. 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 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 F : S Z 2r+1 The domain and range of f are finite. The global function F arises from f by defining: F (c) i = f(c i) could 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: 1. 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. 2. The map F commutes with the shift operator which takes c i to c i+1 . 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. 2 General Information 2.1 How can I get the latest FAQ? See ''abstract'' 2.2 How do I contribute bibliographic material to the FAQ? Send references you do not see in ''ca­faq.bib'' to hag@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.: bibview 5 . Use of bibview will significantly improve your enjoyment of ''ca­ faq.bib''. 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. 2.3 What is the cellular automata mailing list? contributions by: Bruce M. Boghosian 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: [Wol86] [TM87] [Gut91a] [Wol94] 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 MAILING LIST IS UNDER RECONSTRUCTION. WATCH THIS SPACE. The Usenet newsgroup ``comp.theory.cell­automata'' still functions. It seems as well that distribution by mail to ca@think.com is working again as well. Maybe Sinking Machines has come back from the dead. ftp://ftp.informatik.tu­muenchen.de/pub/comp/typesetting/tex/bibview­2.0.tar.Z 2.3.1 Archives The hypertext versions of the archives can be sorted by author, subject or date: 1987 1988 1989 1990 1991 1992 http://alife.santafe.edu/alife/topics/cas/archives/87/index.html http://alife.santafe.edu/alife/topics/cas/archives/88/index.html http://alife.santafe.edu/alife/topics/cas/archives/89/index.html http://alife.santafe.edu/alife/topics/cas/archives/90/index.html http://alife.santafe.edu/alife/topics/cas/archives/91/index.html http://alife.santafe.edu/alife/topics/cas/archives/92/index.html The archives are also available as plain text: 1987 1988 1989 1990 1991 1992 ftp://alife.santafe.edu/pub/topics/cas/archives.87 ftp://alife.santafe.edu/pub/topics/cas/archives.88 ftp://alife.santafe.edu/pub/topics/cas/archives.89 ftp://alife.santafe.edu/pub/topics/cas/archives.90 ftp://alife.santafe.edu/pub/topics/cas/archives.91 ftp://alife.santafe.edu/pub/topics/cas/archives.92 2.4 What's in the ''loose threads'' section? N.B. these threads are available as hypertext only. McIntosh - This is a collection of remarks by Harold McIntosh concerning, among other things, his suite of CA software. go - The ancient Chinese game of Go is like a CA, right? gol - Game of Life Misc. hodge - About the Hodge­Podge Rule. lga - About Lattice Gas Automata and related. music - Can CA generate music> natural - CA as models in the natural sciences. progs - Announcement of new CA software, or updates. life­alife - Discussion concerning the relevance of Conway's Game of Life CA to the field of Artificial Life. reversible - Reversible CA Some CA are such that every configuration has a unique predecessor. Which are these? turing - Discussion of the computational capabilities of CA. paper - Announcements of material which may find its way into ca­faq.bib. http://alife.santafe.edu/alife/topics/cas/threads/progs.html/index.html http://alife.santafe.edu/alife/topics/cas/threads/life­alife.html/index.html http://alife.santafe.edu/alife/topics/cas/threads/reversible.html/index.html http://alife.santafe.edu/alife/topics/cas/threads/turing.html/index.html http://alife.santafe.edu/alife/topics/cas/threads/paper.html/index.html http://alife.santafe.edu/alife/topics/cas/threads/McIntosh.html/index.html http://alife.santafe.edu/alife/topics/cas/threads/go.html/index.html http://alife.santafe.edu/alife/topics/cas/threads/gol.html/index.html http://alife.santafe.edu/alife/topics/cas/threads/hodge.html/index.html http://alife.santafe.edu/alife/topics/cas/threads/lga.html/index.html http://alife.santafe.edu/alife/topics/cas/threads/music.html/index.html http://alife.santafe.edu/alife/topics/cas/threads/natural.html/index.html http://www.seas.upenn.edu/ale/cplxsys.html 2.5 What are some related WWW sites? Spaceships in the Game of Life (David Bell­J¨org Heitk¨otter) http://www.germany.eu.net/people/jokes/shipstoc.html Melanie Mitchell's home page, with references to Evolving CA project http://www.santafe.edu/mm A searchable software archive http://www.leo.org/leo/archiv/start.html CA's at CMU CA Software and other things, basically a mirror of old think.com archives. AU's Complex Systems Archive Some software and a tutorial on CA. http://www.cs.cmu.edu:8001/afs/cs/project/ai­repository/ai/areas/ca/0.html Alex Mallet's Complex (Adaptive) Systems information, includes pointers for CA and AL. http://life.anu.edu.au/./complexsystems/complex.html 2.6 What are some good general references for CA? contributions by: Mark A Biggar John Baez [TM87] [FTW84] [Gut91a] [WL92] 2.7 What is the Complex Systems Journal? Complex Systems: A journal devoted to the rapid publication of research on the science, math­ ematics, 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 H.H. Chou Dana Eckart Andy Wakelin Harold McIntosh Rudy Rucker Ken Karakotsios Simone Maggi 3.1 General­Purpose CA Simulators General Reference: [Hie90]. 3.1.1 automata author: (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 here (ftp://ftp.cs.umd.edu/pub/dtr.tar.Z) or here (http://www.cs.cmu.edu:8001/afs/cs/project/ai­repository/ai/areas/ca/systems/dtr/0.html) 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 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. 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 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. http://delta.cs.cinvestav.mx/~mcintosh/oldweb/software.html 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. http://www-2.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/ca/systems/cam/0.html http://www-2.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/ca/systems/cam/ 3.1.5 CART description: see [AS92]. requirements: >> availability: >> 3.1.6 CELIP description: see [Has90]. 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: cellsim 41 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 38 ftp://ftp.cognet.ucla.edu/pub/alife/public/cam.zip 39 ftp://cogsci.elte.hu/cogsci/alife/CA 40 http://www.cs.cmu.edu:8001/afs/cs/project/ai­repository/ai/areas/ca/syste ms/cam/0.html 41 http://www.cs.cmu.edu:8001/afs/cs/project/ai­ repository/ai/areas/ca/systems/cellsim/0.html 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­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. The latest release of Cellular­3.0 supports multi­threading for multi­processor machines from Sun and SGI with nearly (99computations. 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 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) 3.1.9 CEPROL description: see [Seu85] requirements: >> availability: >> 3.1.10 CINC Creature simulator for the Next. cinc 42 3.1.11 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 3.1.12 Mathematica description: a notebook showing an array of Cellular Automata requirements: Mathematica availability: swdsrv.edvz.univie.ac.at ra.nrl.navy.mil 3.1.13 scamper description: provides its own language and has a nice GUI 42 http://www.cs.cmu.edu:8001/afs/cs/project/ai­repository/ai/areas/ca/systems/cinc/0.html 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 3.1.14 Self­Directed Replicator (>) author: Hui­Hsien Chou . description: 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: here (ftp://ftp.cs.umd.edu/pub/dtr.tar.Z ) or dtr (http://www.cs.cmu.edu:8001/afs/cs/project/ai­repository/ai/areas/ca/systems/dtr/0.html) 3.1.15 SimLife description: GUI requirements: UNIX(>) or mac or amiga or PC availability: in local software store 3.1.16 SLANG description: see [SC91a] availability: cdm (http://www.cs.cmu.edu:8001/afs/cs/project/ai­repository/ai/areas/ca/systems/cdm/0.html ) 3.1.17 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, live­cell diagram. availability: here (ftp://ghost.dsi.unimi.it/pub2/papers/magi/wautom.zip) or wautom (http://www.cs.cmu.edu:8001/afs/cs/project/ai­repository/ai/areas/ca/systems/wautom/0.html) requirements: 286 machine, VGA, necessarily a 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 CASim description: Written by Kenneth M. . Karakotsios (the creator of SimLife). Information about the program from . CASimworks on any color Macintosh, and is still US$30. 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: here 3.2.7 xlife­2.0 requirements: UNIX, X11 availability: iacrs1.unibe.ch alice.fmi.uni­passau.de uxc.cso.uiuc.edu life.c ftp://life.anu.edu.au/pub/complex systems/alife/3DLIFE.ZIP 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 3.3 Does Cellsim for X exist? contributions by: Dave Hiebeler Felicity George 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. 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 Harold V. McIntosh John Pedersen Carter Bays gives a new rule for 3D Life in [Bay92]. The 3dlife program is available for ftp from here 49 49 ftp://life.anu.edu.au/pub/complex systems/alife/3DLIFE.ZIP References [Dew87] [Dew88b] 3.5 How can I make CA simulations run fast? contributions by: Rudy Rucker Richard Ottolini J Dana Eckart 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 com­ puted 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. 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 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. 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 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. 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. tips for periodic boundary conditions There are two basic methods: 1) coding for faster modulo arithmetic; and 2) using a larger array and copying the boundary cells between iterations. The brute force method of doing mod­ ulo arithmetic on index variable, x, for a range of 0..63 in C is (x+offset)%64 whereas on some architectures (e.g. some Sun Sparcstations) it is actually faster to do register int tmp=x+offset; tmp>63 > tmp­64 : tmp if offset is positive and similarly if it is negative. Still better, if the range is a power of 2, might be (x+offset)&63 when offset is positive and (x+offset+64)&63 when offset is negative. 3.6 What hardware implementations exist for CA> contributions by: Dr R W Taylor See [TM87] 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 [HTA92] which describes a 3D automata engine, computation is performed through the reconfiguration (at a very low level) of the hardware. 3.7 Are there any simulators for CAM? contributions by: Don Hopkins 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 `pub/CAM.tar.Z', or here . You will also need to retrieve the HyperLook runtime environment, from the same directory, with the name `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), un­ compress 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. ftp://ftp.uu.net/packages/NeWS/CAM.tar.Z 3.8 Are there simulators for self­criticality? contributions by: Richard J. Gaylord 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 Ex­ periences: Excursions in Programming'' in ``Mathematica in Education,'' an outstanding (and inexpensive) newsletter [contact Paul Wellin at for details]. 3.9 What about running CA's on parallel or distributed machines? contributions by: Dave Hiebeler 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 parti­ tioned 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: Benedict.M.Wightman@cm.cf.ac.uk If you just want a CA that does contributions by: Chris Langton The constructive proof that the game of life is capable of supporting uni­ versal 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. Ar­ range 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. Fur­ thermore, 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 51 http://www.cs.cmu.edu:8001/afs/cs/project/ai­repository/ai/areas/ca/systems/wirewrld/0.html 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 [BCG82] which contains the proof that the game of Life is computation universal. 4.3 Can CA be used to model ecological systems> contributions by: Matthew Burke 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 eco­ logical models. What follows are some quick thoughts on where the major difficulties with CA and ecological models lie. It is not intended to be thor­ ough, and it is not as well argued as I'd like. At the end is a list of interesting references in the area. The major question that needs to be addressed is that of CA's synchronicity. [Hog88], and others, have claimed that the simultaneous updating of all cells is at odds with the localness of interaction that is one of the strengths of CA. It has been shown that changing the definition of a CA to allow for asynchronous updating of cells can dramatically alter the behavior of the CA [Hog88] [HG93]. In particular, frequently the interesting structure seen in the evolution of a CA is, in fact, an artifact of the synchronous updating. What needs to be addressed is whether or not there are ecological systems for which universal updating is not an unwarranted assumption. For example, [SHJD92] develop a CA model of competition between grass species. I have not yet researched the characteristics of the species involved in their model, but it is not inconceivable to think that the dynamics of a set of annual plants may be modeled synchronously (perhaps the species all germinate at close enough times that on the scale of a year, we can think of it as synchronous). On the other hand, [Gre90] develops a CA model of the effects of fire and dispersal on spatial patterns in forests. I see no a priori reason, however, to assume that synchronous updating is reasonable in this situation. Another issue that needs to be investigated is the problems associated with multiple scales, both spatial and temporal. Typically CA models are de­ veloped with the assumption that a cell is a physcial region of the right size for one (or, perhaps, a few) individuals. Consider a model of plankton in the Celtic Sea (I have, which is why I bring it up). If we assume that over a certain horizontal distance, conditions are homogeneous, it suffices to limit ourselves to a water column, i.e. we only need one spatial dimension. At typical concentrations (private communication with R.A. Parker) we have enough plankton that it is impractical to assume one plankton (or a few) per cell. Now the relevant scales for the diffusion of plankton nutrients (such as nitrate) is even smaller. Also, consider three typical organisms: cyanobac­ teria, 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 think­ ing 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 men­ tioned 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 [DS92] [EEK93] [GAH85] [Gre82] [Gre90] [Hog88] [HH90] [HG93] [NM92] [SHJD92] 4.4 CA for reaction­diffusion> contributions by: Joerg Richard Weimar I have developed a method for constructing a CA for reaction­diffusion equations. It basically relies on large square neighborhoods for the diffusion part and a discretization of phase space combined with (mostly probabilistic) state transition tables derived directly from the nonlinear reaction­diffusion equation. I simulate excitable media (chemical waves), pattern formation, non­conservative phase transitions, and many less spectacular RD­systems. 4.5 The Universe as a Cellular Automata> contributions by: Chris Langton cgl@t13.Lanl.GOV There is a great collection of papers [unk82]. These are the proceedings of a conference on the Physics of Computation and Computational models of Physics. They contain some classic papers, including many that view the universe as a CA. Authors include Toffoli, Fredkin, Bennett, Landauer, Hillis, Feynman, Wheeler, and so forth. There is a fascinating paper by Marvin Minsky entitled ``Cellular Vacuum'' in which he shows that a version of relativity holds in CA's as clocks (oscillators) approach the speed of light ­ they slow down, but not in the same way that they do in continuous space. All in all, this collection is a must for those interested in computational aspects of the physical universe or in the physics of computation. 4.6 Can CA be used to encrypt messages> Yes. For a review see: [Gut93a]. References [Wol85a] [Kar92] [Gua87] [Gut93a] [Gut92] [Gut93b] [Wol84a] [MS91] 5 Special Types of CA 5.1 What are Lattice Gas Automata? contributions by: Paul Larson Bruce Boghosian References: [Boo92] [ea90b] [Doo91] [Mon89] [MBVB89] [Alv91] 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 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. 5.1.2 Are there unphysical conservation laws with HPP? contributions by: Bruce Boghosian 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). 5.1.3 What are the physical manifestations of anisotropy? contributions by: Bruce Boghosian 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. 5.2 What are continuous spatial CA? contributions by: Bruce MacLennan 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 5.3 Where can I read about the Gacs rule? contributions by: Lenore Levine 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: [Gac83] [GR85] [G ' 86] [GR88] [G ' 89] One piece of further work is this: [dSM92] Some related papers: [Gra82]; this is Gray's proof of ergodicity for continuous­time monotonic nearest­neighbor rules. [Gra87]; this is Gray's proof for discrete time. [BS88] This is a relatively simple proof of Toom's rule. [G ' 86] This is my Gacs' 1 dimensional construction. [G ' 89] This is a 2­dimensional construction which may help understanding the difficult 1­dimensional paper and has a little more general discussion. 5.4 What's the Hodge­Podge Rule> contributions by: J¨org Heitk¨otter 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 here 52 Cellular­3.0 include a hodge­podge rule. And see J¨org Heitk¨otter's home page 53 for pictures of the Hodge­Podge rule in action. and hodge 54 for a C program. References BZ specific publications: [Dew88a] [MPH85] [MPH87] General CA: [Lan89] [Lea90] Introductory books: [Dav88] [BP89] 5.5 What are some good references on Eater Rules? contributions by: Harold McIntosh [DS91] [Eps91] [GH78] [GHH78] [GGH80] [MF83] [Mur88] [Win74] [WWS85] 5.6 What are Vants> contributions by: John N. Rachlin Charles F. Wells A Fraser 52 ftp://lumpi.informatik.uni­dortmund.de/pub/CA/src/hodge­c­0.98j.tar.Z 53 http://www.germany.eu.net/people/joke.html 54 http://www.cs.cmu.edu:8001/afs/cs/project/ai­repository/ai/areas/ca/systems/hodge/0.html 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: [Lan86] 5.6.1 some vant simulators Langtons Ants by John N. Rachlin 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 and Turbo C 2.0 It requires EGA or VGA graphics. An executable is available from the author. Quick Basic Vants Description: This program implements Chris Langton's cellular automaton [unk93] 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. Virtual Ants in C Borland C port of above by . 6 Properties of CA 6.1 What is Flocking Behavior in CA? contributions by: Rudy Rucker rucker@sjsumcs.SJSU.EDU The canonical flocking paper is [Rey87] 6.2 What about basins of attraction for CA? contributions by: Harold McIntosh References [BC75] [Jen88a] [Jen88b] [Li87] [Nas78] [McI91b] [McI91a] [Wol83] [Wol84a] [Wol84b] [Wol86] [Gut91b] 6.3 What are ``inhomogeneous'' CA? contributions by: Ron Bartlett bartlett@memstvx1.memst.edu Paulo Sergio Panse Silveira Andrew Wuensche <100020.2727@compuserve.com> When each cell has a different rule, the resulting CA is called ``inhomogen­ eous''. Kauffman's ''random Boolean network'' model allows different rules AND connections, with applications in theoretical biology. [Wue93] discusses intermediate architectures between CA and random Boolean networks. Homogeneous rules ­ varying degrees of random wiring, homogen­ eous wiring template ­ various degrees of rule mix. [Hal89]: structurally dynamic CA. References [VTH86] [HV90] [Kau69] [Kau84]. [Wue93] [Hal89] [Ale93] 6.4 How important is Synchronicity in CA? contributions by: Bill Tozier Shan Duncan Joel Rahn Erik Winfree Jordan B Pollack 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 [CM91] 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 phys­ icists 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 [HG93] 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 [EEK93] and the section on lattice­gas automata. An early reference: [TI84] They investigate Wolfram's CA rules using a prob­ abilistic 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 dif­ ferent 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 their 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 asyn­ chronousness. A typical ''biological plausibility'' statement is found in Daniel Amit's book modeling 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 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 6.5 What is the status on Wolfram's Class IV? contributions by: Harold V. McIntosh It's generally accepted that the following ''elementary'' (2 state, radius 1) rules have typical class IV (or ''complex'') behaviours, because they feature emergent coherent propagating structures (analagous to gliders in Life, but 1­D). These gliders move and interact on periodic backgrounds; collisions between gliders produce new gliders. rule 54 (and the equivalent rule 147). rule 193 (and equivalent rules 124, 137 and 110). Who first introduced this particular classification, began by denying that (2,1) held any class IV's, although in a supplement to an article which was published in Scientific American, some of the above Rules may have been mentioned as worthy of interest. The fundamental difficulty here is that the ''Wolfram Classes'' are not well defined, even by Wolfram himself. Taken at their face value, it has been proven that they can't be; in articles by Culick III, as I recall. We are somewhat in the situation of the Supreme Court justice who declared ''I can't define pornography, but I can sure recognize it when I see it<'' Rule 54, which Prof. Wuensche mentions, has much in common with Rule 18, which was studied by Peter Grassberger in considerable detail at one time. The point with these rules is that although they have fairly well defined stable densities, there also seems to be a law of ''conservation of discontinuities.'' In Rule 54, this manifests with the occurrence of large triangular holes on a background of mostly small triangles and antitriangles. With Rule 18, the effect is much more subtle. If we apply the analysis described in the ''about xlcau21'' series to Rule 54, the mean field curve, especially the composite curve for several generations, has a superstable fixed point a little less than 50self­consistent contours for pairs show a linear relation between 1 and 11 yielding about half as many pairs as singlets. The n­block probabilities are less clear, an indication that the program's presentation could use some further work. On the ancestor side, although the rule is balanced, that is only for the in­ dividual states. Like pairs have an extra ancestor, unlike pairs lack one. The discrepancy grows, but not violently; the eigenvalue of the T­matrix is around 2.23. The T­matrix does have an interesting pair of zero rows; also a (different) pair of zero columns. The story with Rule 193 is not overly different, except that the rule is asym­ metrical and the field supports right­angled triangles rather than isosceles triangles. It is also true that the rule is slightly unbalanced from the begin­ ning, and that using the minimal equivalent, Rule 110, the final frequencies of live cells are somewhat larger. The problem with the Wolfram Classification is that it is much like the Christ­ mas Story. It seems simple and easily understood and makes for a kind of common reference when talking about cellular automata. When subjected to closer scrutiny, all kinds of questions and inconsistencies emerge. It does not help that Wolfram seems to have been inspired by a model from chaotic dynamics and Smale's ''strange attractors'' which may not be all that close to the actual behavior of cellular automata. Suffice it to say that it is easy enough, especially at first sight, to find struc­ tures such as those Wolfram described: some evolution IS chaotic, other fields seem to freeze up rather quickly. So far, there does not seem to have been much progress beyond the recognition of ''gliders'' in the mysterious realm called Class IV; for instance, although Wolfram seems to have expected their imminent discovery, not too many ''glider guns'' seem to have been found, and his whole idea of finding a cellular­automaton computer has fallen by the wayside. Wolfram's most important contribution to cellular automata seems to have been his way of looking at automata ­ first by setting random fields loose to see how they evolve, and second, systematically contrasting all the different rules with one another. He may just have been lucky, to have tried this at a time when suitable computer facilities had just become available. The work of von Neumann centered on the behavior of a specific automaton constructed for a specific purpose. Although other automata were considered, all were discarded which did not further the goal of self­reproduction. Conway's work with Life represented a different approach, in that ''marginal stability'' seems to have been his goal, with reference to the possibility of prov­ ing theorems about the evolution, but once a rule meeting that requirement was found, further development has mostly been oriented toward exploiting that one single automaton. Granted that even for one dimensional (2,1) automata it is possible to find some with behavior which seems tantalizingly regular, it would be nice to know that we are not seeing ''cloud castles'' and ''dragons'' and all the other paraphenalia of a small boy's imagination. So rather than worrying too much about what to call everything, attention ought to be directed to making more accurate predictions, on the one hand, and chartacterizing what we observe, on the other. However, all these poetical ideas could quickly become theological. Instead, we should realize that Prof. Wuensche has shown us that there are still some nice complications among the seemingly tame ''elementary'' (2,1) rules. Not entirely forgetting its resemblance to Rule 18, we need to notice that the spatial sequence (1000)*, according to Rule 54, has a temporal period of 4 also, and that it is an extremely common feature of well aged configurations. Besides the regular regions, there are slip lines, where two microcells are joined out of phase. Sometimes the interstices are larger; rarely are they extremely large save as the consequence of an initial configuration. Holes tend to fill by regular crystallization at the boundaries, but there is always the chance for an inconsistency as the gap nears completion. The boundary regions are so conspicuous there is a temptation to think of them as ''particles'' moving hither and yon against a disregardable back­ ground. Sometimes the movement is considerable and consistent, suggesting ''gliders'' although for Rule 54 they tend to stay in place. If Rule 54 particles move, it is more by diffusion than by having a momentum. There also exists the possibility that the particles collide, opening several avenues of further evolution. They may disappear (pair annihilation), cross over (solitons), or create some new kind of interstice (particle creation or transmutation). The scale of the field that is examined tends to influence its interpretation, so it should be chosen as large as possible to get the full effect of the dynamics of imperfections. The accompanying figure, ''54.ps.gz.gz.uu,'' shows only a moderate scale, to keep its size within reasonable limits. As usual, the name suggests the procedure to be followed for decoding it. Some Rules map zero fields into one fields and conversely; they are necessarily odd numbered rules less than 128. Should there be extended runs or gaps, they will tend to alternate, but with boundaries which can move around. This makes for another environment in which to perceive Class IV when the mood strikes. Once the discussion of de Bruijn diagrams begins, there are other aspects of would­be Class IV rules which could then be described. 6.6 Which computations can 1D CA perform? contributions by: Peter Ruff 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. 6.7 Is there is universal 1D CA? contributions by: Mark A Biggar Rudy Rucker 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: 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 : : : 102 : : : would be represented as: : : : 111010001110000011100100111 : : : 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 \Lambda (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. References [III71] [LN90] 6.8 How to perform computations in the Game of Life? contributions by: Wentian Li McIntosh Harold V.­UAP Using the interaction of glider streams, the Game of Life can be programmed to perform computations. Indeed, it is a universal computer. References [BCG82] [Pou85] 6.8.1 Must one use all of the logical gates to perform computations in the Game of Life? See: [Jay00] 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 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. 6.9 Where can I learn about Spaceships in the Game of Life? contributions by: Bruce Stangeland See ``Spaceships in Conway's Life'' by David I. Bell . Texinfo version of above by J¨org Heitk¨otter 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.10 What about running a CA backwards? contributions by: Lyman Hurd 6.10.1 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: 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 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 func­ tion 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 unde­ cidability 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 com­ putationally universal. 6.11 What are some reversible rules? contributions by: Bruno Durand 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 if b <= a 1 if b = a + 1 a + 1 if b > a + 1 6.12 What is known about periodic orbits in CA? contributions by: Lyman Hurd John Pedersen 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 config­ uration ``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 con­ figurations 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 = : : : 000c 0 c 1 : : : c N 0000 : : : has a predecessor: d = : : : d c 1 c 2 : : : c N 0000 : : : 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+1dN+2dN+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., dN+i dN+i+1 dN+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: d 0 n = d n if n < dN+j ; and otherwise d 0 n = d 0 n stronger result (of Golze) that periodic configurations must have periodic predecessors. See also: [Ped92] which derives algebraic conditions for all orbits a CA being periodic. It is true that initial conditions in cellular automata with circular (1D) or toroidal (2D) boundary conditions form a special case of all configurations. In fact, the dynamics on a fixed torus/circle form a compact subspace. The set of all possible spatially periodic configurations is more problematic topologically as it is neither open nor closed and is dense. However, it follows from Kari's work on the undecidability of the nilpotency problem that knowing the eventual dynamics of all periodic configurations does not suffice to tell you the entire behavior of the CA. The following theorems are shown constructively in: L. P. Hurd, J. Kari, K. Culik ''The Topological Entropy of Cellular Automata is Uncomputable'' which appeared in Ergodic Theory and Dynamical Systems (I am unfortu­ nately separated from my files and do not remember the exact issue. Anyone interested can email me directly): I will state the results in 1­D. They all apply a fortiori to higher dimensions. In general, undecidability results get easier as dimensionality goes up. The following conditions are equivalent: 1) A given (1­D) CA has no temporally periodic orbits except for the quiescent one. 2) Every spatially periodic state evolves in finite time to the quiescent state. One of these implications is pretty easy. I will leave it as an exercise. However we gave a counter­example of a nearest­neighbor rule with 17 symbols which showed that 1) and 2) fail to imply: 3) Every configuration evolves to the quiescent configuration. A compactness argument shows that 3) holds if and only if: 4) There exists a constant N such that every configuration evolves to the quiescent configuration in at most N time steps. In all of the above configurations are NOT assumed to be finite (of compact support). Put simply, any spatially periodic initial condition which you set for this rule however big the spatial period will eventually die out. However, there is shown to exist infinite configurations which are not periodic which persist indefinitely. The space­time diagram of one of these configurations forms an aperiodic tiling of the plane. A generalization of this rule (which came in a mysterious way from Penrose plane tilings; more mysterious when you remember we are still in 1D), pro­ duces CA's with arbitrarily high topological entropy (informally arbitrarily much dynamics) for which the dynamics lies entirely off the periodic orbits. 6.13 What are Subshifts of Finite Type/Sophic Systems? contributions by: Mike Boyle 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 . He uses techniques of symbolic dynamics to show that any endomorphism f of a mix­ ing 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 sophist­ icated 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. 6.14 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 – parameter of Langton, more general versions, which take into acount spatial correlations, have also been developed. references [SS78] [Wol83] [Gut87] [Gut91a] [McI90] 6.15 When is a CA injective, surjective? contributions by: Lyman Hurd 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 sur­ jectivity 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). 6.16 Can one decide if a 2D rule is reversible/surjective? contributions by: Lyman Hurd 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. 6.17 Where do I read about reversible cellular automata? contributions by: Harold V. McIntosh The name most prominently associated with reversible cellular automata seems to be Tommaso Toffoli; his most accessible work is probably [TM87]. Whereas the book describes a number of reversible rules for the CAM­6, Ed­ ward 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 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 [Gar83] thereby giving the idea worldwide publicity. Perhaps the computer science community's outstanding early contact with reversible automata was [AP72]. Non­reversibility, in the form of the Garden of Eden, seems to go back to [Moo70]. 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 [Hed69]. 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 re­ stricted 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 gen­ erally credited for this is [Wei73]. 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: [CP74] [CP75] [CP77]. 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: [[Nas78]. Somewhat later the ideas were generalized to apply to flows through graphs: [Nas82]. An early attempt to relate reversibility and Gardens of Eden and to use the interplay between global and local mappings was [Ric72]. A somewhat later paper [SH77] works out in considerable detail the relation­ ships between injectivity, surjectivity, and several other properties of cellular automata. Slightly earlier, [Yak76] 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 <> 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, [Tof77] 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, [FT82] which goes into some of their mutual ideas. References ========== [AB93] R. Anderson and K. Bunas. grain size segregation and strati­ graphy in aeolian ripples modelled with a cellular automaton. Nature, 365:740--743, October 1993. [AF91] Roy Adler and Leopold Flatto. subshifts of finite type and sofic systems (>). the Bulletin of the American Mathematical Society, pages 239--334, October 1991. [AI87] J. Albert and K. Culik II. A simple universal cellular automaton and its one­way and totalistic version. Complex Systems, 1:1--16, 1987. [Ale93] Zoran Aleksic. Computation in inhomogenous celluar automata. In David Green and Terry Bossomaier, editors, Complex Sys­ tems: From Biology to Computation. IOS Press, Amsterdam, 1993. anonymous ftp life.anu.edu.au:`/pub/complex systems/anu92/papers/aleksic.ps'. [Alv91] A.S. Alves. Discrete Models of Fluid Dynamics. World Scientific, 1991. [AP72] S. Amoroso and Y. N. Patt. Decision procedures for surjectivity and injectivity of parallel maps for tesselation structures. Journal of Computer and System Sciences, 6:448--464, 1972. [AS92] N. M. Allinson and M. J. Sales. CART -- A cellular automata research tool. Microprocessors and Microsystems, 16(8):403--415, 1992. [Bar90] A. M. Barbe. A CA ruled by an eccentric conservation law. Physica D, 45:49, 1990. [Bay87a] Carter Bays. Candidates for the game of life in three dimensions. Complex Systems, 1(2):373--400, April 1987. [Bay87b] Carter Bays. Patterns for simple cellular automata in a uni­ verse of dense packed spheres. Complex Systems, 1(6):853--875, December 1987. [Bay90] Carter Bays. The discovery of a new glider in the game of three­dimensional life. Complex Systems, 4(6):599--602, Decem­ ber 1990. [Bay91] Carter Bays. A new game of three­dimensional life. Complex Systems, 5(1):15--18, February 1991. [Bay92] Carter Bays. 3d life (>). Complex Systems, 6(5):433--442, 1992. [BC75] R. C. Backhouse and B. A. Carr'e. Regular algebra applied to path­finding problems. Journal of the Institute for Mathematics and its Applications, 15:161--186, 1975. [BCG82] Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. Winning Ways for your Mathematical Plays, volume 2. Aca­ demic Press, ISBN 0­12­091152­3, 1982. chapter 25. [BGMP93] N. Boccara, E. Goles, S. Martinez, and P. Picco. Cellular Auto­ mata and Cooperative Phenomena. Kluwer Academic Publishers, 1993. [BH92] R. J. De Boer and P. Hogeweg. Growth and recruitment in the immune network. In A. F. Perelson and G. Weisbuch, ed­ itors, Theoretical and Experimental Insights into Immunology, volume 66, pages 223--247. Springer Verlag, New York, 1992. [Bin91] P.­M. Binder. unknown. J. Phys. A, 24(L21), 1991. [Bin93] P.­M. Binder. Parametric ordering of complex systems. Physical Review E, 1993. [BNR91] N. Boccara, J. Nasser, and M. Roger. Particle­like structures and interactions in spatio­temporal patterns generated by one­ dimensional determinsitic cellular automaton rules. Phys. Rev. A, 44, July 1991. [Boo92] Jean Pierre Boon. Lattice gas automata: Theory, simulation, implementation. J. Stat. Phys., 68(3/4), 1992. [BP89] John Briggs and F. David Peat. An Illustrated Guide to Chaos Theory and the Science of Wholeness. Harper & Row, New York, 1989. [Bre93] X. Breckling. unknown. Ecological Modeling, 63(13­27):13--27, 1993. [BS88] Piotr Berman and Janos Simon. Investigations of fault­tolerant networks of computers. In Proc. of the 20­th Annual ACM Symp. on the Theory of Computing, pages 66--77, 1988. [BTS91] Philippe Binder, Carole Twining, and David Sherrington. Phase-- space study of bistable cellular automata. Complex Systems, 5(2):127--138, April 1991. [CD90] A. Canning and E. Droz. A comparison of spin exchange and CA models for diffusion­controlled reactions. Physica D, 45:285, 1990. [CIPY89] K. Culik II, J Pachl, and S Yu. On the limit sets of cellular automata. SIAM J. Comput., 18(4):831, 1989. [CK87] J. P. Crutchfield and K. Kaneko. Phenomenology of spatio­ temporal chaos. In Hao Bai­lin, editor, Directions in Chaos, page 272. World Scientific Publishers, Singapore, 1987. [CK88] J. P. Crutchfield and K. Kaneko. Are attractors relevant to tur­ bulence> Phys. Rev. Lett., 60:2715, 1988. [CM90] H. Chate and P. Manneville. Criticality in CA. Physica D, 45:122, 1990. [CM91] H. Chate and P. Maneville. Evidence of collective behavior in cellular automata. EuroPhys. Let, 14:409--413, 1991. [CP74] Ethan M. Coven and Michael E. Paul. Endomorphisms of irre­ ducible subshifts of finite type. Mathematical Systems Theory, 8:167--175, 1974. [CP75] Ethan M. Coven and Michael E. Paul. Sofic systems. Israel Journal of Mathematics, 20:165--177, 1975. [CP77] Ethan M. Coven and Michael E. Paul. Finite procedures for sofic systems. Monatshefte fuer Mathematik, 83:265--278, 1977. [Cru88] J. Crutchfield. Hunting for transients and cycles. unpublished notes, March 1988. [CS90] D. Chowdhury and D. Stauffer. Systematics of the models of the immune response and the autoimmune response. J. Stat. Phys, 59:1019--1042, 1990. [CS92a] F. Celada and P. E. Seiden. A computer model of cellular inter­ actions in the immune system. Immun­t, 13:56--62, 1992. [CS92b] D. Chowdhury and D. Stauffer. Statistical physics of immune networks. Physica A, 186: 1­2:61--81, 1992. [Dav88] Paul Davies. Cosmic Blueprint. Heinemann, London, 1988. [Dew87] A. K. Dewdney. The game life aquires some successors in three dimensions. Scientific American, 224(2):112--118, February 1987. [Dew88a] A. K. Dewdney. The Armchair Universe, volume ISBN 0­7167­ 1939­8 pbk. W. H. Freeman and Company, New York, 1988. [Dew88b] A. K. Dewdney. The hodgepodge machine makes waves. Sci­ entific American, 225(8), August 1988. [DGT85] J. Demongeot, E. Goles, and M. Tchuente. Dynamical systems and cellular automata. Academic Press, New York, 1985. [DMJ94] R. Das, M. Mitchell, and J.P.Crutchfield. A genetic algorithm discovers particle based computation in cellular automata. Tech­ nical report, SFI, 1994. Submitted to the 3rd Parallel Problem­ Solving From Nature Conf. [Doo91] G.D. Doolen. Lattice Gas Methods for PDE's, Theory, Applica­ tions and Hardware. North­Holland, 1991. [DS91] Richard Durrett and Jeffrey E. Steif. Some rigorous results for the greenberg­hastings model. Journal of Theoretical Probability, 4:669--690, 1991. [DS92] C. Dytham and B. Shorrocks. Selection, patches and genetic variation: a CA modelling drosophila populations. Evolutionary Ecology, 6:342--351, 1992. [dSM92] Paula Gonzaga de S'a and Christian Maes. The G'acs­ Kurdyumov­Levin Automaton revisited. Journal of Statistical Physics, 67(3/4):607--622, May 1992. [ea90a] F. C. Richards et al. Extracting CA rules directly from experi­ mental data. Physica D, 45:189, 1990. [ea90b] G. D. Doolen et al. Lattice gas methods for partial differential equations. Addison­Wesley, New York, 1990. [ea90c] K. Culik II et al. Computation theoretic aspects of CA. Physica D, 45:357, 1990. [ea90d] K. Culik II et al. Formal languages and global CA behavior. Physica D, 45:396, 1990. [ea90e] R. Livi et al. Periodic orbits and long transients in coupled map lattices. Physica D, 45:452, 1990. [ea90f] S. Qian et al. Adaptive stochastic CA: experiment. Physica D, 45:181, 1990. [ea90g] W. Li et al. Transition phenomena in CA rule space. Physica D, 45:77, 1990. [ea90h] Y. Aizawa et al. Soliton turbulence in 1­D CA. Physica D, 45:307, 1990. [ea90i] Y. C. Lee et al. Adaptive stochastic CA: theory. Physica D, 45:159, 1990. [(ed91] B. Mikolajczak (ed.). Algebraic and structural automata theory. Annals of Disc. Math, 44, 1991. [EEK93] G. Bard Ermentrout and Leah Edelstein­Keshet. Cellular auto­ mata approaches to biological modeling. Journal of Theoretical Biology, 160:97--133, Jan 1993. [Eis91] M. Eisele. Long­range correlations in chaotic cellular automata. Physica D, 48:295--310, 1991. [Eps91] Irving R. Epstein. Spiral waves in chemistry and biology. Sci­ ence, 252:67, 1991. [Fis90] R. Fisch. Cyclic CA and related processes. Physica D, 45:19, 1990. [FPS90a] A.S. Fokas, E.P. Papadopoulou, and Y.G. Saridakis. Coherent structures in cellular automata. Physics Letters A, 147:7:369-- 379, 1990. [FPS90b] A.S. Fokas, E.P. Papadopoulou, and Y.G. Saridakis. Soliton cellular automata. Physica D, 41:297--321, 1990. [FPSA89] A.S. Fokas, E.P. Papadopoulu, Y.G. Saridakis, and M.J. Ablow­ itz. Interaction of simple particles in soliton cellular automata. Studies in Applied. Math, 81:153--180, 1989. [Fre90] E. Fredkin. Digital mechanics: An informational process based on reversible universal CA. Physica D, 45:254, 1990. [FT82] Edward Fredkin and Tommaso Toffoli. Conservative logic. In­ ternational Journal of Theoretical Physics, 21:219--253, 1982. [FTW84] J. D. Farmer, T. Toffoli, and S. Wolfram. Cellular automata. North­Holland, Amsterdam, 1984. [G ' 86] Peter G'acs. Reliable computation with cellular automata. Journal of Computer System Science, 32(1):15--78, February 1986. [G ' 89] Peter G'acs. Self­correcting two­dimensional arrays. In Silvio Micali, editor, Randomness in Computation, volume 5 of Ad­ vances in Computing Research (a scientific annual), pages 223-- 326. JAI Press, Greenwich, Conn., 1989. [Gac83] P. Gacs. Reliable computation with cellular automata. STOC, 1983. [GAH85] D.G. Green, House A.P.N., and S.M. House. Simulating spatial patterns in forest ecosystems. Mathematics and Computers in Simulation, 27:191--198, 1985. [Gar83] Martin Gardner. Wheels, Life, and Other Mathematical Amuse­ ments. W. H. Freeman and Company, New York, 1983. ISBN 0­7167­1589­9. [Gar90] M. Garzon. CA and discrete neural nets. Physica D, 45:431, 1990. [GGH80] J. M. Greenberg, C. Greene, and S. Hastings. A combinator­ ial problem arising in the study of reaction­diffusion equations. SIAM Journal of Algebra and Discrete Mathematics, 1:34--42, 1980. [GH78] J. M. Greenberg and S. P. Hastings. Spatial patterns for discrete models of diffusion in excitable media. SIAM Journal on Applied Mathematics, 34:515--523, 1978. [GHH78] J. M. Greenberg, B. D. Hassard, and S. P. Hastings. Pat­ tern formation and periodic structures in systems modelled by reaction­diffusion equations. Bulletin of the American Mathem­ atical Society, 84:1296--1327, 1978. [GR85] P. Gacs and X. Reif. A simple three­dimensional real­time reli­ able cellular array. STOC, 1985. [GR88] P. Gacs and X. Reif. A simple three­dimensional real­time reli­ able cellular array. JCSS, 36, 1988. [Gra82] Lawrence F. Gray. The positive rates problem for attractive nearest neighbor spin systems on z. Z. Wahrscheinlichkeitsthe­ orie verw. Gebiete, 61:389--404, 1982. [Gra84] Peter Grassberger. unknown. Physica D, 10:52, 1984. [Gra86a] Peter Grassberger. appendix. In Stephan Wolfram, editor, The­ ory and Applications of Cellular Automata. World Scientific, 1986. [Gra86b] Peter Grassberger. Long­range effects in an elementary cellular automaton. J. Stat. Phys, 45:27--39, 1986. [Gra87] Lawrence F. Gray. The behavior of processes with statistical mechanical properties. In Percolation Theory and Ergodic The­ ory of Infinite Particle Systems, pages 131--167. Springer­Verlag, 1987. [Gra89] Peter Grassberger. Problems in quantifying self­generated com­ plexity. Helvetica Physica Acta, 62:489, 1989. [Gre82] D.G. Green. Simulated effects of fire, dispersal and spatial pat­ tern on ceompetition within forest mosaics. Vegetation, 82:139-- 154, 1982. [Gre90] David Geoffrey Green. Cellular automata models of crown­of­ thorns outbreaks. In R.H. Bradbury, editor, Acanthaster and the Coral Reef:A Theoretical Perspective, volume 88 of Lecture Notes in Biomathematics, pages 169--188. Springer­Verlag, Ber­ lin, 1990. [GS89] X. Gerhardt and X. Schuster. A cellular automation describing the formation of spatialy ordered structures in chemical systems. Physica D, 36:209, 1989. [GS92] X. Gerhardt and X. Schuster. Anregungen. Heft, 2:44-- 50, 1992. [Gua87] P. Guan. Cellular automaton public­key cryptosystems. Complex Systems, 1, 1987. [Gut87] Howard Gutowitz. Local Structure Theory for Cellular Auto­ mata. PhD thesis, Rockefeller University, New York, New York, 1987. [Gut89a] Howard Gutowitz. Statistical properties of cellular automata in the context of learning and recognition. part i: Introduction. In K.H. Zhao, editor, Learning and Recognition--A Modern Ap­ proach, pages 233--255. World Scientific Publishing, Singapore, 1989. [Gut89b] Howard Gutowitz. Statistical properties of cellular automata in the context of learning and recognition. part ii: Invert­ ing local structure theory equations to find cellular automata with specified properties. In K.H. Zhao, editor, Learning and Recognition--A Modern Approach, pages 256--280. World Sci­ entific Publishing, Singapore, 1989. [Gut90a] Howard Gutowitz. A hierarchical classification of CA. Physica D, 45:136, 1990. [Gut90b] Howard Gutowitz. Introduction (to cellular automata). Physica D, 45:vii, 1990. [Gut90c] Howard Gutowitz. Maps of recent CA and lattice gas automata literature. Physica D, 45:477, 1990. [Gut91a] Howard Gutowitz. Cellular Automata: Theory and Experiment. MIT Press/Bradford Books, Cambridge Mass., 1991. ISBN 0­ 262­57086­6. [Gut91b] Howard Gutowitz. Transients, cycles and complexity in cellular automata. Physical Review A, 44(12):7881--7884, Dec 1991. [Gut92] Howard Gutowitz. Method and apparatus for encryption, decryp­ tion, and authentication using dynamical systems. U.S. Patent Pending, 1992. [Gut93a] Howard Gutowitz. Cryptography with dynamical systems. In N. Boccara, E. Goles, S. Martinez, and P. Picco, editors, Cellular Automata and Cooperative Phenomena, pages 237--274. Kluwer Academic Publishers, 1993. [Gut93b] Howard Gutowitz. A massively parallel cryptosystem based on cellular automata. In B. Schneier, editor, Applied Cryptography. K. Reidel, 1993. [GV87] H. A. Gutowitz and J. D. Victor. Local structure theory in more than one dimension. Complex Systems, 1:57--68, 1987. [GV89] H. A. Gutowitz and J. D. Victor. Local structure theory: Calcu­ lation on hexagonal arrays, and the interaction of rule and lattice. J. Stat. Phys., 54:495--514, 1989. [GVK87] H. A. Gutowitz, J. D. Victor, and B. W. Knight. Local structure theory for cellular automata. Physica D, 28:18--48, 1987. [Hal89] Paul Halpern. Sticks and stones: a guide to structurally dynamic cellular automata. American Journal of Physics, 57(5):405--408, May 1989. [Has90] Wilhelm Hasselbring. CELIP: A cellular language for imaging processin. Parallel Computing, 14:99--109, 1990. [Hed69] G. A. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. Mathematical Systems Theory, 3:320--375, 1969. [Hei93] J¨org Heitk¨otter. HODGE­C: An implementation of Ger­ hard and Schuster's hodge­podge machine. C source code, Systems Analysis Research Group, LSXI, University of Dortmund, Department of Computer Science, D­44221 Dortmund, Germany, March 1993. Available via anon. ftp to lumpi.informatik.uni­dortmund.de as file `hodge­c­0.98j.tar' in /pub/CA/src. [HG93] B.A. Huberman and N. Glance. Evolutionary games and com­ puter simulations. Proc. Natl. Acad. Sci. USA, 90:7716--7718, August 1993. [HH90] P. Hogeweg and B. Hesper. Crowns crowding:an individual ori­ ented model of the acanthaster phenomenon. In R.H. In Brad­ bury, editor, Acanthaster and the Coral Reef:A Theoretical Per­ spective, volume 88 of Lecture Notes in Biomathematics, pages 169--188. Springer­Verlag, Berlin, 1990. [Hie90] D. Hiebeler. A brief review of CA packages. Physica D, 45:463, 1990. [Hil91] David Hillman. The structure of reversible one­dimensional cel­ lular automata. Physica D, 54:277--292, 1991. [HM90] B. Hasslacher and D. A. Meyer. Knot invariants and CA. Physica D, 45:328, 1990. [Hog88] P. Hogeweg. Cellular automata as a paradigm for ecological mod­ eling. applied Mathematics and Computation, 27(81­100):81-- 100, 1988. [HT90] H. Hartman and P. Tamayo. Reversible CA and chemical turbu­ lence. Physica D, 45:293, 1990. [HTA92] N. Howard, R. Taylor, and N. Allinson. The design and imple­ mentation of a massively­parallel fuzzy architecture. Proc. IEEE, pages 545--552, March 1992. [HV90] H. Hartman and G. Vichniac. Inhomogenous cellular automata. In E. Bienenstock and et al., editors, Disordered Systems and Biological Organization. unknown, 1990. [III71] Alvy Ray Smith III. Simple computation­universal cellular spaces. Journal of the Association for Computing Machinery, 18:339--353, 1971. [IJW92] O.H. Ibarra, T. Jiang, and H. Wang. String editing on a one­ way linear array of finite­state machines. IEEE Tr. on Comp, 41:1:112--118, 1992. [IY88] K. Culik II and S. Yu. Undecidability of CA classification schemes. Complex Systems, 2:177--190, 1988. [Jay00] E.T. Jaynes. probability theory--the logic of science. unknown, 1900. [Jen88a] E. Jen. Preimage scaling in cellular automata. Complex Systems, 2:1046, 1988. [Jen88b] Erica Jen. Cylindrical cellular automata. Communications in Mathematical Physics, 118:569--590, 1988. [Jen90] E. Jen. Aperiodicity in one­dimensional CA. Physica D, 45:3, 1990. [Kan84] K. Kaneko. Period­doubling of kink­antikink patterns, quasiperi­ odicity in antiferro­like structures and spatial intermittency in coupled logistic lattice. Prog. Theo. Phys., 72:480, 1984. [Kan85] K. Kaneko. Spatiotemporal intermittency in coupled map lat­ tices. Prog. Theo. Phys., 74:1033, 1985. [Kan86a] K. Kaneko. Lyapunov analysis and information flow in coupled map lattices. Physica, 23D:436, 1986. [Kan86b] K. Kaneko. Phenomenology and characterization of coupled map lattices. In Dynamical Systems and Singular Phenomena, Singa­ pore, 1986. World Scientific. [Kan89a] K. Kaneko. Pattern dynamics in spatiotemporal chaos. Physica D, 34:1, 1989. [Kan89b] K. Kaneko. Spatiotemporal chaos in one­ and two­dimensional coupled map lattices. Physica D, 35, 1989. [Kar90] J. Kari. Reversibility of 2D CA is undecidable. Physica D, 45:379, 1990. [Kar92] J. Kari. Cryptosystems based on reversible cellular automata. preprint, April 1992. [Kau69] S.A Kauffman. Metabolic stability and epigenisis in randomly constructed genetic nets. J. Theoretical Biology, 22:437--467, 1969. [Kau84] S.A Kauffman. Emergent properties in random complex systems. Physica D,, 10:146--156, 1984. [KM90] S. Kim and R. McCloskey. A characterization of constant­time CA computation. Physica D, 45:404, 1990. [Lan86] Christopher G. Langton. Studying artificial life with cellular automata. Physica D, 22:120--149, 1986. [Lan89] Christopher G. Langton. Artificial Life. Addison­Wesley, Red­ wood City, CA, 1989. [Lan90] C. G. Langton. Computation at the edge of chaos. Physica D, 42, 1990. [Lay92] John W. Layman. Dynamics of multicellular automata with un­ bounded memory. Complex Systems, 6(4):315--332, August 1992. [Lea90] Christopher G. Langton and et al. Artificial Life II. Addison­ Wesley, Reading, MA, 1990. [Li87] Wentian Li. Power spectra of regular languages and cellular automata. Complex Systems, 1:107--130, 1987. [Lin84] D. A. Lind. Applications of ergodic theory and sofic systems to cellular automata. Physica D, 10:36--44, 1984. [LN88] K. Lindgren and M. Nordahl. Complexity measures in cellular automata. Complex Systems, 2:409--440, 1988. [LN90] C. Lindgren and M. Nordahl. Universal computation in simple one dimensional cellular automata. Complex Systems, 4:299--318, 1990. [LN92] Wentian Li and Mats Nordahl. Transient behavior of cellular automata rule 110. Physics Letters A, 166(5/6):335--339, 1992. [LP90] W. Li and N. H. Packard. unknown. Compl. systems, 4:281, 1990. [Mar90] O. Martin. Critical dynamics of 1­D irreversible systems. Physica D, 45:345, 1990. [MBVB89] P. Manneville, N. Boccara, G. Vichniac, and R. Bidaux. Cel­ lular automata and the modeling of complex physical systems. Springer, Berlin, 1989. [MCH94] M. Mitchell, J. P. Crutchfield, and P. T. Hraber. Evolving cellular automata to perform computations. Physica D (submitted), 1994> available from ftp.santafe.edu `/pub/Users/mm/sfi­93­11­071.part1.ps.Z' and `sfi­93­11­071.part2.ps.Z'. [McI90] H. V. McIntosh. Wolfram's class IV automata and a good life. Physica D, 45:105, 1990. [McI91a] Harold V. McIntosh. Linear cellular automata via de bruijn dia­ grams. preprint, May 1991. [McI91b] Harold V. McIntosh. Reversible cellular automata. preprint, Jan 1991. [MF83] Barry F. Madore and Wendy L. Freedman. Computer simula­ tions of the belousov­zhabotinsky reaction. Science, 222:615--616, 1983. [MHC93a] M. Mitchell, P. T. Hraber, and J. P. Crutchfield. Dynamic computation, and the ``edge of chaos'': A re­examination. In G. Cowan, D. Pines, and D. Melzner, editors, Integrative Themes, Santa Fe Institute Proceedings, Volume 19, page (to appear), Reading, MA, 1993. Addison--Wesley. Santa Fe Insti­ tute Working Paper 93­06­040. [MHC93b] M. Mitchell, P. T. Hraber, and J. P. Crutchfield. Evolving cellular automata to perform computation: Mechanisms and impedients. Physica D, page (submitted), October 1993. Santa Fe Institute Working Paper 93­11­071. [MHC93c] M. Mitchell, P. T. Hraber, and J. P. Crutchfield. revisiting the egde of chaos: Evolving cellular automata to perform compu­ tations. Complex Systems, page (submitted), 1993. Santa Fe Institute Working Paper 93­03­014. [MJL91] Ablowitz M.J., Keiser J.M., and Takhtajan L.A. Class of stable multistate time­reversible cellular automata with rich particle content. Physical Review A, 44:10:6909--6912, 1991. [Mon89] R. Monaco. Discrete Kinetic Theory, Lattice Gas Dynamics and Foundations of Hydrodynamics. World Scientific, 1989. [Moo70] Edward F. Moore. Machine models of self reproduction. In Ar­ thur W. Burks, editor, Essays on Cellular Automata. University of Illinois Press, Urbana, 1970. [MOW84] O. Martin, A. Odlyzko, and S. Wolfram. Algebraic properties of cellular automata. Commun. Math. Phys., 93:219, 1984. [MPH85] Stefan C. Muller, Theo Plesser, and Benno Hess. The structure of the core of the spiral wave in the b­z reaction. Science, 230:4726, Nov 1985. [MPH87] Stefan C. Muller, Theo Plesser, and Benno Hess. Threedimen­ sional representation of chemical gradients. Biophysical Chem­ istry, feb 1987. [MS91] W. Meier and O. Staffelbach. Analysis of pseudo random se­ quences generated by cellular automata. Proceedings of Euro­ crypt '91, pages 186--199, 1991. [Mur88] James D. Murray. How the leopard gets its spots. Scientific American, pages 62--69, March 1988. [Nas78] Masakazu Nasu. Local maps inducing surjective global maps of one dimensional tesselation automata. Mathematical Systems Theory, 11:327--351, 1978. [Nas82] Masakazu Nasu. Uniformly finite­to­one and onto extensions of homomorphisms between strongly connected graphs. Discrete Mathematics, 39:171--197, 1982. [NM92] Martin A. Nowak and Robert M. May. Evolutionary games and spatial chaos. Nature, 359:826--829, 1992. [Pac88] N. H. Packard. unknown. In J. A. S. Kelso, A. J. Mandell, and M. F. Shlesinger, editors, Dynamic patterns in complex systems, pages 293--301. World Scientific, Singapore, 1988. [Pan91] R. Pandey. Cellular automata approach to interacting cellular network models for the dynamics of cell population in an early HIV infection. Physica A, 179:442--470, 1991. [PAS88] T.S. Papatheodorou, M.J. Ablowitz, and Y.G. Saridakis. A rule for fast computation and analysis of soliton automata. Studies in Applied. Math, 79:173--184, 1988. [Pay90] M. Payer. Finite state machine theory as a tool for construction of systolic arrays. In Pichler F. and Moreno­Diaz R., editors, Com­ puter Aided Systems Theory ­ Eurocast 89, volume LNCS:410, pages 212--224, Berlin, 1990. Springer­Verlag. [Ped92] John Pedersen. Cellular automata as algebraic systems. Complex Systems, 6(3):237--250, June 1992. [PF89] T.S. Papatheodorou and .S. Fokas. Evolution theory, periodic particles and solitons in cellular automata. Studies in Applied Math, 80:165--182, 1989. [Pou85] William Poundstone. The Recursive Universe. William Morrow and Company, New York, 1985. ISBN 0­688­03975­8. [P.S93] P.Siwak. Introduction to filter automata theory. Studia z Auto­ matyki, T.XVIII:87--110, 1993. [PST86] J.K. Park, K. Steiglitz, and W.P. Thurston. Soliton­like behavior in automata. Physica D, 19:423--432, 1986. [PT89] T.S. Papatheodorou and N.B. Tsantanis. Fast soliton automata. In H.Djidjev, editor, Optimal Algorithms, volume LNCS:401, pages 41--47. Springer, Berlin, 1989. [Rey87] Craig Reynolds. Flocks, herds, and schools: A distributed beha­ vioral model. Proceedings of ACM Computer Graphics, 21(4):25-- 33, jul 1987. [Ric72] D. Richardson. Tesselations with local transformations. Journal of Computer and System Sciences, 5:373--388, 1972. [SC91a] Hans B. Sieburg and Oliver K. Clay. Cellular automata as algeb­ raic systems. Complex Systems, 5(6):575--602, December 1991. [SC91b] Hans B. Sieburg and Oliver K. Clay. The cellular device ma­ chine development system for modeling biology. Complex Sys­ tems, pages 575--601, 1991. [Sch85] A. Schlijper. On some variational approximations in two­ dimensional classical lattice systems. PhD thesis, University of Groningen, The Netherlands, 1985. [Seu85] Friedhelm Seutter. CEPROL: A cellular programming language. Parallel Computing, 2(327--333):327--333, 1985. [SH77] Tadakazu Sato and Namio Honda. Certain relations between properties of maps of tesselation automata. Journal of System and Computer Sciences, 15:121--145, 1977. [SHJD92] Jonathan Silvertown, Senino Holtier, Jeff Johnson, and Pam Dale. Cellular automaton models of interspecific competition for space­the effect of pattern on process. Journal of Ecology, 80:527--534, 1992. [Siw92] P. Siwak. Particles of parity rule recursive filtering constructed by means of particle edge automata. Technical report, unknown, 1992. typescript. [SKW88] K. Steiglitz, I. Kamal, and A. Watson. Embedding computation in one­dimensional automata by phase coding solitons. IEEE Tr. on Computers, C­37:2:138--145, 1988. [SMC + 90] H. Sieburg, X. McCutchan, X. Clay, X. Cabalerro, and X. Ostlund. Simulation of HIV infection in artificial immune systems. Physica D, 45:208--227, 1990. [Smi90] M. A. Smith. Representations of geometrical and topological quantities in CA. Physica D, 45:271, 1990. [SNH91a] Bhavin Sheth, Prantik Nag, and Robert W. Hellwarth. Binary addition on cellular automata. Complex Systems, 5(5):479--486, October 1991. [SNH91b] Bhavin Sheth, Prantik Nag, and Robert W. Hellwarth. Driver mechanisms on cellular automata. Complex Systems, 5(5):487-- 496, October 1991. [SP92] D. Stauffer and R. Pandey. Immunologically motivated simula­ tion of cellular automata. Computers in Physics, 6:4:404--410, 1992. [SS78] L. S. Schulman and P. E. Seiden. Statistical mechanics of a dynamical system based on conway's game of life. J. Stat Phys., 19:293, 1978. [Sta91] D. Stauffer. Computer simulation of cellular automata. J. Phys. A: Math. Gen., 24:909--927, 1991. [Sut90] K. Sutner. Classifying circular CA. Physica D, 45:386, 1990. [Sut91] Klaus Sutner. De bruijin graphs and linear cellular automata. Complex Systems, 5(1):19--30, February 1991. [Svo90] K. Svozil. Constructive chaos by CA and possible sources of an arrow of time. Physica D, 45:420, 1990. [SW92] D. Stauffer and G. Weisbuch. High­dimensional simulation of the shape­space model for the immune system. Physica A, 180: 1­2:42--52, 1992. [Tak76] H. Takahashi. The maximum invariant set of an automaton sys­ tem. Information and Control, 32:307--354, 1976. [Tak90a] S. Takahashi. CA and multifractals:dimension spectra of linear CA. Physica D, 45:36, 1990. [Tak90b] S. Takesue. Relaxation properties of elementary reversible CA. Physica D, 45:278, 1990. [TI84] R.L. Buvel T.E. Ingerson. Structure in asynchronous cellular automata. Physica D, 1:59--68, 1984. [TM87] Tommaso Toffoli and Norman Margolus. Cellular Automata Ma­ chines: A New Environment for Modeling. MIT Press, Cam­ bridge, Mass, 1987. [TM90] T. Toffoli and N. Margolus. Invertible cellular automata: A re­ view. Physica D, 45:229, 1990. [Tof77] Tommaso Toffoli. Computation and construction universality of reversible cellular automata. Journal of Computer and System Sciences, 15:213--231, 1977. [unk82] unknown, editor. Physics of Computation and Computational models of Physics, volume 21:3­4, 6­7, and 12, 1982. [unk93] unknown. Chris langton's cellular automaton (>). Mathematical Intelligencer, 15(2):54, 1993. [Vic90a] G. Vichniac. Boolean derivatives on CA. Physica D, 45:63, 1990. [Vic90b] J. D. Victor. What can automaton theory tell us about the brain> Physica D, 45:205, 1990. [Voo90] B. Voorhees. Nearest neighbor CA over Z 2 with periodic bound­ ary conditions. Physica D, 45:26, 1990. [Voo91a] Burton Voorhees. Geometry and arithmetic of a simple cellular automaton. Complex Systems, 5(2):169--182, April 1991. [Voo91b] Burton Voorhees. Geometry and arithmetic of a simple cellular automaton. Complex Systems, 5(2):169--182, April 1991. [VTH86] G. Vichniac, P. Tamayo, and H. Hartman. Annealed and quenched inhomogeneous cellular automata. Journal of Statist­ ical Physics, 45, 1986. [Wal90] C. C. Walker. Attractor dominance patterns in sparsely connec­ ted boolean nets. Physica D, 45:441--451, 1990. [WB94a] J¨org R. Weimar and Jean­Pierre Boon. A new class of cellular automata for reaction­diffusion systems. Physical Review E, to appear, 1994. [WB94b] J¨org R. Weimar and Jean­Pierre Boon. New class of cellular automata for reaction­diffusion systems applied to the cima re­ action. In A. Lawniczak and R. Kapral, editors, Lattice Gas Automata and Pattern Formation, Waterloo, Ont, Canada, 1994. Fields Institute. [WDBS92] J¨org R. Weimar, David Dab, Jean­Pierre Boon, and Sauro Succi. Fluctuation correlations in reaction­diffusion systems: Reactive lattice gas automata approach. Europhysics Letters, 20(7):627-- 632, 1992. [Wei73] Benjamin Weiss. Subshifts of finite type and sofic systems. Mon­ atshefte fuer Mathematik, 77:462--474, 1973. [Wei92] J¨org R. Weimar. Spontaneous nucleation in a reactive lattice gas automaton. In Stefan M¨uller and Theo Plesser, editors, Spatio­ temporal organization in nonequilibrium systems, pages 266--269, Dortmund, Germany, 1992. Projekt Verlag. [Win74] Arthur T. Winfree. Rotating chemical reactions. Scientific Amer­ ican, pages 82--95, Jun 1974. [WL90] W. W. Wootters and C. G. Langton. Is there a sharp phase transition for deterministic CA> Physica D, 45:95, 1990. [WL92] Andrew Wuensche and Mike Lesser. The Global Dynamics of Cellular Automata, volume Reference Vol 1 of Santa Fe Institute Studies in the Sciences of Complexity. Addison­Wesley, 1992. IBSN 0­201­55740­1. [Wol83] Stephan Wolfram. Statistical mechanics of cellular automata. Rev. Mod. Phys., 55:601--644, 1983. [Wol84a] Stephan Wolfram. Random sequence generation by cellular auto­ mata. Adv. Appl. Math, 7:123, 1984. [Wol84b] Stephan Wolfram. Universality and complexity in cellular auto­ mata. Physica D, 10:1--35, 1984. [Wol84c] Stephen Wolfram. Computation theory of cellular automata. Communications in Mathematical Physics, 96:15--57, 1984. [Wol85a] Stephan Wolfram. Cryptography with cellular automata. Pro­ ceedings of Crypto '85, pages 429--432, 1985. [Wol85b] Stephan Wolfram. undecidability and intractability in physics. Phys. Rev. Lett., 54:735, 1985. [Wol86] Stephan Wolfram. Theory and applications of cellular automata. World Scientific, Singapore, 1986. ISBN 9971­50­124­4 pbk. [Wol94] Stephan Wolfram. Cellular Automata and Complexity: Collected Papers. Addison­Wesley, 1994. revision of [Wol86] Paperback: ISBN 0­201­62664­0, Hardcover: ISBN 0­201­62716­7. [WTW92a] J¨org R. Weimar, John J. Tyson, and Layne T. Watson. Diffusion and wave propagation in cellular automaton models of excitable media. Physica D, 55:309--327, 1992. [WTW92b] J¨org R. Weimar, John J. Tyson, and Layne T. Watson. Third generation cellular automaton for modeling excitable media. Physica D, 55:328--339, 1992. [Wue93] Andrew Wuensche. The ghost in the machine:basins of attrac­ tion of random boolean networks. Cognitive Science Research Paper 281, University of Sussex, 1993, 1993. to be published in Artificial Life III, Santa Fe Institute Studies in the Sciences of Complexity. [WWS85] A. T. Winfree, E. M. Winfree, and H. Seifert. Organizing centers in a cellular excitable medium. Physica D, 17:109--115, 1985. [Yak76] Takeo Yaku. Inverse and injectivity of parallel relations induced by cellular automata. Proceedings of the American Mathematical Society, 58:216--220, 1976. [Zab88] J. G. Zabolitzky. Critical properties of rule 22 elementary cellular automata. J. Stat. Phys., 50:1255--1262, 1988.