What in a system is non-linear?

The question is what in a system is non-linear?  Linear chemical interactions of atoms and molecules, drive life which is essentially non-linear.  Peptide polymerization is linear. Yet only when peptides interact they create   proteins (enzymes) , exhibiting non-linear structure and behavior. The same applies the CA systems. Indeed the CA are linear, as you wrote, however their interaction initiates non-linear structure  and behavior. You have to distinguish between a linear engine consisting of CA, whose manifestation  is a non-linear change of structure and behavior.

You might liken the CA to isolated peptides. Once interacting they generate the complexity which we observe in life.  There are two pre-requisites for  this kind of non-linearity:  Interaction and death (turnover).

The non-linearity of life cannot be captured by current mathematical  tools.

There is a broader definition of non-linearity than mathematics has to offer. When you encounter a system  what you perceive is change.  Then you ask yourself where is this change going to?  In order to find out you decide that this change is a process and your task is to capture the essence of this change in order to predict where it is going to. You know its past and would like to predict its future. You obviously start with mathematical tools:

1. Assume that the change is linear and find out that you can’t predict its future.

2. You turn to non-linear mathematical tools, and still the future of this process is unpredictable.
3. Then you transform the observed change to make it linearly or non-linearly predictable. And the process is still unpredictable.
4. In short none  of the mathematical tools known today may foretell the future of this process.
5. Then your teachers turn to Plato and say that  this change which you observe is a corruption of how really this process ought to  behave . They beam with self-confidence and are ready to face a  corrupted future which current mathematical  tools foretell.

The non-linearity of an ant’s nest

In order to see what I mean do the following:
Look for an ant’s nest and study it for some time.  What you perceive is change. You already know that this nest is a process with a past and a future, yet you don’t have the tools to study its past. You can’t even define its today’s initial conditions on which you might construct a conceptual model for predicting the future. This is the non-linearity I am talking about.  Yet the nest is an organism which experienced its past  and has inborn expectations of what its future might be. Its “swarm –intelligence” outsmarts  any scientific intuition.
It is my humble belief that CA may capture a tiny bit of this non-linearity.