CA2D

CA2D 4 Mac: A Snazzy way to Investigate the Diverse CA Field
Chris King
For help/queries, email

Download the CA2D Mac application v1.1.14 Apr 2017 with XCode source files, documentation and examples.
For updates and the live linked version of this page with downloads see: http://dhushara.com/CA/

CA2D is designed as a Mac application to provide a research tool to explore as rich and diverse a variety of 1D and 2D cellular automata as possible, while at the same time providing a fast high-resolution artistically appealing easy to use interface, which is ideal for exploring the surprising graphical features of these processes. It comes with source code, so you can reprogram it easily using XCode for new ideas, but also has input rules for a vast array of interesting known CAs spanning most key types, including complex games representing quantum wave functions, the prisoners' dilemma, evolutionary rock-paper-scissors, and the reaction-diffusion automata on mollusc shells which are not available in other applications. It also has some of the nicest visual and scientific demonstrations of the versatility of CAs. For a good introduction to many of the CAs in this package see Joel Schiff's "Cellular Automata: A Discrete View of the World", Wiley ISBN: 978-0-470-16879-0, also available in chapters in the Wiley online library.

This page provides some quite stunning examples of the CAs invoked in CA2D and how the controls work. The application is designed as an open source research tool to investigate 2D cellular automata, given the high performance of current Intel macs.

It begins with the Moore neighborhood Infect CA on 10000 iterations at a moderate speed. Some of the 2D CAs use a Von Neumann neighbourhood consisting of center C and four neighbours N, S, E and W. Others such as the game of life use the Moore neighbourhood with NE, SE, NW and SW as well.

Other Sources: If you are more interested in technical simulation of CA rule schemes and constructing self-replicating CAs with complex computational instruction sets, try the cross-platform open-source application Golly, which runs on Windows, Linux and Mac OS. This is a good interface for viewing the very large game of life simulations involving universal computation for which there are links in the game of life section. The Life Wiki is also a comprehensive resource. If you are using Windows Mirek's Cellebration also has a large library of CAs. The Rule Table Repository is a valuable place to investigate the diversity of CAs and find new rule tables. Cellular Automata also has a large list of Java examples. Stephen Wolfram's A New Kind of Science also provides a detailed overview of elementary CAs.

The codes defining a sample of the resident CAs are listed here so you can see how each of them work. The rest can be accessed in the updated source code. The first eight or so options also enable the input of a wide variety of rule defined CAs. Finally it is easy and completely general to be able to program the CAs with no restrictions, using the source code, so entirely new types of CAs can be constructed.

There are several colour schemes which are useful for specific CAs. Bit Color 8 gives integer RGB values of 0 or 1 for each channel, giving colors mod 8. KRGB gives a four colour mode which extends to more states by graduation. RYGCBM gives a rainbow sequence. KRYGCBMW (the default) runs from black through the rainbow to white graduated to the number of states. AbsSinRGB runs sinusoidally as does ShiftedSin. These are slower to compute than the default. Finally Special gives the correct color coding for Diffuse Aggregate, Byl and Sexy Loops, Maze Solver, Rock-Paper-Scissors and for my replicating self-portrait.

The standard screen is 797 x 399 which is chosen to invoke an odd number of cells in both directions for scales 1, 2 , 4 and 8, and to provide a standard screen with a width twice the height, discounting the central row and column, to retain symmetry of growing 2D patterns and minimize irrational toroidal interference when the pattern expands beyond the boundaries. The screen can be resized and Redawn to larger or smaller dimensions.

Time tunnel has a very long evolution from diamonds to patchworks with the invasion of singular cells
ultimately resulting in a wild leopard-skin dynamic.

You can type or paste in a start matrix of numbers 0-9 (or higher values using ASCII single character bytes) as a text string in Start Matrix to override the options provided e.g. 010011111 will start the life CA with a 3x3 matrix corresponding to a glider formation. You can easily paste up a large array of numbers using Text Edit. The string can have line breaks or carriage returns so can accept a single vector and convert to a square matrix up to 330x330. Inserting r will provide a random screen-filling array in the number of cell states used by the rule. xn n=1-9 will generate a random array exponentially biased by varying degrees towards lower values. yn n=1-9 favours higher values. You can also insert rs, xns, or yns to set symmetrized random initial conditions. Inserting s on its own retains the existing screen (or the existing last line in 1D CAs) and proceeds to a new series of steps on Redraw.

This provides an opportunity to explore the different CAs using previous states as starting conditions. Try alternating between demons or Persian and hour glass, or for an interesting cascade. If you need a finite random array use can use the random growth CA followed by s. Try 2112144114412112 with Infect for a wild visual! Try shrike with 242121242 for an interlocked trellis. This provides ample opportunity to input complex stating states.

Many of the CAs on the CA list can be modified by using input rules. In addition to the rules listed below, there are also several rule lists. The input rule option expands the number of examples from 10 to way over a googol, or 10¹⁰⁰, since for example a Moore binary rule with 4⁸ = 65536 neighbourhood arrangements in 4 colours involves 4⁶⁵⁵³⁶ possibie code rules - something akin to the number of possible DNA sequences in a vestigial organism.

The input rules treat each character as ASCII and subtract 48 so that the codes for 0-9 are just the nine digits 0-9 themselves. The ASCII for larger numbers relative to ascii(0)=48 are thus coded as the characters 0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^"'abc... and so on, enabling any initial state or rule to be specified using larger values than 0-9, under the given protocols for each CA type.

A unique CA, based on a chequerboard-iterating neighbourhood in two stages, which enables a discrete simulation of a Hamiltonian process iterating position and velocity, is the CA developed by th

e author from Selcuk Hosoglu's 2006 thesis (www.dtic.mil/dtic/tr/fulltext/u2/a462598.pdf) to study quantum chaos and quantum wave functions in the stadium and other potential well chambers. The rules are very simple. Each iteration occurs on an alternate chequerboard of either the black or white squares. We take (-2C+N+S+E+W)/2 for each cell on say the black squares and apply a reflecting condition at any boundary point as well e.g. if E is outside the boundary we take (-2C+N+S+2W)/2. The curved region is actually a series of staggered right angles reflecting e.g. both N and E, replicating the atomic condition of a small quantum wave chamber reasonably acurately. Finally we copy the states found back to the original array so the second half-stage updating the white squares uses the updated values.

This differs from the Margolus neighbourhood, which likewise iterates in two stages, but instead works as a block CA, with each cellular calculation confined within with four cells per square. In this case, the 2-stage process uses alternate tilings of the plane, with block squares partially overlapping, so that the two stage process enables dynamic motion across the entire plane.

The quantum CA defaults to a bow-tie wave function in the stadium, as illustrated above. This is designed to run in the default screen size, or the max or min screen sizes, so that the stadium length is twice the width, but will produce rescaled wave functions at any size. You can also run it in a variety of configurations by inputting a code of the form m;nn;pp;q.qqq , default= 0;03;01;1.000, where m is the region type ( 0=stadium, 1=rectangle, 2 double slit, 3= losenge, 4=circular, 5=hyperbolic, 6=cardioid, and 7=cardioid centered on the cusp), and nn=00-12 is the wave type. ( 00=twin radial, 01=single radial, 02=horizontal, 03=bow tie, 04= twin diamonds, 05=twin pegs, 06=twin V, 07=rectangular orbit, 08=period 6. 09=cosx*cosy 10=cosx+cosy 11= double slit wave and 12=vertical). 01-08, and 12 have wavelengths designed for the stadium in default size; 09, 10 for the rectangular box; and 01, 12 for the losenge. pp allows you to determine how far the wave function will go before beginning to calculate a scar in units of 100 steps (Default=01 which is 100 steps). q.qqq allows for scaling the wavelength of the generating wave by an additional factor. This is useful for looking for resonances, particularly in the generic waveforms 01, 02, 09, 10 and 12).

The process completes when the defined number of steps are completed, when the display gives an absolute average of wave phase-stepped states, forming a scar. A good number of iterations is 2000. The minimum is 1000.

