download pdf 
ARXIV
peer reviewThe smallest nontrivial signature that can lead to growth (and therefore unbounded evolution) is 22 32. There are 4702 distinct left-connected rules with this signature. Here is a random sample of the behavior they generate, starting from a double self-loop {{0,0},{0,0}} and run for 8 steps:
Restricting to connected cases, there are 291 distinct outputs involving more than 10 relations after 8 steps:
The overall behavior we see here is very similar to what we saw with rules depending only on a single relation. But there is a new issue now to be addressed. With rules depending only on a single relation there is never any ambiguity about where the rule should be applied. But with rules that depend on more than one relation, there can be ambiguity, and the results one gets can potentially depend on the order in which updating is done.
Consider the rule
With our standard updating order, the result of running this rule for 30 steps is:
But with 6 different choices of random updating orders one gets instead:
None of these graphs are isomorphic, but all of them are qualitatively similar. Later on, we will discuss in detail the consequences of different updating orders, and their potentially important implications for physics. But for now, suffice it to say that at a qualitative level different updating orders typically lead to similar behavior.
As an example of something of an exception, consider the 22 32 rule shown in the array above:
With our standard updating order, this rule behaves as follows, yielding complicated-looking results with about 1.5n relations after n steps:
But with random updating order, the behavior is typically quite different. Here are six examples of results obtained after 10 steps—and all of them are disconnected: