Cellular automata. A brief introduction. For readers not familiar with the concept of cellular automata a brief introduction into the subject is given. Readers who are familiar with the concept though, can easily skip this chapter. Although cellular automata nowadays cover a vast area, they all have some features in common. First of all a cellular automaton is a discrete dynamic model that has a spatial and a temporal part. The spatial part is formed by the cells of the automata. It is dynamic in the sense that the spatial appearance of the automaton changes in discrete time steps. This is the temporal part. Cells in the automaton are dependent entities. I.e. they are connected together and therefore each cell has surrounding cells called the neighborhood of the cell. If the cellular automaton would be a two dimensional square lattice, like in a notebook with squared paper, each cell would have 8 neighboring cells. Such a neighborhood is commonly known in cellular automata theory as a Moore neighborhood. Another commonly known neighborhood is the von Neumann neighborhood that comprises the four cells orthogonally surrounding the cells. Both neighborhoods are drawn in the picture below. It is possible to construct other configurations with the number of direct neighborhood cells ranging from 0 to infinity. A cell with zero direct neighbors would be a singularity. A cell with one direct neighbor would comprise a cellular automaton consisting out of 2 cells. These concepts will be used in the development of the cellular automata in this book. Another important aspect in the dynamics of cellular automata is that every cell can be assigned a value. Most commonly used are the values 1 and 0. However other values are possible. The value of a particular cell is determined by a set of rules and is generally based on the actual value of the cell itself and the values of its neighboring cells. Usually the direct neighbors of the cell are used to determine this value. However it is possible to take into account the second next neighbors of the cell and so on. This will of course complicate the calculations necessary in determining the value of the cell in the next time step. As an example, consider the simple cellular automaton consisting of 3 cells that can each take the values 0 and 1. If the cell has the value 1 it will be colored gray. If it has the value 0 it will be colored white. This automaton then has 23 = 8 states as depicted below. The next step would be to define a rule set that defines the value in the next time step of the central cell based on the values of the 2 neighboring cells and its own value. A convenient way to implement this would be in the form of a transition table like below: Left Cell Value Central Cell Value Right Cell Value Value of Central Cell in next time step 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 So looking at the first row, if the values of the neighboring cells would be 1 and the value of the central cell is 1 then in the next time step it will maintain its value of 1. The other 7 rules work in a similar way. It should be noted that for this particular kind of automaton 256 (= 28) transition rules can be constructed since there are eight possible configuration states for 3 cells and each of these can result in two possible outcomes (0 or 1) for the central cell. I.e. it is possible to order the zero’s and one’s in the column titled “Value of Central Cell in next time step” in 28 ways ranging from 00000000 to 11111111 and every possible order in between without changing the values in the other columns. These 256 transition rules result in 256 different cellular automata. These are commonly known as elementary cellular automata. (Actually, the rule given in the table above is commonly known as rule 150 because 10010110 in base 2 is the number 150 in decimal notation). Imagine a row of cells extending to infinity at both sides like in the picture below: Now a arbitrary cell will get the value 1 at time step zero (t0). Using the table above and putting the results from top to bottom the following pattern emerges for t0 till t6. Extending this even further the pattern eventually becomes self repeating as can be seen in the next picture. This emergent behavior makes cellular automata very interesting. It shows that quite simple rules on a local level lead to rather complex behavior on a global scale. Although rather brief, this short introduction will give a firm enough base to understand the other chapters in this book.