This page contains algorithms for five cellular automata. What is common to all five is as follows:

Cellular Automata Algorithms

Thus from an initial state or configuration of the grid we obtain a series of states or configurations, and thus the cellular automaton may be thought of as evolving over time (or as traversing a path through the "state space").

- A rectangular grid whose elements (positions) are specified by row number and column number.
- Each position in the grid is associated with a certain state, which is specified by a number. Each position is said to be occupied by a cell in a certain state, or alternatively a position with associated state zero may be said to be "empty", the other positions being occupied by cells in some (non-zero) state.
- A set of rules which determines how the state of a cell (or of a position in the grid) changes from one "step" or "generation" to the next, usually as a function of the state of the cells (if any) around it and its own state.
- Periodic boundary conditions.

The presentation of the algorithms on this page is © 2006 Hermetic Systems. They may be reproduced only with attribution and acknowledgement of source in the form of a link to, or the URL of, this page.

## q-state Life

The rules for q-state Life are as follows:

(i) Select four integers k1, k2, k3 and k4 in the range 0 through 900.

(ii) In the transition from one step to the next the state of each cell is changed once according to rules (iii) - (v).

(iii) For each cell letSdenote the sum of the states of its eight neighbors (Sdoes not include the state of the cell itself).

(iv) Letsdenote the state of the cell. If s > q/2 then if k1 <= S <= k2 then add 1 (if s < q) to the state of the cell, otherwise subtract 1 (if s > 1).

(v) Otherwise (i.e. if s <= q/2) if k3 <= S <= k4 then add 1 (if s < q) to the state of the cell, otherwise subtract 1 (if s > 1).Taking q = 2, k1 = 10 and k2, k3, k4 each equal to 11 we obtain rules which are equivalent to the rules for Conway's Life (taking 'dead' = state 1 and 'alive' = state 2).

## The Belousov-Zhabotinsky Reaction

The rules, as given by Professor A. K. Dewdney, to be applied to a cell, in order to determine its state in the next generation, are as follows:

(i) If the cell is healthy (i.e., in state 0) then its new state is [a/k1] + [b/k2], where ais the number of infected cells among its eight neighbors,bis the number of ill cells among its neighbors, andk1andk2are constants. Here "[]" means the integer part of the number enclosed, so that, for example, [7/3] = [2+1/3] = 2.

(ii) If the cell is ill (i.e., in staten) then it miraculously becomes healthy (i.e., its state becomes 0).

(iii) If the cell is infected (i.e., in a state other than 0 andn) then its new state is [s/(a+b+1)] + g, whereaandbare as above,sis the sum of the states of the cell and of its neighbors andgis a constant.Rule (iii) can be seen as stating that the new state of a cell is the average of its state and its neighbors states plus a constant which may be thought of as the tendency of the infection to spread.

A slightly modified version of these rules is as follows:

(i) Select an integer qin the range 2 through 255. Cells may be in any of the states 1 throughq.

(ii) Select two integersk1andk2in the range 1 through 8 and an integergin the range 0 through 100.

(iii) In the transition from one "step" to the next the state of each cell is changed once according to rules (iv) - (vii) below:

(iv) A cell in stateqchanges to state 1.

(v) A cell in state 1 changes to state a/k1 + b/k2 + 1 whereais the number of neighbors of the cell which are in states 2 through q-1 andbis the number of neighbors in stateq.

(vi) A cell in any of states 2 through q-1 changes to S/(9 - c) + g, whereSis the sum of the states of the cell and its neighbors andcis the number of neighbors in state 1.

(vii) If the application of rule (v) or rule (vi) would result in a cell having a state >qthen the state of that cell becomesq.## Togetherness

The rules for this automaton are as follows:

(i) Select an integer qin the range 1 through 7. Cells may be in any of the states 1 throughq(represented byqdistinct colors) and do not change their state as the system evolves.

(ii) Select a grid sizesand an integernsuch that 1 <= n <= s (this is the "selection range").

(iii) Select a real-valued "concentration"c(range 0 through 1), which is the probability that a location on the grid is occupied by a cell, then set up the initial state of the system by placing c.s^{2}cells at random locations on the grid and in random states subject to the condition that there are approximately equal numbers of cells in each of theqstates.

