Cellular Automata

Tackling such a problem is hard, so scientists decided to simplify the problem.
How to find the logical mechanisms for self-reproduction? Finding an algorithm to achieve transcription and translation would be a great start, it would also be easier to formalize these concepts in a discrete world.
That's when the idea of cellular automata was born.
A cellular automaton is a mathematical abstraction of the real world, a modeling framework in which everything is discrete. There are many examples of cellular automata, in this blog we will be looking at two that use a square lattice (a grid).
Although the square lattice is the most common, it is possible to use a hexagonal lattice, a triangular lattice, or even a three-dimensional lattice (a cube).
It is also possible to make a simpler automaton, for example, a one-dimensional automaton. Take a look at Wolfram's Automata.

Implementing the rule is pretty simple for the inner cells, but what about the cells on the edge?
How do we handle the cells that don't have four neighbors?
There are many ways to handle such cells (this is called boundary conditions) here are a few examples:

• Fixed, an imaginary cell would exist with a permanent state
• Adiabatic, the same cell would be considered a neighbor
• Periodic, the cells on the edge are regarded as neighbors of the cells on the other side of the grid

When applying the periodic boundary condition, the neighboring cells for the top left cell would be:

1. The next on the right
2. The next on the bottom
3. The bottom left cell (this is the north neighbor)
4. The top right cell (this is the west neighbor)

In this blog, we will be using the periodic boundary condition.

It is relatively easy to create a cellular automaton in p5.js. You can take a look at the complete code here.
We have a grid of cells that saves the state of each cell, when one is clicked its state is flipped, and when the start button is clicked the simulation starts.
The most important part is how to implement a certain rule for the automaton (in this case the parity rule), and how to enforce the boundary conditions (in this case the periodic boundary condition).

To implement the parity rule, we need to sum up the states of the four neighbors, and then check if the sum is even or odd.
At each iteration, every cell needs to be updated, so we need to save the new state of each cell in a temporary grid. Then we can sum up the four neighbors of each cell and check the parity.
There are many ways to sum up the four neighbors, the best and the most efficient one is to use the modulo operator. By doing so, not only we can sum up the neighbors, but we can also enforce the periodic boundary.

    
      for (let i = 0; i < gridVSize; i++) {
        for (let j = 0; j < gridHSize; j++) {
          iM = (i - 1) % gridVSize;
          iP = (i + 1) % gridVSize;
          jM = (j - 1) % gridHSize;
          jP = (j + 1) % gridHSize;
          grid[i][j].alive =
            (gridCopy.at(iM).at(j).alive +
              gridCopy.at(iP).at(j).alive +
              gridCopy.at(i).at(jM).alive +
              gridCopy.at(i).at(jP).alive) %
            2;
        }
      }
    
  

Here gridVSize and girdHSize are the vertical and horizontal sizes of the grid respectively.
The modulo operator ensures that when the index equals the size of the grid, it will be set to 0, so back at the start of the grid.
On the other hand, the Javascript at function is used to access the element at a certain index, if the index is -1, it will be set to the last element.
This is how the periodic boundary condition is enforced.

Let's take a look at the parity automaton in action. We will begin with a single cell alive approximately in the middle of a 64x64 grid.

The gif below shows the first 7 iterations of the parity rule

Despite the simplicity of the, rule we can already see complex shapes forming, a shape that "copies" itself

Let's see an example of a more complex initial state, take a look at this video, the initial shape is somewhat triangular.

We can see that the automaton generates the same shape multiple times in different positions.
Pause at iteration 4, the triangular shape is reproduced, there are now 4 shapes instead of one.
At iteration 12, the triangular shape is reproduced again, now there are 16 shapes instead of 4.

At different iterations we can see intricate patterns forming, this is the beauty of cellular automata, we began with a simple rule and a simple initial state, and we ended up with complex patterns.

If you watched the video till the end, you would have noticed that at iteration 32, the grid is empty, and all cells are white. This is not an error, this is the expected behavior of the parity rule given the grid size.

We can mathematically prove that a cellular automaton of size \( 2^k \) with periodic boundary conditions will reach a whole zero state at iteration \( 2 ^ {k - 1} \).

You can find proof in this book Cellular Automata Modeling of Physical Systems I won't get into the details here.

In our case, the grid size is \( 64 = 2^6 \), so the automaton will reach a whole zero state at iteration \( 2^{6 - 1} = 32 \).

This is an example of the fact that cellular automata is indeed a mathematical object, we can study it mathematically. Here is a randomly generated grid, watch the video till the end, you will see that the automaton reaches a whole zero state at iteration 32.

The most famous example of a cellular automaton is Conway's Game of Life. Unlike the parity automaton, the game of life has a more complex rule.
The affected cells when determining the state of a cell are the eight neighbors, not just the four we saw earlier, here is an image.

The rule is as follows:
If a cell is alive and has 2 or 3 alive neighbors, it stays alive, otherwise, it dies.
If a cell is dead and has exactly 3 alive neighbors, it becomes alive, otherwise, it stays dead.

The game of life has been studied and analyzed extensively, there is an online community of enthusiasts that study the game of life, and they have found many interesting patterns and shapes.
Take a look at LifeWiki

The examples we saw above are theoretical, but cellular automata can be used to model real-world systems.
From simulating diffusion to modeling the spread of diseases, the spread of forest fires, growth models in physics, fluid mechanics, and many more, cellular automata is a powerful scientific tool.

Scientists have contemplated the implications of cellular automata, how could something so simple be able to simulate real-world phenomena?
What does that say about the nature of reality? How could a discrete world be able to simulate a continuous world?

Lots of questions are raised by cellular automata, and it is a fascinating field of study.
I will be writing more about cellular automata in the future, so stay tuned!