A series of prisoners dilemma games show varying success of the strategies on differing payoffs.
(1-3) evolution under the default 3051;50;10;05. Defect black, tit-for-tat yellow, simpleton red, random cooperate green, and cooperate blue.
(4-5) 2050;25;10;05 results in hard defection followed by domination by tit-for-tat. (6) 4050;25;10;05 now has a mix of cooperate and simpleton
but if random is made more cooperative, it then becomes most populous.

The prisoners' dilemma is a famous game of evolutionary strategy in which two co-defendents are tempted to accuse one another in the hopes of getting off, but both betray one another and receive a long punishment rather, than the lighter sentence if they had stuck to a common plea of innocence, because the temptation to defect leads to double jeopardy of mutual defection, in which both lose out. It has been applied to nuclear mutually assured destruction, as well as sexual relationships and the Red Queen evolutionary race between parasites and hosts. This is an intrinsically more complicated cellular interaction because it requires playing several rounds against all Moore neighbours for each cell and after a series of say five rounds, giving the cell to the winning strategy in the neighbourhood.

The simulation, ported from Gary Flake's open source program, has five resident strategies: always cooperate (red), always defect (black), tit-for-tat (doing what your opponent did last time), Pavlov or simpleton (win-stay lose-shift, i.e. change what you did if you got punished last time) and a strategy randomly switching, in our case, between tit-for-tat and cooperate, with a probability rcp determined by the input rule. In Bit Color 8 the colors are: defect=black, tit-for-tat=yellow, simpleton-=red, random/cooperate=green, and cooperate=blue. New strategies can easily be tested by amending the source code.

