Generative Art
Computational Art
Cellular Automata

Elementary Cellular Automata : complexity rooted in simple rules

Dorit Geifman

5 min readJun 17, 2024

Even from very simple programs behavior of great complexity could emerge

Stephen Wolfram

Imagine a vector of numbers, zeros or ones (white or black), and a rule that transforms every number to a new number depending on the value of the cell and its two neighbors. Now imagine that, at discrete time steps, you apply this rule recursively to form a grid of vectors that extend over time from top to bottom.

In the 1980’s Stephen Wolfram, a physicist by training, started to explore this family of models, a.k.a. Elementary Cellular Automata, and was fascinated by the highly complex forms that emerge from simple rules. He believed that complexity in nature could similarly arise from simple underlying rules. Wolfram embarked on a twenty-years research project that gave the topic a firm mathematical basis. He summarized his findings in book called A New Kind of Science.

Wolfram’s research contributed significant to fields such as computational theory, complex systems and cryptography. They also opened new research directions in areas such as computational physics and biology.

In this project I explore the visual outcome of some variants of Elementary Cellular Automata.

… but let’s start with Wolfram

Elementary Cellular Automata can be regarded as one-dimentional Cellular Automata (see my previous post). It is a vector of cells, each assigned with a state that is represented by a number (or a color). At discrete time steps, an evolution rule defines the new state of each cell based solely on its current state and the states of its two neighbors.

Wolfram analyzed all 256 possible rules of a 2-state Elementary Cellular Automata and identified four classes of behavior.

Why 256 rules?

A rule is defined by the state of 3 cells, the current cell and its 2 neighbors. This means that each rule is defined by 8 (2³) combinations that result in a new state, therefore 256 = 8² distinct rules.

Elementary Cellular Automata classes:

Class 1: Patterns that evolve into a homogeneous state, never changing again. These are equivalent to trivial computer programs that halt after a few execution steps.
Class 2: Patterns that evolve into a set of periodic oscillating structures. These resemble to programs that execute in an inifine loop.
Class 3: Patterns that evolve in a seemingly random or chaotic manner. These are similar to programs that are pseudo-random number generators.
Class 4: Patterns that form complex patterns with localized structure that move vertically and horizontally and eventually become homogenous (class 1) or periodic (class 2). This is the most interesting class. It is difficult todescribe; It is not regular, periodic or random, with some of these automata being capabel of universal computation (i.e. being a Turing machine)

Lets take a look at two examples:

Get Dorit Geifman’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

(a) Rule 30 exhibits a class 3 behavior

250 iteration of the rule, starting with one “black” cell at the center of the array, produces the following pattern:

Each row in this pattern, when regarded as a binary number, reflects a chaotic, seemingly random pattern that does not repeat itself. This rule has been used to generate pseudo-random numbers

(b) Rule 110 exhibits a class 4 behavior

250 iteration of the rule, starting with one “black” cell at the center of the vector, produces the following pattern:

This rule has significant importance in computational theory as it was proved to be Turing Complete, meaning that in principle, any calculation or computer program can be simulated using this automaton. It demonstrated that even simple systems could exhibit computational universality.

… and to the interesting part

The Wolframs’ Elementary CA rules may create mathematically interesting patterns, but to be honest, they are quite boring visually. To generate more compelling artwork we can increase the number of states (colors), change the rules, or add randomness

Lets say that we want to add one color to the process described above. Each lookup table now consists of 27 (3³) combinations resulting in a range of 10¹² (3²⁷) rules. The task of identifying visually pleasing rules becomes quite tedious. And just think of the number of combinations when working with more colors.

One workaround to this problem is to use the sum of states of the 3 cells as an index to the lookup table of new states. The number of unique sums of 3 numbers (k) is 3k-2. For three states (colors) we have 7 unique sums that result in 2187 (3⁷) rules that produce three new states (colors), a rather manageable number. By starting with a vector of randomly distributed colors we get quite interesting results

Another way to go is to map the multi-state cell value to a binary value and calculate a new vector by using one of the 256 original Wolfram rules. Each cell in the new vector is now mapped back to a new multi-state value that is randomly selected from the multi-state value of the previous cell and its neighbors. And here again we can start with a random inital vector.