Mathematical definitions about the complexity of systems come from computing and information theory. In the mathematical aspect, complexity is treated in the context of mathematical objects like sequences of characters. The complexity of a system is the amount of information necessary to describe it, this is a descriptive complexity. In dynamical systems the description includes the changes of the system in time influencing the environment. Then the amount of information necessary to describe this reaction is a system of complexity in its behavior (taken from Yaneer Bar-Yam [3]).
In cellular automata theory, complexity can be discussed in several contexts, but we will focus to the amount of information that can be produced in the evolution space. For instance in The Game of Life the number of interactions that we can have among gliders, still life or other structures grows exponentially. Rule 110 may support an infinite amount of information because the collision among them is not limited, for example there are gliders with extensions that belong to set of the positive numbers. On the other hand the formation of groups among several gliders originates a series of limitless collisions in Rule 110.