The CA can be modified by inputting the four payoffs CC (both cooperate),CD (sucker's penalty),DC (aced the opponent), DD (double jeopardy) as well as rcp, noise, and mutation in the form of the following rule: pppp;rr;nn;mm, where p = 0 - 9, and rr, nn, mm give probabilites 0.xx. Noise causes random changes in a single round, mutation causes a random shift to a new strategy. The default is 3051;50;10;05.

Left four panels: The default demons CA 0810 also proceeds from randomness to structure.
Right: Demon 3211 shows three stage engulfing from a random beginning Far right: 0433.

Cyclic CAs have rules in which a cell is upgraded a unit cyclically if a number of neighbours over a threshold have one greater value. Input a rule of the form sstn where ss = 02 - 99 is the number of states, t = threshold, and n is the neighbourhood type 0 = von Neumann, 1,2 = Moore 3,4 = radius 2 von Neumann. In 2 and 4 the diagonal and radius two quartets count as having value 2 more and 3 more respectively. The default is 0810 but 1610 gives a longer burst into a more prominent demons, and 2012 gives an further cyclic demon phenomenon. Several other configurations e.g. 0431, 0320, 0621, 0823 lead to highly variable stratification or equilibrium states. 3613 and 5014 give interesting examples of demons from larger neighbourhoods. You can also generate hexagonal demons using n = 6, 7, or 8 for hexagonal first second and third generation neighbourhoods as described in Leopard systems below. e.g. 1216, 2417, 3018. Scale 6 is designed to give correct hexagonal symmetry at the same resolution as scale 2.

Two kinds of replicative CAs: Left: Fredkin3, named after physicist Ed Fredkin, a 3-state CNSEW von Neumann rule listed in the rule table in the von Neumann section. Right: Three state summative cyclic CA pattern breeder 00301. Both systems were initialized with the independent three-state BBC2 rule ;;3 fractal in 24 steps and set to run with initial condition s to form ever-larger fractals with novel internal structure, only to fragment into clones of the original. Because the Fredkin rule is based on a 5 cell CNSEW vN neighbourhood and pattern breeder is based on 4 the number of replicates is 5 and 4 respectively at the final stage. This also explains why the pattern breeder successfully replicated at two intermediate states where Fredkin's centre replicate overlapped the others. In fact Fredkin3 is formally identical to pattern breeder 00311, which is also based on the five element neighbourhood. The final pattern in each case is after three stages of 27 = 3³ iterations reflecting the prime 3 color pattern, as in the Winograd replicator to follow. They would replicate in 3² = 9 steps, but the initializing pattern of 24 steps is too large. Higher prime values p also replicate in p² steps.

Pattern Breeder is a slightly different type of cyclic CA. The rule is 00tnm, where t are the states in ASCII(t)-48 = 0123456789:; etc., n is the neighbourhood type 0,1=vN 2,3=M or 4,5=r2, with the odd numbers including the centre cell, and m = 0, 1 gives the count of non-zero mod t and the neighbour sum mod t respectively. The default 00=00200 makes a cell alive if an even number of neighbours in the NSEW vN neighbourhood are alive. It is best shown off with a good starting configuation e.g. running BBC2 to make a small seed fractal using rule ;;t and then running pattern breeder using start array option s, where it replicates the seed patterns. The binary von Neumann rule Fredkin2 12510010110011010010110100110010110 is formally identical to pattern breeder 00210 or 00211, and Fredkin3 in the rule table is identical to 00311. Fredkin life 1357;1357;2 is likewise identical to 00240 or 00241 and the Winograd replicator is identical to 00p01 where p is a prime. Pattern breeder thus forms a model of all these replicator types. You can verify the identity with the Winograd relicator by using my image file chris.txt as starting array and inputting 00;01, using CA2D's ASCII encoding, since ";" counts as 11, the prime number of colours in the 121x121 image.

Diverse Rock-Paper-Scissors dynamics: Lower left, 00111+..0100 r generates two classes of demons the narrow ones dominant over the disordered milieu and the wider ones developing from flaws in the former recessive to both. The random seed states generating these demons cannot come into being once the dynamic has reached cyclic evolution. Upper left: Two competing strategies '+..' and '+.-' in 0123+..11002+.- x1 under Special colour coexist intermediate term, with regions of CBK stratification building up around the WMR strategy. Centre: 0112+..1090 x2 shows the effects of 10% mutation facilitating regions of local dominance as well as evolving cyclic fluctuations of the overall population between the three states under iteration. Right (bottom to top): Two player RPS strategies in in 0122+..11001-.. x2 showing rapid takover in which the backward '-..' strategy of WMR engulfs the forward strategy "+.." of CBK, with large-scale cycling regions expanding until one reaches overall dominance of with fine-scale cyclic stratification, illustrate the differing strategies of cycle-forward-on-lose and cycle-backward-on-lose. It has been noted that counterintuitively moving to the next weaker state on losing can be a winning strategy in the real game. Far right: Long term stability between '-..' and '.++' in 0121-..11000.++ r. although each perturbs the other's stability along their boundaries, resulting in internal evolution of the states and engulfing of smaller regions of each strategy, leading to ever larger regions of dominance.

Rock Paper Scissors explores options focussing on the three state game in which

. The rule is 01staaanpqrubbb where s sets the game play: s=1 examines a single strategy applied to the three states and s=2 plays off two strategies against one another. t is the threshold of neighbours beating the centre value summed over all neighbours (counting both winning and losing neighbours as +1 and -1 respectively). The next 3 entries aaa set the strategy for lose, draw and win. '+' increases the state by 1 when (e.g. stone to paper), '.' leaves the state unchanged, '-' decreases (stone becomes scissors) and 'r' chooses a random one of the three states. To do this s=2 plays a six state game where pixels labelled 012 move using the settings aaa, 567 are determined by bbb and the threshold u is invoked which operates to switch between strategies if a cell is dominated by the other strategy and losing. Using special colour here shows off the contrasting strategies by adopting BCK for 012 and WMR for 345. n = 0 or 1 gives the neighbourhood type vN or M and pqr gives the probablility of mutation p.qr for a given cell at each step into one of the three os six states respectively.

An example showing the effects of mutation 00111+..0100 proceeds from random to demons, while 00111+..0090 has oscillating regions of dominance. You can use the start condition xn n=1-9 to generate a random start array exponentially biased to give more 0 values than 1s and 2s to test for fluctuations in RPS. yn acts likewise to bias towards high values. These may take a few seconds to initialize as they repeatedly use an extended exponential function floor(exp((float)n*exp(1)*((float)rand()/(float)RAND_MAX-1))*3 at every point. For example x2 gives highly unstable processes with 0112+..0099 and the inverse process 0112-..0099. 0112+..1099 gives intermediate-range oscillations of dominance.

RPS also illustrates certain prisoners' dilemma like evolutionary games, in which for example in sexual selection we have cooperation, deception and defection forming an RPS game. Deception arises both because females need to avoid putting all their eggs into one possibly inferior basket given the huge investments of pregnancy, and because men depend on sewing some wild oats to spread their fertilization investment. Human sexual selection has been closely based on the conflicting investments of females and males in a prisoners' dilemma in which each sex has three such RPS strategies due to Machiavellian intelligence depending on strategic bluffing to create the diverse niches of a complex society. The principal thrust of patriarchy and patriarchal religious traditions is to repress female reproductive choice, which is both pivotal to XY-based sex chromosome evolution and is essential for women because of the huge parenting investment and danger of human pregnancy lactation and child-rearing and the much smaller number of offspring a woman can nurture by comparison with a powerful or popular male. Invocations against adultery are primarily targeted at women as the 'devils gateway' along with dire punishments such as stoning, although men pride themselves in sewing wild oats which is explicitly a strategy of deception of female partners(s).

Left four panels: Infect 29;07;2.0;3.0 starts out random but goes through globular waves then looser and finally tight spials taking over the region.
Right: Infect 36;06;2.0;3.0 shows 5 generations of growing complexity islands, with one spawning spirals.

Infect Cyclic CAs modelling spread of infectious diseases and autocatalytic chemical waves such as the Belousov-Zhabotinski reaction, originally named Hodge-Podge, have more complex cyclic rules involving three additional parameters. A rule is input in the form ss;gg;pp,qq, where ss is the number of states 00 - 99, and gg, pp, and qq determine how the infection proceeds. An infected cell is modified by s/A+gg, the sum of the infected neighbour states s over the number of infected cells A plus gg. A non-infected cell is infected at a level equalling A/pp + B/qq the number of infected neighbours A over pp + number reaching max level B over qq. The default is 29;07;2.0;3.0.

Try 36;06;2.0;3.0 for a fascinatng evolution. It generates islands which grow to engulf the region, growing more complex as they grow, forming several generations. Ultimately one of these islands spawns a spiral which engufs it while it is at the same time engulfing the entire region. 99;04;3.0;3.5 is even more dynamic!

Left: Ink-blot 0428 x1 evolving dominating chaotic excitations from a geomerical fracturing generated by a random initializer.. Right: Yin-yang fire 1526 rs long-term evolution.

Leopard (El Capitan version only) models both reaction-diffusion equations that make the leopard's spots and a couple of somewhat simpler of CAs than infect. The first two share the attribute of many (2^p) states and a quasi-cyclic additive rule tmnp providing for an m = 4, 5, 8 or 9 member von Neumann/Moore neighbourhood following the rule to form the s = the average of the m elements, with subsequent modifications.

For t = 0 we have ink blot by taking c = s + n mod 2^p. The example with initializer x1 and rule 0428 is shown above evolving firstly to form a geometrical set of fractures whose corners and intersections then develop chaotic excitations which can superimpose on both kinds of pattens and gradually take over the dynamic.

For t = 1, we have yin-yang fire, which follows the rule that if the current state c satisfies c + p >= s, c -> c-1 and if c < 0, c -> 2^p - 1, while otherwise c -> c+1. This iterates in a way which induces both smooting averages and bursts of discrete pixelation forming long-standing waves of excitation with a slow evolution. For example 1526 with initializer rs is shown above at three stages of long-term cyclic evolution.

For t = 3 we have simplified reaction-diffusion c -> c+((N+S+E+W)-(NE+SE+NW+SW)/n)/m mod 2^p.

Top two rows: 4001: 997765453628, 508075454020, 508565454030, 506852444350, 508565454038 504560505050, 506070551060, 506065453020, 507255454836,
997765553628, 504560551040, 506070551040, 504263554560, 504560514845, 508057363018, 509906403001, 506040554560, 508765305230 in scale 1.
Bottom row: 5001 50703040, 50755520, 90605530, 99704832, 80704528, 80703828, 99704028, 99704828, 90456235 in scale 6.

For t = 4 the variety of reaction-diffusion dynamics becomes apparent. We have a 16 step command line 4001AaBbCcDdEeFf. This provides a raster model for Turing's equations, where a live cell secretes both an activator, which has high values nearby which decline rapidly, and an inhibitor with lower values nearby which decline more slowly, so that the inhibitor exceeds the activator at middle distances. A live cell secretes both, and a cell comes alive if its neighbours add up to an excess of activator over inhibitor. The code spells out positive or negative values 10*X+x-50 for the difference at each of (a) C, (b) N, S, E, W, (c) NE, NW, SE, SW (d) NN, SS, EE, WW (e) NNE, NNW, NEE, NWW, SSE, SSW, SEE, SWW and (f) NNEE, NNWW, SSEE, SSWW at successively greater distances 0, 1, 2^(1/2), 2, 5^(1/2) and 2*2^(1/2). Example patterns are shown above.

For t = 5 we have the hexagonally tiled version which can be viewed in scale 6. We have a 12 step command line 4001AaBbCcDd as above with (a) C, (b) N,S,E,W, and NE SE or NW SW on alternating odd and even rows (c) NN, SS with NW, SW, NEE, SEE and NE, SE, NWW, SWW on alternate lines and (d) NNE, NNW SSE, SSW, WW, EE, forming a four stage hexagonal neighbourhood which views correctly in scale 6 when the even rows are right-shifted by a half step to restore symmetry. These patterns look more natural, although they are coarser in half-resolution, because circular diffusion regions pack in a hexagonal array.

Left: the CA 600116016032 showing divergences of the dark and light neighbour spectra (blue and red) with the corresponding ones for a random distribution with the same average
dark density (yellow and magenta). Centre: The hexagonally tiled CA 700111013032 (click twice to enlarge) plotted using scale 6. Right: the same process on an ocellated lizard.

For t=6 we have a counting method for 8 Moore neighbours modelling lizard scale pigment patterns (Manukyan et al. 2017 A living mesoscopic cellular automaton made of skin scales doi:10.1038.nature22031 ). The 12 step command 6001abcdefgh defines two polynomial distributions for light and dark cells based on a probabily of switching that increases as the number of neighbours of opposite type increases, based on dark switching with a probability defined by (light/(10a+b+0.1c))^g, and light switching with probability (dark/(10d+e+0.1f))^h. E.g. 600116016032 gives a dark-dominant camouflage with around 59% dark similar to the ocelated lizard, defined by (light/16)^3 and (dark/16)^2.

For t=7 the corresponding system 700112012032 gives a mathematical equivalent of the hexagonal system using staggered neighbouthoods, alternately omitting the NW, SW or NE, SE Moore neighbours on successive rows to give a consistent 6 neighbour tiling. This can be plotted using scale 6 (which actually is hexagonal in scale 2).

Segregation portraits for: 3544351088, 4444440044, 3335183444 and 4426182444, 4435172377 and 4462355518882468 showing different
degrees of tolerance and partitioning of neighbourhoods. The first two explore only two cultures because 0 pixels have been allotted to the first culture.
The right four show a xenophobic yellow culture which can grow large elite communities in the face of the more tolerent green and blue cultures.
In the far right image cultural dominance and prejudice has resulted in a ring of elite 'gated-enclaves' of culture 1
with the underdog 'ghetto' culture 3 permated by small islands of 'middle-class' culture 2.

This example of an agent-based model, originally devised on a game board by the Nobel winning economist Thomas Schelling, explores the way in which small differences in favour in terms of how many neighbours share your culture or values and how many people of alien or different culture exist in one's neighbourhood can radically influence formation of segregated ghettos and elite gated communities. The process differs from a standard CA in that the addresses of the pixels are first scrambled row and column three times Rubik style using a copy of the screen array containing the row and column address of each pixel. This avoids having a spatial bias in the change of positions. Diring the iteration, each randomly placed pixel is tested to see if it is satisfied, by having sufficient in-group neighbours in a 9 pixel Moore neighbourhood, and few enough alien neighbours (not counting vacancies). Of course the centre cell is always a selfie, so required neighbours can go from 0-9, but aliens can only go from 0-8. If the agent is not satisfied, a spiral search is pursued 'SENNWWSSS...' on the screen torus, to seek another site where the agent can be satisfied, either by moving and adopting a good vacant space, or exchanging places with an alien in a good site, who is satisfied to take up the agent's place in return. Of course good places may revert to bad by the action of other random agents, so the process may need to iterate a few times to reach equilibrium.

The process is designed for three coexisting cultures with differing degrees of xenophobia. Different arrangements can be entered into a 10 digit rule string consisting of how many neighbours are required and an upper limit of aliens to be satisfied to remain for each of the three cultures. The additional four places give the relative frequency of vacant and cultures 1 to 3. E.g. the default 4435282356 says culture 1 requires 4 in-group neighbours including their own spot and no more than 4 alien neighbours (not counting vacancies). 3,5 for culture 2 and 2,8 for culture 3. 2356 says 2/16 pixels will be vacant and 3, 5 and 6/16 will be filled for each culture. Setting any of these last four to 0 will remove all vacant places, or reduce the number of cultures to 2. A more searching 16 digit rule string allows each culture to have specific phobias about each other. E.g. 4426355528882356 says that in addition to needing 4 in-group and not tolerating 4 aliens, culture 1 also can tolerate no more than 2 neighbours of culture 3 and 6 of culture 1. 3555 shows culture 2 needs 3 in-group and no more then 5 out-group of any kind. Culture The colours in KRYGCBMW are culture 1 = yellow, 2 = cyan, green = purple.

The asynchronous process scans several indexed columns of randomly scrambled addresses once for each step. You may like to set the speed to max if you are on Scale 1 as it will take 100 steps to complete one full scan of the screen. The search process will abort if it can't find a suitable vacancy 10 times set by athresh=10 in the source code to avoid the process hanging in a search cul-de-sac. When the process has reached abort, or completion, the screen will blink once and the CA will go into idle mode. You can also use the start controls r, s, xn, yn and an input matrix as start conditions to check to iteration more closely. If a process reaches a cul-de-sac and aborts, using s can sometimes take the process further towards resolution. Challenging choices of values can lead to a temporary freeze, with the MacOSX rainbow 'wheel of death' turning at the cursor. A large number of spiral paths are being explored to try to find new sites and the process will abort at the first cul-de-sac.

(Left) Diffusion-limited aggregation into fractal dendritic growth structures with reflectionally and rotationally symmetric flakes
(centre) generated by random gases with the corresponding symmetry. (Right). A fractal gas giving rise to a symmetrical crystal.
Inset: A fractal set of reflecting cells and fractal gas generated using BBC2, then generating an asymmetric dendrite with gas rays.

Diffuse Aggregate is one of a variety of CA models simulating the effects of gases or solutions. This one is also modeling DLA, or diffusion-limited aggregation, resulting in fractal dendritic growth, as witnessed in snowflakes, chemical gardens, dendritic formations on electrodes and a variety of other physical systems. A simulation, is included of a von Neumann neighbourhood gas causing fractal growth on a single seed. The rule table includes instructions for bouncing off boundaries, for free passage of the particles through one another except for two horozontal or vertical particles colliding, when horizontal and vertical switch, and for aggregation events onto the crystal, when a particle touches a dendrite tip or side. There are more elaborate 'realistic' lattice gas CAs, on Margolus neighbourhoods, or with honeycomb hexagonal arrays, giving diagonal motion as well, but this example gives a good generic idea of the process. Use Special colour to see the process in strict gas particle colours.

If the rule input has an r inserted a small number of particles are allowed to randomly leak into the vacuum to make up for the loss of particles to the crystal. You can also add fractal seeds, along with an input array of gas molecules and reflectors into the start array. Gas particles are 1>W, 2>N, 4>E, 8>S in a space of 0's. Numbers up to 15 are superpositions of these particle motions. 16 is a stationary reflector and 17 through 33 are reflectors that are about to emit a particle with 1>W, 18>N, 20>E, 24>S with numbers between 19 and 32 being a superposition as before emitting a single volley, with 32 being a passive sink and 33 continuously emitting 'gas rays' of particles in all four directions. 34 is a static crystal cell in the aggregating fractal.

If you input fn, n = 0-3 into the start array, the process will generate a reflectionally (0,2) or rotationally (1,3) symmetrical gas and crystals, with reflecting barriers for n = 2,3. f alone will remove the reflecting barriers from the non-symmetrical random default condition.

You can also generate a fractal gas by using a fractal CA such as BBC2 set to 5 states using rule ;;5 as a seed, and then switching to Diffuse Aggregate on f 4-7 which also replicates a sector of the fractal. Other numbers of states are spectrally modularized to 5. This array rule replicates f 0-3 above, but using the values of a five state fractal to define the four velocities and the vacuum. The f rule ensures symmetry by replicating fractal or random information from the lower right sector to the other three, with appropriate symmetries in the velocity transformations. To set up the symmetrical gas states, this CA is set to idle in the first step so to go a single step at a time you need to set s for start array and 2 for steps rather than the usual 1.

This system can have very surprising consequences when initial conditions not anticipated in the model arise, which can destroy the apparent symmetry of the rules. For example concentric rings of NESW particles break symmetry because, as they move in different directions, some parts collide and others don't, destroying the apparent symmetry. Two opposing particles collide only if they arrive on the same square at the same time. If they arrive one square apart they will pass right through in the next step as the difference in their velocities is two steps. Fractal structures involving different reflecting boundary states can end up emitting continuous streams of particles if they include a 33 cell, which acts as a continuous particle source in all four directions. To see these effects, try running BBC2 or random growth on rule ;;35 e.g. for 50-54 steps and then run diffuse-aggregate on start array s. The fractals will not be symmetric although BBC2 is symmetric, because the same number in symmetric positions results in asymmetric motions, as direction of motion varies with cell number.

You can enter a life rule for life-like CAs on a Moore neighbourhood under Life/Generations in the form bbb;sss;g where b are the birth numbers of neighbours s are the survival numbers and g is the generations. +/- can also be added at the beginning i.e. +bbb;sss;g if one wants to count the centre cell in the tally. - is the default.

Life-like These have rules stipulating the number of neighbours in a Moore neighbourhood for a cell to be born and for it to stay alive. The form of the rule is aaa;bbb where aaa are the numbers of Moore neighbours to give birth and bbb to sustain life.

The Game of Life itself is 3;23 meaning that a cell lives on if 2 or 3 Moore neighbours are alive and is born if 3 are alive. These two very simple rules have unboundedly complex consequences as the game-of-life is a universal computer and can replicate any computational process.

Other good examples you can explore using the rules are Seeds 2; Life without Death 3;012345678 Day&Night 3678;34678 and Diamoeba 35678;5678. Life-like automatically have 2 generations live and dead, and are coloured by age, however the same rule with ;2 appended, e.g. 3;23;2 for life gives the 2-colour version. You can explore a diverse variety of life-like CAs in by choosing further rules from the attached list of life-like rules.

Some life patterns wil last forever uninterrupted. Other have record finite lives before stabilizing. Life and life/generation CAs begin by default with the R-pentomino for classic Life, which takes 1103 generations to stabilize. If you enter e in the start matrix for Life, you get record methuselah edna taking 31192 generations to stabilize. Or you can paste it as an array. A spaceship is a pattern that returns to its own configuration after a finite number of steps, but translated, thus forming an immortal process which strictly speaking never revisits the same condition. The smallest is the glider below.

(a) Twins pre-block and grin both lead to a block. (b) The smallest known orphan state. (c) R-pentomino. (d) Edna. (e) Glider.

A Garden of Eden is a state in a CA which has no precursor. An orphan is a finite pattern that cannot occur as part of the evolution of another pattern. They are thus Gardens of Eden that can be extended in any way to form other Gardens of Eden. A cellular automaton is injective over finite patterns (locally 1-1) if no two distinct finite patterns map into the same finite pattern. It is surjective (onto) if every pattern is mapped to by some other pattern. Thus, by definition a CA contains Gardens of Eden if and only if it is not surjective. The Garden of Eden theorem states that CAs are onto if and only if they are locally 1-1. In other words, a cellular automaton has a Garden of Eden if and only if it has twins - two different finite configurations that evolve into the same configuration in one step. Pre-block and grin above are twins, so the game of life has orphans and Gardens of Eden. The smallest is the Garden of Eden 6 orphan pictured, found in 2011.

Try copying and pasting the spacecrazy array directly from text edit and starting Life/Generations for the classic game of life in scale 1-4 and you will get a gosper gun gradually taking out a delicate fleet of caterpillar spaceships traveling at varying speeds! See also the fortress and changing lines.

You can also generate a classic example of Day and Night guns and anti-guns shooting it out by pasting gunantigun into the start array and using 3678;34678.

Because the game of life is a universal computer, one can replicate any computational process, given an appropriate set of initial conditions on the game board. A life board has been designed to simulate a Turing machine, with a CPU and memory later extended to a universal Turing machine, as well as another numerical calculator, Minsky's register machine, and large tiles have been made of life arrays which can replicate any game-of-life process on a hugely expanded 2048x2048 scale, taking 35328 steps to complete one meta-step showing the universal computer can also construct a universal game-of-life computer. For off and on templates which can be tiled and run, see the OTCA metapixel, and several pre-tiled example boards. All these simulations can be run in the versatile CA Mac/Windows app Golly.

Left and Centre geneation CAs. Left: Bombers 24;345;25 set off using ThrillGrill 34;1234;48 as initializer. Centre: Brain 2;;3, initiated from a symmetric random state rs is a classic generations rule modeling an excitable medium such as brain tissue, which has many types of colliding and regenerating structure. A receptive cell (0) becomes excited (2) if two neighbors are active, then undergoing a latency step (1) before again becoming receptive (0). Right: Hex life from a random start.

Generation Generation rules aaa;bbb;nn add a specific number of generations nn to the birth, survival rule. You can also input any of the "generations" CAs, which have some of the most interesting dynamic properties, like brain, by inputting an extended life code. Life itself is equivalent to 3;23;2 because each live cell will die in the second generation unless sustained. For example brain is equivalent to 2;;3 and space wars to 2;345;4. This gives life with aging rather than death, colour coded by age. Dead cells come alive and then age steadily until they reach the lowest state where they are again assessed for survival as live. The last number, anything from 2 to 48 or so, gives the number of aging states. Attached is a list of established generation rules.

Mirek's rule 2;345;4 from the list can be used to generate a neat steeplechase of 'worms' if you copy and paste the steeplechase text array. View in scale 4.

BBC2 and Random Growth are useful precursors which will assume the same number of states as the last parameter in a generations type rule preceded by two semi-colons by inputting e.g. ;;6 or 12;345;6 into either BBC2 or Random Growth, which will then have 6 states. This means one can switch to generations 12;345;6 with s input for starting array to continue from a radom or fractal island with the correct number of states. For a life-like game you can initally set ;;2 for 2-state random. For a larger number of states, in life-like CAs, random growth acts as a random-edged block which can result in interesting dynamics developing around the edge, where 2 and 3 neighbours prevail.

Hex Life A hexagonal CA similar to the game of life can be explored using Hex Life at the end of the CA list with Scale 6. The dynamics can be viewed by using the default initializer 'r' to see a variety of colliding gliders. You can also input initializer 021000010000110000201000110000022000 to see an initiailzer for a hexagonal spiral of simple gliders. All of the following produce glider arrays: 2, 1200, 212121212, 222222222, 0111021000022222100001110 a glider gun and 2222222222222222 generates a complex system of gliders with symmetry under a half revolution.

This is a 3 state system where a 'dead' 0 cell comes alive, 'young and frisky', with value 2, if there is one 2 in the neighbourhood and no 1s - close to panspermia. Any cell becomes an 'aged' 1 if it has one 1 and one 2 neighbour, or two 2 neighbours, and becomes a 'young' 2 if it has three two neighbours. All other live states die. 2s are 'youthful' reproductive live cells, as they can both bring dead cells alive and also turn 1s into 2's. 2s can also 'age' to 1's. 1 cells can't generate anything themselves, but can become young again if they have three young 2 neighbours. The rules combine to drive the system close to the edge of chaos.

von Neumann 2D automata from the rule file: tanks, strata, knitting, aggregation and typhoon each from a random beginning.

Binary (n-Ary) Rules You can input a binary rule for a von Neumann or Moore neighborhood using the rule tscnnn and select Neumann to portray a variety of well-known von Neumann neighborhood rules of up to s = 8 states or Moore up to 4 states and centered Moore up to 3. The first number t = 1-2 gives the rule type, binary =1 or totalistic 2), s = 2-8 is the number of cell states, c gives the neighbourhood type 4 is vN 5 is centered vN, 6 for hexagonal (use scale 6), 8 for Moore and 9 for centered Moore. The remainder nnn... give the value 0 ... s-1 for each of the s^c neighbours in n-ary format with the bit order C,N,E,S,W,Nw,Ne,Se,Sw, or the (s-1)*c+1 summative states, adding the values of neighbours, for totalistic, since the largest possible sum is (s-1)*c and the smallest is 0.

Fredkin2 12510010110011010010110100110010110 will reproduce any 2-bit pattern. Try for example 101010101 in 4 steps and 0001001101011111 in 8 steps as symmetric and asymmetric initial conditions.

The game of life is also definable as a binary 9-cell Moore neighbourhood binary rule with 2⁹+ 3 = 515 entries listed in the rule table.

The Greenberg-Hastings rule is one of the first CAs to make spiral waves based on cellular excitation. A cell has three states 2=excited, 1=refractory and 0=resting. Excited > refactory > resting and resting becomes active if there is an excited neighbour. Two versions of the rule are included in the rule table. One can enter a single 2 to see an expanding diamond, or a matrix with a row of 1s and then a row of 2s e.g. 111111222222000000000000000000000000 into the starting array to see two interlocked spiral waves emerge.

Another three-state rule of significance as a universal computer and constructor is that for the Serizawa CA. This is also listed in the rule table. You can use three initializers delay.txt, splitter.txt and and.txt to see three logical functions executed. The rule table repository includes a paper by the author (in Japanese) listing all the logical interactions including the AND circuit, pulse generator, signal-line, delay circuit and memory circuit. Finally, the structure of the self-reproducing machine is shown, which is realized by combining those circuits. It can also be operated as a universal construction machine or a universal Turing machine.

The simplest randomly generated rules can have surprising results. Randomly generated rules using 124r1nnn, nnn=331-600 show diverse fractal and compuational process with varying symmetry, some beginning with 101010101 (*) and the rest with 1 (default) iterated around 60 times. This simplest system with only 4 neighbours, each in 2 possible states, is ideal for exploring random structures, because the state space contains the smallest number of random degrees of freedom, allowing structured effects with higher probability without being confused by overlapping effects. They show a variety of symmetries and multiple fractal effects. For example 1241110001000101011 top right of centre has both triangular Sierpinski gaskets and a rectangular fractal similar to 1241000001001010100 below, whose right edges generate a chequerboard of smaller triangles. A few e.g. 1241100101110000110 upper left appear to be setting off 1D-like computations in their interior.

Totalistic Rules: You can also enter a totalistic type 2 rule for a von Neumann or Moore neighbourhood such as 245330323313023033122121 where the sum of elements for all the possible sum respectively are specified. Many of these result in distinctive fractals as shown below and a few make obvious Fredkin CAs.

Left: Random fractals generated from a single live cell using search 285r1000 iterated 60 times each. Right: A Hex fractal generated by 586r1331 in 40 steps and its reversible counterpart.

Random Searches: You can also perform random searches of these states using the formula tscrunnn, where t is the type (binary=1 or totalistic=2) s is the number of states, c = 4, 5, 6, 8 or 9 is the neighbourhood type, r is for random search, u = 0-11 is the search type and nnn is the probability parameter 0.nnn of live non-zero states biasing the search.

Symmetries in 4-state vN 4-cell CAs: 144r2000 rotate90, 144r4000 reflect axes, 144r6000 reflect diagonals, 144r:000 rotate180,
144r8000 rotate90reflect, and 144r<000 bilateral.

In type 1 non-hexagonal binary systems, you can assign a rule type u = 2, 4, 6, 8, (or : , < for 10, 12) which forces symmetric rules 2 = rotate 90, 4 = reflect axes, 6 = reflect diagonals, 8 = rotate90reflect, 10 = rotate180, 12 = bilateral reflect x. Adding 1 to these e.g. 3, 5, 7, 9, or ( ; , = for 11, 13) results in a biased search favouring lower valued states in roughly the same probability ratio as nnn.

Types u = 0, 1 ignore symmetry constraints and work for all type 1 neighbourhoods. If the search rule is set to 6 instead of 1, rules will stipulate that if all neighbours have state s they will continue to do so to avoid flickering regions. The actual rule will still be type 1. E.g. 144r1500, 125r<331.

Random 2 state CNESW vN CAs from a random start display both topological and geometric structures. The left-hand images show how the
regime can split into competing domains with agitation on the boundary reminiscent of domain-wall bifurcations in the symmetry-breaking
of the forces of nature in the early universe. The lower one maintains hanging threads of activity over thousands of iterations.
The deep chaos of the second below shows another manifestation of the physics of order and disorder. Rules used.

Totalistic CAs automatically have full symmetry, so using values of u above 0 and 1 has no net effect. Setting the probability nnn to 000 gives an entirely unbiased random search over all states. For totalistic CAs 265r2000 or 385r2000 give unbiased random numbers on von Neumann and Moore neighbourhoods and many become fractals starting from a single live cell. Each generated rule can be copied from Rule Out into the rule field to explore it further. You can use a simple matrix such as 101010101 or generate a matrix e.g. using BBC2 with rule ;;s for s states, as an initial condition to explore searches like 145r2331 or 285r2600. If the rule is set to 7 instead of 2, search rules will stipulate that if all neighbours have state 0 they will continue to do so to avoid flickering regions in the type 2 rule.

Left: A reversible second order 425 2D CA rule used and the corresponding first order 125 CA. In this case, both form fractals from a single cell. Centre: (left to right): (a) The second order CA of the game of life shows its reversibility with a 'pulsar' cyclic fractal from 101010101. (b) The intitial condition 1001011001101001 leads to an expanding fractal and a sparse random start (c) also leads to expanding regions of activity, quite different from the game of life CA. Right: Three reversible CAs showing their less 'evolutionary' dynamics. Rules used.

Second Order Reversible 2D CAs Finally, you can set the search rule type, or actual rule type, to 4 or 5 to invoke the corresponding second order 2D reversible CA for rule types 1 and 2. This is generated by logically subtracting the grandparent state two steps back from the new state generated from the forward rule resulting in an invertible function q_t₊₁ = rule(qⁱ_t) - q_t_-1 for which time can be reversed. It is harder to find distinctive patterns with these CAs from a random start, but they do show clear correspondences if the original forms a fractal from a single live cell. You can also use 9 or ':' for 10 here to invoke the 'no-flicker' options noted above.

There are a number of highly coded von Neumann type CAs (distinct from the widely used von Neumann neighbourhood) available in applications like Golly which carry out coded replication of existing structures and are thus able to duplicate themselves to varying degrees.

Byl Loops To include a rather beautiful generic root example of an elemental self generating structure, we include the Byl loop, in which a single small looping region is able to generate a grid of duplicates of itself as shown in the above figure. The rule table consists of 61 neighbourhood instructions, each in four orientations, consisting of four inner cells forming a very simple code sequence instructing the formation of further loops. Special colors gives the standard Byl Loop colors 0=black, 1=blue, 2=red, 3=green, 4=yellow, 5=magenta.

This is a generic reduction of the original design of Langton's loops, themselves a modification of Codd's CAs, which, like the game of life and 1-D rule 110 (see below) are capable of universal computation and are in turn a simplification of a type of CA originally developed by John von Neumann with the aim of developing a self-replicating universal constructor. Golly and the rule table repository have a number of examples of this class of CA, which can be ported back to Golly for investigation.

Sexy Loops A second more challenging example, derived from Langton and evolutionary Evo loops are F-sexy Loops, which have a similar root form to Langton's and Codd's original structures, but allow for transmission of genetic information between loops using a cell type (9=orange) encoding an elementary sexual gene concept. The loops bounded by red (2), form channels for the movement and transfer of this genetic information and for natural selection of loops with variant genetic information. It further provides an elementary model to test the evolutionary survival of genetic elements providing sexual transfer, such as the F-factor bacterial plasmid.

You can independently utilize a series of alternative initial states such as sl2, which has two loops, the upper left one carrying the sex gene. Other examples check out critical processes discussed in Oros and Nehaniv's research paper to verify the CA, such as introducing the sex gene with and without error correction. The rule table contains two rotationally invariant schemes, one covering all states apart from 8 and a second to model the dissolver cell 8. Color Special gives the original 12-color coding for F-Sexy Loops: 0=black, 1=blue, 2=red, 3=magenta, 4=green, 5=cyan, 6=yellow, 7=white, 8=gray (dissolver), 9=orange (sex gene), 10=pink (signal blocker), 11=dark gray (error correction).

Winograd Replicator One of the simplest systems of all developed by Terry Winograd is counter-intuitively capable of generating replicates of any image. Generalizing the Friedkin replicative life game 1357;1357, and the patter breeder, we have the rule, which says for any prime number p of states, C(out) = sum(NSEW) mod p. The included rule Default sum is set to replicate a simple 9x9 heart pattern in 3 colors at steps 9, 18 etc. For a more interesting effect the 121x121 template chris.txt is included which can be pasted into the start array with the rule set to 11 for 11 states using Special color, resulting in the above cloned image set, at the 121st and 242nd steps.If you want to use another image with say 7 colours and a 49x49 image, you need to set the rule to 07 not 7 to get the algorithm to recognize it.

To make the original image, I used Photoshop to turn the 121x121 RGB jpg into an indexed 11 colour image, and saved it as a gif. I then imread it into Matlab and printed out and copied the ensuing colour index matrix as text strings of characters "0123456789:", which Special recognizes. The source code could be edited to allow for any other colour scheme.

Left: Maze Solver solving a simple maze, showing the arrow directions in different colors (greens flood fill, magentas back path). Live ends of the flood are the single cells in white. Start and finish are the single red and yellow cells. Right: Maze Solver solving a more complicated maze generated by using the life-like 'maze' CA 3;12345;2 starting from the life-CA default R-pentamino with start and finish points (194,299) and (627,300). The flood fill is in magenta and the return path in yellow. Most, but not all of the toroidal universe is accessable from the starting point showing the maze is connected and non-trivial but contains a large number of disconnected islands.

Maze Solver An intriguing CA developed by Adam Goucher performs a flood fill of a maze. The rule table keeps hidden track of the directions used in the fill, enabling a reverse path to be traversed via the reversed arrows from finish to start. The default is the start array maze.txt. Special color shows the flood fill and return path but the default KRYGCBMW shades so the arrow directions can be distinguished, so you can see how the CA works, as illustrated above. There are a set of larger more complex computer-generated mazes in the mazes folder which can be pasted into the start array. You can generate more here. Note that the flood fill is quite happy with mazes with irregular shapes, as long as there is a vertical or horizontal connection between adjacent cells.

Maze solver can also solve pseudo-mazes generated by another life-like CA. Run the Life/Generations 'maze' CA 3;12345;2 from a seed and then set start array to sxxxyyyXXXYYY where xxx and yyy specify the x and y coordinates of the start point and XXX, YYY those of the finish point. Then Redraw with Maze Solver to see a CA solving a CA-generated maze. The above image was generated using the default R-pentamino (start array 011110010 has the same effect) with Life/Generation CA 3;12345;2 and then solving using s194299627300. You MUST use three digits for each coordinate e.g. 020 for 20! The same coordinates will also give a successful solution for the maze with seed 1010111011011101 and you can use s387062665204 with seed 11100011111001010101010101 and s002004399197 with seed 1101110101101110110101. You can also try 'mazectric' 3;1234;2, but this is not as capable of generating a global maze. Starting array 0101010101110111010101010 leads to a pseudo-maze with fourfold symmetry, but this has fragmented into a number of larger and smaller open islands islands in a closed ocean, forming a phase transition from the condition of the maze CA shown above, which admits percolation through the toroidal space within the global network and has closed islands in an open ocean.

If you initialize with s, or smn, Maze Solver will use a random set of start and finish points and attempt a series of local solutions with around m start points and mn finish points. The most probable number is m, since aorund half the screen points are corridors and two points are chosen at random on the screen. The default mn is 12. Any start point will locate paths to many finish points, but the flood fills from individual start points overwrite the corridor zeros with vector directions, so they will exclude one another, even if the mazes do connect.

The first Redraw of Maze Solver in Special color gives the life maze inverted in colour, drawn with the corridors black, the barriers white, the start green and the finish red, and then flood fills it in magenta and reverse solves it in yellow. Using Redraw repeatedly with Maze Solver inverts live and dead cells, so that the corridors are swapped with the barriers, making a complementary (generally inferior) maze.

If you have just generated a life maze and want to find suitable start and finish points, switch to Special color and inputsxxxyyyXXXYYY in Maze Solver, as above, using 0 steps. You can then check and adjust the start and finish positions non-desructively, preserving the initializing maze. The two points will be highlighted green for the start and red for the finish, as before. They will be displayed only when the component they are assigned to is black, so you may need to Redraw twice to flip complements to be sure where each of the two points is. You can then adjust the positions until you have the pair on the same component (generally the actual one constructed by the life maze). You can then Redraw twice, with say 9999 steps, to actually solve the maze in this configuration. The standard size screen is 797x399 in scale 1.

Sand Pile gives a vertical view of a Per Bak sand pile CA which exemplifies self-organized criticality to the critical angle due to fractal avalanches. The CA values represent local slopes rather than the height of the pile, so all tend to the critical value. Whenever a slope exceeds a critical value, an amount is subtracted from the cell and a quater of the amount added to each of the the neighboring NSEW cells.

Left: Rule 110 has universal computation. Just as gliders can operate in 2D life to carry information and induce logical operations, so can sloping glider patterns in rule 110. Centre: The 23 initial state shown for the totalistic rule 2433311100320 takes around 1000 iterations to die out. It is unknown if the stalactite starting with 11 ever finishes. Right: Cyclic and stratified outcomes of the 1D cyclic CA 3871.

Although CA2D focuses on 2D automata, 1D automata provide a very good space-time view of how CAs work. Moreover some of the simplest, like rule 110, possess universal computing capacity, like the game of life.

You can enter codes for a 1D CA using CA type 1D Rule in the form tscnnnnnn where t is the rule type, s is the number of states (2-9 but 5 for c = 7) and c is the number of cells used (3, 5, or 7) followed by the array of numbers 0 ... s-1 defining the rule. You can use a start array as previously, either an r for a random start row or enter a 1D array. The display will fill the first screen and then continue to scroll slowly a line at a time if you have steps set above 0. If you set s for the start array after the process has begun, pressing Redraw will instantly produce successive screens of the CA.

Binary t =1 lists the full binary code for a CA. c = 7 s <= 3, c = 5 s <= 5, c = 3, s <= 9.

For example the famous rule 110, which like Conway's life is capable of universal computation, so can model any process a Turing machine can. It lists as 12301101110 where 01101110 is binary for decimal code 110 with each of the 8 binarys determining one of the 3-neighbour 2-states since 2³=8. If there are 3 or 4 states the rule string will have s^c values each up to 2 or 3.

Similarly rule 30 = 12300011110 is digitally chaotic. It displays sensitive dependence on initial conditions (two initial configurations that differ only in a small number of cells rapidly diverge), its periodic configurations are dense in the Cantor space of all configurations (there is a periodic configuration with any finite pattern of cells), and it is mixing (for any two finite patterns of cells, there is a configuration containing one pattern that eventually leads to a configuration containing the other pattern) and there is a dense orbit (an initial configuration that eventually displays any finite pattern of cells). It also displays patterns similar to some mollusc shells.

Rule 90 = 12301011010 also has root significance. In each time step all values are simultaneously replaced by the exclusive or XOR of the two neighboring values.

If we go to 5 neighbours, rule 3283936144 or 12511000011101111001110001110010000 with a random start gives 3D-like 'tetrahedrons'. A short list of some 2-state 1D-rules.

Examples of elementary 1-D 2-state CAs include four types in Wolfram's classification: (1) Eventually fixed (136 = 12310001000) (2) Periodic often as a result of finite separated regions (73) (3) Chaotic with aperiodic patterns and (4) Complex system potentially capable of universal computation (110 in previous image). Behavior can depend strongly on initial conditions. 90 forms a Sierpinski gasket on starting from a single live cell but more complex structures from a random start. Likewise 73 = 12301001001 becomes finite periodic from random beginnings but appears to be chaotic from a single live cell as it doesn't generate the cell combinations leading to confined periodicities..

Totalistic t = 2 is a type of totalistic rule, summing the 3 to 7 neighbours above and providing an entry for each possible sum. For example the famous stalactite has code 2433311100320 with starting matrix 23. Other interesting codes are 2430002213310 1, 2430003211310 r, 2430000131210 r, 2530000004200410 r or 1. You can develop other rules using the random search routine below.

Cyclic t = 3 is a cyclic rule to illustrate time evolution of cyclic CAs. The rule has the form tscn where n is the threshold (see 2D cyclic). For example 3871 leads about half the time to cyclic dominance, while 3471 leads to stratification. 3971 is on the borderline with most random states stratifying, but a few becoming cyclic dominated.

The second order reversible CAs (below) corresponding to rules 110 (12301101110), 30 (12300011110), 90 (12301011010), 13 (12300001101), 73 (12301001001), 146 (12310010010), 18 (12300010010) and 161 (12310100001) (above). Notice the triangles are now on their sides and the square and diamond shapes which enable propagation in both directions.

Second Order Reversible t = 4, 5 portray the second order reversible 1D CA derived from a type 1 or type 2 CA rule. E.g. 110 = 12301101110 becomes 42301101110.

Reversible CAs can be run backwards as well as forwards, unlike all the other systems we have looked at, where many different states end up with the same values. You can also search for and explore these e.g. using 423r1500. You can likewise run the second order versions of type 1 and 2 2D binary and summative CAs although it is harder to see the difference with 2D because you don't have a space-time portrait, as in 1D CAs.

The Reversible 'Black Hole Big Bang': Above and middle: The second order reversible CAs 42300011110 and 42300011101 rotated so we can see a longer sequence of iterations generated using 'r' as initializer with iteratons set to 0 so a single page of iterations is generated, have been then reversed (symmery line centre-left) using Redraw with initializer 'st' which reverses the automata by copying the second to last iteration over the last one. This leads the automata back to their initial condition (centre-right) .We can then issue Redraw with 's' to see the automata proceeding back before their origin. When we do this, we find the second iterate comes out to a 'black hole' row of zeros, because we had no predecessor 0 state to subtract from the first iterate, so by default subtracted nothing. Notice that the upper automaton is entirely symmetric through the 'big bang' at time 0, while the lower one has major asymmetric anomalies surrounding the zero point. Both these effects are abolished if we initialize using 'rr' which gives random values to both the first and zeroth iterations. Below: The CA 42300100101 (Wolfram 37R) generated with initializer 'x4' has become famous because it is capable of extremely long periods of non-periodic behavior, as high as 293,216,266 iterations, before periodicity ensues, but it does not appear to approach a random (ergodic) distribution exploring almost all possible configurations numbering around 10⁶⁰ for a size 100 1D automation. It has thus been cited as an example of a system which is micro-reversible but does not fully obey the second law of thermodynamics. Click figure to enlage to actual size.

The second order system behaves quite differently from the original type 1 binary CA. They are like conservative dynamical systems, as opposed to dissipative systems with sources and sinks. They have interesting applications in physics and low-energy computing. For two state systems, they are generated by taking the XOR(c,g) of the current result c of the type 1 CA rule with the grandparent centre state g two steps back. For more than 2 states, XOR is equivalent to a cyclic permutation of the states, taking (g-c) mod s.

The second order system is invertible, because, although the CA rule equation q_t₊₁ = rule(qⁱ_t) generally invokes a non-invertible function, in which the reverse direction may either have cases where there is no solution because the rule is not 'onto' (as in the game of life 'Garden of Eden' states which have no precursor), or multiple ambiguities if the rule is not 'one-to-one' (as in pre-block and grin twins in life which both lead to the same block). However the second order equation q_t₊₁ = rule(qⁱ_t) - q_t_-1 is automatically invertible, since we have the immediate solution q_t_-1 = rule(qⁱ_t) - q_t₊₁.without having to invert the transfer rule function. Reversibility restricts the properties of CAs of a given dimension, but they are clearly able to have complex local interactions (Toffoli & Margolus doi:10.1016/0167-2789(90)90185-R).

More generally, it is possible to generate a reversible (n+1)-D CA which replicates the properties of a given n-D CA. Each n-dimensional slice of the new reversible rule simulates a single time step of the original rule making it possible to show reversible systems have the same properties such as universal construction and universal computing (Toffoli doi:10.1016/S0022-0000(77)80007-X).

Random searching. You can also input a random rule for types 1, 2 and 4 in the form tscrunnn (n=000-999) e.g. 143r1500. The first number u gives two random search statistics with and without symmetrization. The last number nnn chooses a three decimal place number 0<=p=0.nnn<1. E.g. for type 1 try 143r2331 and for type 2 try 243r1000, or 263r2700.

Both statistics aim to set a given probability of live states, based on the idea of Chris Langton's edge of chaos lambda, suggesting a proportion of live states around 0.331 is at the edge of chaos, so it sets a random sequence of non-zero numbers 1 - s -1 and then randomly masks a proportion p of these to 0. This gives a wide distribution of individual codes biased logarithmically towards smaller values. If p = 000 an unbiased random rule is generated.

Statistic A u = 0, 2 gives a flat distribution of values for the non zero entries. Statistic B u = 1, 3 gives a biased exponential distribution of the non-zero entries based on r.e^k⁽^r^-1) k~sp/(1-p) which gives more low values ased on the lowest approximating to p.

