In A New Kind of Science, Stephen Wolfram describes a set of simple one-dimensional cellular automata in which each cell can take one of two values: 'on' or 'off'. A row of cells is initialised in some state (for example, with a single 'on' cell somewhere in the row) and it evolves into a new state according to a rule which determines the subsequent state of a cell ('on' or 'off') from its value and that of its two nearest neighbours. There are $2^3 = 8$ different states for these three 'parent' cells taken together and so $2^8=256$ different automata rules: that is, the state of cell $i$ in the next generation is determined by the states of cells $i-1$, $i$ and $i+1$ in the present generation.
These rules are numbered 0 – 255 according to the binary number indicated by the eight different outcomes each one specifies for the eight possible parent states.
For example, rule 30 produces the outcome (off, off, off, on, on, on, on, off) (or 00011110) from the parent states given in the order shown in the figure below. The evolution of the cells can be illustrated by printing the row corresponding to each generation under its parent as shown in the figure.
Write a program to display the first few rows generated by rule 30 on the command line, starting from a single 'on' cell in the centre of a row 80 cells wide. Use an asterisk to indicate an 'on' cell and a space to represent an 'off' cell.
Solution P4.3.3
The program below generates the first 32 generations of the cellular automaton governed by rule 30. The rule number is turned into its binary representation in the list rule (in this case, [0,1,1,1,1,0,0,0] - note that the least significant bit is stored first). This list can then be indexed for each cell by turning the states of the three parent cells into a number 0–7.
# The rule number and its binary representation as a list of 1s and 0s
# (least-significant bit first)
n = 30
rule = [n // 2**i % 2 for i in range(8)]
width = 80
ngens = 32
# The previous row: initialise with a single 1 in the centre
lrow = [0] * width
lrow[39] = 1
# An array representing the next generation
row = [0] * width
def line(row):
""" Outputs a string representation of the row of on/off cells. """
return ''.join(['*' if cell else ' ' for cell in row])
# Print the initial row
print(line(lrow))
# Evolve for ngens generations
for n in range(ngens):
for i in range(1,width-1):
# Apply the rule to cell i by turning the state of the three parent
# cells into an index to the rule list
row[i] = rule[4*lrow[i-1] + 2*lrow[i] + lrow[i+1]]
print(line(row))
# The present generation becomes the previous one before the next iteration
lrow = row[:]
The intriguing output is:
*
***
** *
** ****
** * *
** **** ***
** * * *
** **** ******
** * *** *
** **** ** * ***
** * * **** ** *
** **** ** * * ****
** * *** ** ** * *
** **** ** *** *** ** ***
** * * *** * *** * *
** **** ** * * ***** *******
** * *** **** * *** *
** **** ** *** ** ** * ***
** * * *** * ** *** **** ** *
** **** ** * ****** * * *** ****
** * *** **** **** *** ** * *
** **** ** *** * ** * * * *** ***
** * * *** * *** ** * *** ** * * * *
** **** ** * *** * * **** * * ** ******
** * *** **** ** ***** * ***** * * *
** **** ** *** * ** * * ** * ***** ***
** * * *** * ** * **** ** * ** ** * ** *
** **** ** * *** * * * *** **** * ** * ** * ****
** * *** **** **** ** ** *** * * **** * * *
** **** ** *** * ** * * *** * ** **** *** ** ***
** * * *** * ** * * ***** * ****** * * ** * * *
** **** ** * *** * * **** **** **** ** * * *********
** * *** **** **** * * ** * ** * * * * *