Cellular Automata

A short essay about how cellular automata work.

Imagem de capa

Cellular Automata

Ever imagined a two-dimensional board that can represent life?

All living beings interact with, and are affected by those around them. Given the complexity, the rules of the world dictate the survival of every cellular organism. We try to simulate this using a cellular automata. For every generation, each cell is affected by its current state, and that of those around it. Every possible combination has a rule associated with it, which can be changed, in turn changing the results of the simulation.

A cellular automaton is a model of a system of “cell” objects with the following characteristics.

The cells live on a grid. (We’ll see examples in both one and two dimensions, though a cellular automaton can exist in any finite number of dimensions.)

Each cell has a state. The number of state possibilities is typically finite. The simplest example has the two possibilities of 1 and 0 (otherwise referred to as “on” and “off” or “alive” and “dead”).

Each cell has a neighborhood. This can be defined in any number of ways, but it is typically a list of adjacent cell.

The development of cellular automata systems is typically attributed to Stanisław Ulam and John von Neumann, who were both researchers at the Los Alamos National Laboratory in New Mexico in the 1940s. After that Stephen Wolfram wrote a 1000 page long tome on the topic and named it: A New Kind of Science appropriately. The book is available on his website in its entirety for those interested.

Coming back to the automaton, I present here a basic implementation of these evolving structures. But instead of creating a static cellular automata, I have created a dynamic one to explain the whole concept interactively. Hopefully after playing with this implementation, you will have a better understanding of how these structures work.

This simulation consists of just one dimension. The grid here is just a one-dimensional array and we use the other dimension (y-axis) as the dimension for time. The consequent generations are shown below their parents, resulting in the creation of a pattern. We assume that each cell is influenced only by itself, and its immediate neighbors. In other words, the neighborhood for each cell contains 3 cells. Now if each rule contains 3 cells, each of which can have 0 or 1, how many possible rules are there?

ch07_07.png

You’re right! There are 8 possible rules for this particular automaton. To make it interactive, I have added clickable properties to all the rule buttons in the implementation. You can change all the 8 rules by clicking on the respective button and see the resulting pattern. Go ahead and see all the 256 (28) possible patterns created using this automata and revel in the elegance of cellular automata.

Hail the Cellular Automata

For the curious reader, yes I am developing more interactive versions of cellular automata, with more dimensions and functionality. I will be uploading some cooler automata soon!

Some fun patterns to try out:

1st Rule 2nd Rule 3rd Rule 4th Rule 5th Rule 6th Rule 7th Rule 8th Rule
1 1 0 1 1 0 1 0
0 0 0 1 0 1 1 0
0 0 0 1 1 1 1 0
0 0 1 0 1 1 0 1
0 1 0 0 1 0 0 1
0 1 1 0 1 1 0 1
0 1 1 0 1 1 0 1
1 0 1 0 0 1 1 1
1 1 1 1 1 0 1 0
1 1 1 1 1 0 1 0
0 1 1 1 0 0 0 1
0 0 1 0 1 1 0 1
0 0 1 1 0 1 1 0
0 1 1 0 1 1 1 0
1 0 1 0 0 1 0 1