u = 2, 3 pick only isotropic, type 1 rules, which play out palindromically as they have the same value e.g. for 110 and 011. They thus give rise exclusively to symmetric rules. They are of no advantage with type 2 which are already isotropic and limit the search here.

E.g. 143r3331 gives an interesting set of complex systems on repeated itinitalization with r as the initial condition. You can see a similar approach in David Eck's edge of chaos Java jar applet.

These help to search for complex systems at the edges of chaos. When steps are set to 0 you can then click Redraw to journey through a random series of CAs to explore their properties. If you input s in the rule the random rule will be preserved so you can explore it using Redraw. The rule generated by a random choice appears in the Rule Out field so you can copy it for later exploration. You can also copy the initial random state from Init Out so you can fully replicate the long term evolution of a particular CA.

For example the rule 133010000002120000001000000210 generated using 133r2331 develops stalactites sometimes lasting over 170,000 iterations using the standard width of 797 cells. Copy and paste the first array in stalactite2.txt, set steps to 0 and Redraw 341 times to see one which takes around 136117 iterations to die out. In this CA there are just the following rules for live states: 100, 001 221, 122 > 1, 121, 200, 002 > 2 compensated for by a corresponding asymmetry in the zeros with 112, 211 and 212 > 0, as well as all the remaining codes. The second array has an infinite stalactite because the iteration eventually becomes periodic after about 31841 iterations entering a period of roughly 98307 iterations on the finite 797 cell screen cyinder. Although the process has a simple Markov-like transfer function between the two live states, it is highly sensitive to initial conditions.

