Wolfram's automata, a simple implementation with Python

January 23, 2017

Complexity science is one of my favorite topics, ever. Studying complexity is how I ended up in the computer science bandwagon in the first place, and I constantly find myself thinking about how individual agents’ decisions affect the overall state of systems. Self-organization and emergence are fundamental aspects of how the pieces of the complexity puzzle fit together, and Wolfram’s elementary cellular automata are a great way to understand them.

From Wikipedia¹, these are “one-dimensional cellular automata where there are two possible states (labeled 0 and 1) and the rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors.” This sounds complicated, but in reality it is just complex, and can be explained with quite simply.

For example, the animation above is a run of Rule 30², which can be visualized easily: rule-30

Which represented by a Python dict looks like:

rule = {"111": '0', "110": '0', "101": '0', "000": '0',
        "100": '1', "011": '1', "010": '1', "001": '1'}

In this dictionary, each triplet (“the current state of the cell and its two immediate neighbors”) points to “the state of a cell in the next generation.” Basic arithmetic can show us that there will always be 8 states to consider in one of these rules.

Generating a pattern is just a matter of breaking some initial state into triplets, and iterating over the groups. An initial state, or seed, might look like this:

initial_state = '00000000000000000000100000000000000000000'

As we just saw, we calculate the next state for each cell by looking at groups of three cells at a time. This can be done with a windowing function:

def window(iterable, stride=3):
    for index in range(len(iterable) - stride + 1):
        yield iterable[index:index + stride]

The behavior of this function is pretty simple, and is best shown by example:

# notice that window is a generator
>>> window('foobar')
<generator object window at 0x10346bf10>
>>> list(window('foobar'))
['foo', 'oob', 'oba', 'bar']

If we apply this to our seed, we get what we’d expect, and computing the next state is quite straightforward: for every triplet, we look up the corresponding next state, and join it into a new string.

# >>> list(window(initial_state))
# ['000', '000', '000', '000', '000', '000', '000', '000',
#  '000', '000', '000', '000', '000', '000', '000', '000',
#  '000', '000', '001', '010', '100', '000', '000', '000',
#  '000', '000', '000', '000', '000', '000', '000', '000',
#  '000', '000', '000', '000', '000', '000', '000']

patterns = window(initial_state)
new_state = ''.join(rule[pat] for pat in patterns)

# >>> print(new_state)
# 00000000000000000111000000000000000000

It isn’t hard to see how repeating the same process again and again will give us the kind of behavior we see in the original animation. However, we need to add a bit of padding to accommodate for the special conditions of our (literal) edge cases, or we’ll shrink by two cells when processing each row.

# non-padded
state = initial_state
for _ in range(15):
    patterns = window(state)
    state = ''.join(rule[pat] for pat in patterns)
    print(state)

# 00000000000000000000100000000000000000000
# 000000000000000000111000000000000000000
# 0000000000000000110010000000000000000
# 00000000000000110111100000000000000
# 000000000000110010001000000000000
# 0000000000110111101110000000000
# 00000000110010000100100000000
# 000000110111100111111000000
# 0000110010001110000010000
# 00110111101100100011100
# 110010000101111011001
# 0111100110100001011
# 10001110011001101
# 101100111011100
# 0101110001001
# 10100101111


# padded
def generate_pattern(state, rule):
    for time in range(MAX_TIME):
        print(state)
        patterns = window(state)
        state = ''.join(rule[pat] for pat in patterns)
        state = '0{}0'.format(state)
    print(state)

# >>> generate_pattern(initial_state, rule)
# 00000000000000000000100000000000000000000
# 00000000000000000001110000000000000000000
# 00000000000000000011001000000000000000000
# 00000000000000000110111100000000000000000
# 00000000000000001100100010000000000000000
# 00000000000000011011110111000000000000000
# 00000000000000110010000100100000000000000
# 00000000000001101111001111110000000000000
# 00000000000011001000111000001000000000000
# 00000000000110111101100100011100000000000
# 00000000001100100001011110110010000000000
# 00000000011011110011010000101111000000000
# 00000000110010001110011001101000100000000
# 00000001101111011001110111001101110000000
# 00000011001000010111000100111001001000000
# 00000110111100110100101111100111111100000

Clearly, different rules, and different seeds, will give you different patterns:

RULES = {30: {"111": '0', "110": '0', "101": '0', "000": '0',
              "100": '1', "011": '1', "010": '1', "001": '1'},

         90: {"111": "0", "110": "1", "101": "0", "100": "1",
              "011": "1", "010": "0", "001": "1", "000": "0"},

         110: {"111": '0', "110": '1', "101": '1', "100": '0',
               "011": '1', "010": '1', "001": '1', "000": '0'},

         184: {"111": "1", "110": "0", "101": "1", "100": "1",
               "011": "1", "010": "0", "001": "0", "000": "0"}
         }

# generate_pattern(initial_state, RULES[110])
# 00000000000000000000100000000000000000000
# 00000000000000000001100000000000000000000
# 00000000000000000011100000000000000000000
# 00000000000000000110100000000000000000000
# 00000000000000001111100000000000000000000
# 00000000000000011000100000000000000000000
# 00000000000000111001100000000000000000000
# 00000000000001101011100000000000000000000
# 00000000000011111110100000000000000000000
# 00000000000110000011100000000000000000000
# 00000000001110000110100000000000000000000
# 00000000011010001111100000000000000000000
# 00000000111110011000100000000000000000000
# 00000001100010111001100000000000000000000
# 00000011100111101011100000000000000000000
# 00000110101100111110100000000000000000000

Surprisingly, these really simple mappings, which can be encoded in only 8 bits, can be used to model very complex behavior. Simple rules quickly give way to complexity, and it is likely that much of our world behaves according to similar, although more complex mappings.

There are all sorts of interesting mathematic properties behind how these automata actually work, and what kind of patterns arise from them, which are beyond the scope of this post. The fact that Stanislaw Ulam and John von Neumann were studying automata back in the 40s³ with the first electronic computers shows how fundamental these concepts are. Wolfram’s book on the topic is freely available online, and while I have only read bits and pieces of it, I am sure it does a better job of explaining them than I could without overloading the basic mechanics.

To download a runnable version of this script, and give this a shot on your own, you can find my code here.

Tweet at me and let me know what you think!

Wikipedia Contributors. Elementary cellular automaton., Wikipedia, The Free Encyclopedia. ↩
Weisstein, Eric W. “Rule 30.” From MathWorld, A Wolfram Web Resource. ↩
“John von Neumann’s Cellular Automata”. Embryo Project Encyclopedia. ↩

Want to see more articles like this? Sign up below:

Blog AF

Wolfram's automata, a simple implementation with Python