A cellular automaton is a formal device consisting of
This page contains algorithms for five cellular automata. What is common to all five is as follows:
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").
These cellular automata have been implemented by the author in his program Five Cellular Automata. The images at right show snapshots of the dynamic output of this program.
The user interface for this program is written in Visual Basic 6. To run the cellular automata this program calls functions in a DLL written in C. The source code for these functions is given here:
(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 let S denote the sum of the states of its eight neighbors (S does not include the state of the cell itself). (iv) Let s denote 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).
(i) If the cell is healthy (i.e., in state 0) then its new
state is [a/k1] + [b/k2], where a is the number of infected
cells among its eight neighbors, b is the number of ill cells
among its neighbors, and k1 and k2 are 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 state n) 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 and n) then its new state is [s/(a+b+1)] + g, where a and b are as above, s is the sum of the states of the cell and of its neighbors and g is 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 q in the range 2 through 255. Cells may be in any of the states 1 through q. (ii) Select two integers k1 and k2 in the range 1 through 8 and an integer g in 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 state q changes to state 1. (v) A cell in state 1 changes to state a/k1 + b/k2 + 1 where a is the number of neighbors of the cell which are in states 2 through q-1 and b is the number of neighbors in state q. (vi) A cell in any of states 2 through q-1 changes to S/(9 - c) + g, where S is the sum of the states of the cell and its neighbors and c is 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 > q then the state of that cell becomes q. |
(i) Select an integer q in the range 1 through 7. Cells may be in any of the states 1 through q (represented by q distinct colors) and do not change their state as the system evolves. (ii) Select a grid size s and an integer n such 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 the q states. (iv) Select an integer m in 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 of s^{2} "substeps". (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. |
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.
(i) Select an integer q in the range 2 through 254. Cells may be in any of the states 1 through q. A cell in state q is 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 size s. (iii) Select integers k1 (range 0 through 100), k2 (range 0 through 9999) and k3 (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 of s^{2} "substeps". (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. |
(i) Select an integer q which is one of 2, 4, 8 or 64. Cells may be in any of the states 1 through q. Cells are either "fixed" or "mobile". (ii) Select a grid size s. (iii) Select integers k1 (range 5 through 100) and k2 (range 1 through minimum of s and 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 by k1 and 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 state q (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 of s^{2} "substeps". (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. |
Home Page of this Hermetic Systems Website |
Home Page of the other Hermetic Systems Website |