Mirek and Golly use slightly different rules but many of these examples will also run as rules in this format.

1D Life-like and Generation You can also enter a 1D form of any life-like or generation formula using the following format extending that for the 2D version bbb;sss;g;n where b give the number of cells required for birth, s for survival, g is the number of live generations and n gives the neighbourhood size 3, 5, or 7. The maximum number of live neighbours not counting N which plays the role of C here, are actually 2 for a 3 neighbourhood, 4 for a 5 neighbourhood and 6 for a 7 neighbourhood. +/- can again be included at the beginning, i.e. +bbb;sss;g;n, if one wants to include the centre cell in the tally. e.g. try 12;23;20;7, 123;234;4;7 as well as 2;456;2;7 and the default start up 2;24;2;7. Compare + and - varieties of 245;034;7;3.

Shell Pattern CAs By selecting Shell you can also run a variety of 1D CAs modeled to represent the patterns on various mollusc shells. The default is 1;0;12;48;0;011;003;000 Lorien1. One needs to set steps to 0 and REDRAW for successive screens as the diffusion rules takes several steps to initialize and the scrolling 1-D simulation refreshes only on the last row.

1;2;05;10;0;300;002;000	2;0;06;35;0;050;002;100 KM fig11	3;0;05;12;0;220;004;190 KM fig10
3;8;02;11;0;300;001;000 KM fig9	2;0;10;48;0;000;002;000 KM fig4	4;9;02;18;0;200;002;060 KM fig18iii
4;9;05;38;0;000;002;060 Lorien2	2;4;08;48;0;030;002;055 LorienFin	3;8;02;11;0;300;002;060 Christine

