Think Complexity, 2nd Edition

Chapter 5. Cellular Automatons

A cellular automaton (CA) is a model of a world with very simple physics. “Cellular” means that the world is divided into discrete chunks, called cells. An “automaton” is a machine that performs computations—it could be a real machine, but more often the “machine” is a mathematical abstraction or a computer simulation.

This chapter presents experiments Stephen Wolfram performed in the 1980s, showing that some cellular automatons display surprisingly complicated behavior, including the ability to perform arbitrary computations.

I discuss implications of these results, and at the end of the chapter I suggest methods for implementing CAs efficiently in Python.

A Simple CA

Cellular automatons¹ are governed by rules that determine how the state of the cells changes over time.

As a trivial example, consider a cellular automaton (CA) with a single cell. The state of the cell during time step i is an integer, x_i. As an initial condition, suppose x0=0.

Now all we need is a rule. Arbitrarily, I’ll pick xi+1=xi+1, which says that during each time step, the state of the CA gets incremented by 1. So this CA performs a simple calculation: it counts.

But this CA is atypical; normally the number of possible states is finite. As an example, suppose a cell can only have one of two states, 0 or 1. For a 2-state CA, we could write a rule like xi+1=(xi+1)%2, where % is the remainder (or modulus) operator.

The behavior of this CA is simple: it blinks. That is, the state of ...