# Elementary cellular automata

tags
Cellular automata
resources
Wolfram Mathworld, Wikipedia

ECA are one of the simplest form of 1D cellular automata possible. The grid is a 1-dimensional array of cells in state 0 or 1 (dead or alive). The size of the neighborhood being used for the update is 3 (one cell to the left, the main cell and one cell to the right).

Each of those $$2^3$$ neighborhoods of size 3 can be mapped to either state 1 or 0. There are $$2^{2^3} = 2^8 = 256$$ possible mappings and therefore 256 possible ECA rules.

From this very simple definition, rules with various unexpected behavior emerge. Wolfram constructed a classification of those behavior, known as Wolfram’s classification (Wolfram 2002).

## Simple implementation

In Python, taking advantage of Numpy’s array manipulation. This implementation is much faster than loping through elements of the grid to update them, but uses more memory. The algorithm is simply based on the standard ECA update.

import numpy as np
import matplotlib
import matplotlib.pyplot as plt
fig, ax = plt.subplots(figsize=(3,2))

N = 100
T = 50
rule = 54 # Rule code
rule_list = bin(rule)[2:]
# Zero padding of the rule
rule_list = [0] * (8 - len(rule_list)) + [int(i) for i in rule_list]
# Convert to array and reverse the list
rule_array = np.array(rule_list[::-1])

init = np.random.randint(2, size=N)
grid = np.zeros((T, N), dtype=np.int)
grid[0, :] = init
for i in range(1, T):
next_step = rule_array[np.roll(grid[i-1, :], -1) +
2 * grid[i-1, :] +
4 * np.roll(grid[i-1, :], 1)]
grid[i, :] = next_step

ax.matshow(grid, cmap='Greys')
fig.tight_layout()
fig.savefig('img/plots/ca_rule54.png')


Results:

## Bibliography

Wolfram, Stephen. 2002. A New Kind of Science. Champaign, IL: Wolfram Media.

← Back to Notes