These identify parameters r;R;w1;w2;m0;m1;p;d in the model of:
Kusch I, Markus M 1996 Mollusc Shell Pigmentation: Cellular automation simulations and evidence for undecidability J Theor Biol 178 333-340.

Finally you can add new rules freely by including further cases in the source code of sillyballview.m and controller.m. Default(Sum) is already set up for you to do this simply by opening the source project in XCode resident in every Mac or downloadable from Apple and altering the entry in sillyballview.m wavefn under default. You can add new selections by adding an extra case in the same section and assigning a top size for cell states under the wavefn procedure. You need also to add an extra Cell Rule in the Cell Rule popup button using Interface Builder and add an extra selection entry with the same text name in controller.m.

Mirek's Cellebration gallery has a very complete collection of all these CA types, along with an excellent open source CA simulator for Windows.

See: http://www.dhushara.com/CA/ for full manual, downloads and further research.

Shrike behaves differently depending on the initial conditions. It can end up forming fractals dominated by either a
chequerboard of 1s and 2s or an ocean of 3s or it can develop a complex trellis of interacting and collapsing diamonds.
Click on image to enlarge.

The various CAs can be developed using one another's states as initial conditions.
Here Persian is used followed by Diffuse. Then Fires burns out the interior and grows new dendrites
with its green 'flames' and finally Border attempts to retrace the boundaries. Click on image to enlarge.