Introduction to cellular automata

Introduction

First off, let’s define a cellular automaton (plural: automata) as a series of cells evolving according to a predefined set of rules, creating a new generation of cells. This principle is used in several fields such as digital imaging, physics, chemistry, and any application requiring automation, such as industrial engineering.

Concrete example

The rule governing every individual cell’s evolution is predicated on its neighbours’.

So, if the rule for evolution is the following:​​

• 0 with 0 to the right becomes 1.
• 0 with 1 to the right stays 0.
• 1 with 0 to the right stays 1.
• 1 with 1 to the right becomes 0.

Starting with the following arbitrary state of 0010, generation 0 will evolve as follows:

The result is the following:

• 0010 (generation 0).
• 1011 (generation 1).
• 1000 (generation 2).
• 1110 (generation 3).

Let’s take it one step further

This principle is easily extendable. For example, by using both right-hand and left-hand neighbouring cells, we can compare 3 cells with two potential states rather than two cells in two states.

So that gives us 2^3 = 8 rules to define (i.e. determine whether they yield a 0 or a 1).

Each of these rules provides 2 possible results (0 or 1), which gives us 2^8=256 possibilities. These rules, known as the Wolfram Rules, yield patterns that are sometimes predictable, sometimes chaotic, but never random, since everything is predictable and reproducible as long as you know the rule applied and the configuration of generation zero.

Here are a few examples of these rules and their results (as above, each line is a new generation). (Source : http://wolframalpha.com.)

Rule 30

Rule 43

Rule 90

Now, let’s go 2D or more!

With one line of 2-state cells, you quickly reach a limit if you only consider the contiguous cells.

To put it in binary terms, imagine taking a phrase (for example, a password) and converting its binary value into an 8 cells wide matrix.

Then, you pick rules for the four neighbouring cells (above, below, left and right). Including the value of the center cell, that makes 2^5 = 32 rules to determine, each cell producing two potential output values (0 or 1). So, using the same calculation we used for the Wolfram rules, there are 2^32 potential rules, or over 4 billion.

The Game of Life

By taking one cell and its 8 immediate neighbours, John Conway created a set of 4 rules that he then animated, to produce “Game of Life”. Check out his rules and how they interact:

1. A live cell dies if it has fewer than two live neighbours.
2. A live cell survives if it has two or three live neighbours.
3. A cell dies if it has more than three live neighbours.
4. A dead cell with exactly three live neighbours becomes a live cell.

Here are some examples of the results:

To summarize:

Given S number of possible states for a given cell, and N number of verified cells to establish the next generation, we get S^(S^N) possible rule combinations.

For example:

• For 2 states and 3 verified cells (as in rule no. 30), we get 2^(2^3) possibilities.
• For 2 states and 9 verified cells (for example a pixel and all its neighbours), we get 2^(2^9) possibilities.
• For 2 states and 27 verified cells (for example by comparing a matrix of 3D-cubes, like in Minecraft), we get 2^(2^27) possibilities.

Applications

Digital imaging

Take a 2D model with over two states, for example color pixels. Now you can play with them to create effects such as fuzziness or contrast, refine the grain, or clean artifacts left over from compression.

Random generation

Wolfram rule 90 allows you to generate a pattern that looks random. Just choose an initial binary population based on a known value (date and time, IP address of the user, etc.) to generate a new binary, random-like sequence after a set number of generations (given that absolute randomness does not exist in computing). You can then use this “random” value as an encryption key, as a value for salting, etc.

Randomized generation for creating terrain maps (for example in video game types such as Dungeon Crawlers and Rogue-like games) use cellular automaton algorithms to clean up the result of parasitic elements.

In the example below, taken from roguebasin.com, a wall (#) stays a wall as long as it is surrounded by 4 walls. If it isn’t already a wall, it becomes one if it is surrounded by 5 walls or more. Otherwise, it becomes empty space. Cellular automata are used to clean up the pattern.

Security

I’ve been talking about binary transformation since the beginning of this article, so there is no need to justify its usefulness for encrypting data. As you can guess, encryption is usually unilateral, depending on the type of rule. Though there are plenty of potential combinations, as demonstrated above, not all of them are usable. For example, in unilateral encryption, there is absolutely no need for all data to always go to zero. Ultimately, from a less extreme viewpoint, there is always a risk of collision between rules (see Rainbow Table). However, it is an efficient method if your goal is to keep anyone from reverse-engineering a password from its encrypted version.

On the other hand, you can change rules at each generation, vary the number of times generation zero evolves according to known criteria, etc.

What about more than two states?

Until now, we’ve only talked about binary cells, with just two possible states. What if we were to increase the number of states? Obviously, it would increase the number of possibilities.

Take Minecraft, and imagine we’re using a cellular automaton algorithm to create the world, a “Big Bang” algorithm. Based on a completely random zero generation made up of lava, water, air and earth, you could evolve a puddle into air, for example, if it is surrounded by 4 squares of lava, or into earth if only surrounded by two lava squares. Just set the rules, then let the world unfold naturally.

The Langon Loop is an 8-state automaton algorithm able to reproduce itself, and shrink when necessary.

So what?

As John Conway stated in an interview, his Game of Life is not in itself a mathematical breakthrough. His “game” is simply a demonstration of what can be accomplished with a set of very basic rules. Furthermore, it would be inconceivable to create a set of valid rules producing symmetrical encryption, and performance becomes a problem when evolving too many cells with too many rules.

That said, cellular automata are used in many fields. In digital imaging, they allow pixel-by-pixel manipulation to create effects like those mentioned earlier. In physics, they provide prediction and estimation models, for example, for lattice gas automaton. In industrial applications, Von Neumann’s universal constructor demonstrated that a machine can reproduce itself; by extension, a system should be able to evolve on its own. In fact, bright minds are working on integrating cellular automata and artificial intelligence.

Documentation is still thin on the ground and the field is still young; if your interest in this topic is piqued, I encourage you to read up on it!