Indeed, this kind of rapid increase in network complexity is a general characteristic of most class 3 and 4 rules. But it turns out that there are a few rules which at first appear to be exceptions.
The pictures at the top of the next page show four different rules that each have the property that if started from initial conditions in which all possible sequences of cells are allowed, these same sequences can all still occur at any subsequent step in the evolution.
The first two rules that are shown exhibit very simple class 2 behavior. But the last two show typical class 3 behavior.
What is going on, however, is that in a sense the particular initial conditions that allow all possible sequences are special for these rules.