(iv) Select an integermin the range 1 through 9999 (the "lossy move chance").

(v) The system evolves as a succession of "steps", each of which consists of a succession ofs"substeps".^{2}

(vi) A "substep" consists of the following process:

(a) Select at random a cell which is not surrounded by 8 neighbors all in the same state.

(b) Among those locations on the grid that are withinnunits of distance from the cell select one at random (which is not the location of the cell itself). (Distance is measured as the length of a minimal path, in horizontal and vertical steps, along the grid.)

(c) If there is a cell at that location and either it has the same state as the first or it is surrounded by 8 neighbors all in the same state as that (second) cell then continue with the next substep.

(d) If there is no cell at that location then calculate the "gain"g, that is, the increase or decrease in the number of neighbors of the cell in the same state as that cell, which would result from moving the cell to that location. If g >= 0 then move the cell to the new location. If g = -1 then make the move with a probability of 1 inm.

(e) If there is a cell at that location then calculate the combined "gain"g, that is, the net increase or decrease in the number of neighbors of the two cells in the same state as those cells which would result from swapping them. If g >= 0 then swap the cells. If g = -1 or g = -2 then perform the swap with a probability of 1 inm.

(f) This completes a substep.The rule allowing a move or a swap which results in a loss, although seldom occurring, makes this algorithm a simple relative of the Metropolis and Glauber dynamics algorithms used in computational physics.

## Viral Replication

The rules for this automaton are as follows:

(i) Select an integer qin the range 2 through 254. Cells may be in any of the states 1 throughq. A cell in stateqis said to be "healthy", a cell in state 1 is "fully infected" and a cell in any other state is "infected".

(ii) Select a grid sizes.

(iii) Select integersk1(range 0 through 100),k2(range 0 through 9999) andk3(range 0 through 100), interpreted respectively as specifying the active infection rate, the base rate and the chance of cell division as described above.

(iv) Set up the initial state of the system by placing healthy cells at random locations on the grid so that approximately half of the locations are occupied by cells.

(v) The system evolves as a succession of "steps", each of which consists of a succession ofs"substeps".^{2}

(vi) A "substep" consists of the following process:

(a) Select a random location. If it is not occupied by a cell then this substep is completed.

(b) Otherwise if the cell at this location is healthy then its state changes to q-1 (so it becomes infected) with probability k2/100,000.

(c) If the cell does not become infected, and at least one of the eight neighboring locations is empty, the cell divides with probability k3/100, with one daughter cell remaining at this location and the other occupying one of the empty neighboring locations (chosen at random).

(d) If the cell at this location is infected but not fully infected then its state decreases by 1.

(e) If the cell at this location is fully infected then it disappears, and the state of each neighboring cell which is not fully infected decreases by 1 with probability k1/100.

(f) This completes a substep.## Diffusion-Limited Aggregation

The rules for this automaton are as follows:

(i) Select an integer qwhich is one of 2, 4, 8 or 64. Cells may be in any of the states 1 throughq. Cells are either "fixed" or "mobile".

(ii) Select a grid sizes.

(iii) Select integersk1(range 5 through 100) andk2(range 1 through minimum ofsand 250), interpreted respectively as specifying the initial percentage concentration of cells on the grid and the number of seed cells.

(iv) Set up the initial state of the system by placing (a)k2"seed" cells either at random locations on the grid or at certain predetermined positions and (b) the remaining cells (whose number is determined byk1and the grid size) at random empty locations. The seed cells are all fixed and the other cells are all mobile. The seed cells are all in stateq(and are usually colored white) and the other cells are all in state 1 (and are invisible).

(v) The system evolves as a succession of "steps", each of which consists of a succession ofs"substeps".^{2}

(vi) A "substep" consists of the following process:

(a) Select a random location. If there is no mobile cell at this location then this substep is completed.

(b) If one of the neighboring locations has a fixed cell then this mobile cell changes to a fixed cell, and is assigned a state in the range 2 throughqand an appropriate color (this completes this substep).

(c) If no neighboring location has a fixed cell then this mobile cell moves at random to one of the empty neighboring locations (if any).

(d) If the new location of the cell is beyond the circular region centered on the central location with radius s/2 then the cell ceases to exist.

(f) This completes a substep.

Computational Science Hermetic Systems Home Page