Chapter 8 - Algorithmic and grammatical complexities

Summary

The core of the problem when dealing with a complex system is the difficulty in discerning elements of order in its structure. If the object of the investigation is a symbolic pattern, one usually examines finite samples of it. The extent to which these can be considered regular, however, depends both on the observer's demand and on their size. If strict periodicity is required, this might possibly be observed only in very small patches. A weaker notion of regularity permits the identification of larger “elementary” domains. This intrinsic indefiniteness, shared alike by concepts such as order and organization, seems to prevent us from attaining a definition of complexity altogether. This impasse can be overcome by noticing that the discovery of the inner rules of the system gives a clue as to how its description can be shortened. Intuitively, systems admitting a concise description are simple. More precisely, one tries to infer a model which constitutes a compressed representation of the system. The model can then be used to reproduce already observed patterns, as a verification, or even to “extend” the whole object beyond its original boundaries, thus making a prediction about its possible continuation in space or time.

As we shall see, a crucial distinction must be made at this point.