But from what we have seen in this section such behavior appears to be quite rare: unlike many of the simple rules that we have discussed in this book, it seems that almost all simple constraints lead only to fairly simple patterns. Any phenomenon based on rules can always ultimately also be described in terms of constraints. … The pattern required to satisfy this constraint corresponds to a shifted version of the one generated by the evolution of the rule 30 elementary one-dimensional cellular automaton.

And indeed it is a common feature of systems of limited size that the repetition period one sees can depend greatly on the exact size of the system and the exact rule that it follows. … The pictures below show another example of a system of limited size based on a simple rule. The particular rule is at each step to double the number that represents the position of the dot, wrapping around as soon as this goes past the right-hand end.

In the substitution systems for strings discussed in previous sections , the rules that are given can involve replacing any block of elements by any other. … Examples of rules that involve replacing clusters of nodes in a network by other clusters of nodes. All these rules preserve the planarity of a network.

In each case the whole pattern can be generated by repeatedly applying the substitution system rule shown. … The first example shown corresponds to cellular automaton rule 60; the last two examples correspond respectively to rules 90 and 150.

How complicated do the rules need to be in order to get universality? … The rule for a universal Turing machine with 7 states and 4 colors constructed in 1962. … Note that one element of the rule can be considered as specifying that the Turing machine should "halt" with the head staying in the same location and same state.

As the picture at the bottom of the previous page illustrates, this Turing machine emulates rule 110 in a quite straightforward way: its head moves systematically backwards and forwards, at each complete sweep updating all cells according to a single step of rule 110 evolution. And knowing from earlier in this chapter that rule 110 is universal, it then follows that the 2-state 5-color Turing machine must also be universal.

But if the underlying rules for the network preserve planarity then each of these pieces of non-planarity must on their own be persistent—and can in a sense only disappear through processes like annihilating with each other. … In the realistic case of network rules for the universe, planarity as such is presumably not preserved. … And ultimately the values of these quantities must reflect properties of underlying networks that are preserved by network evolution rules.

But what if one allows Turing machines with more complicated rules? With 4-state 2-color rules it turns out to be possible to generate the same output as examples (c) and (d) in just a fixed number of steps. But for none of the other 3-state 2-color Turing machines shown do 4-state rules offer any speedup.

there are all sorts of features in the behavior of these rules that could in principle represent a possible purpose. But what is special about rules like those on the previous page is that they are the minimal ones that exhibit the particular feature of doubling their input. … Computational irreducibility implies that it can be arbitrarily difficult to find minimal or optimal rules.

Implementation of totalistic cellular automata To handle totalistic rules that involve k colors and nearest neighbors, one can add the definition CAStep[TotalisticCARule[rule_List, 1], a_List] := rule 〚 -1 - (RotateLeft[a] + a + RotateRight[a]) 〛 to what was given on page 867 . The following definition also handles the more general case of r neighbors: CAStep[TotalisticCARule[rule_List, r_Integer], a_List] := rule 〚 -1 - Sum[RotateLeft[a, i], {i, -r, r}] 〛 One can generate the representation of totalistic rules used by these functions from code numbers using ToTotalisticCARule[num_Integer, k_Integer, r_Integer] := TotalisticCARule[IntegerDigits[num, k, 1 + (k - 1)(2r + 1)], r]