Toward a quantitative theory of self-generated complexity (Q1084370)

Quantities are defined operationally which qualify as measures of complexity of patterns arising in physical situations. Their main features, distinguishing them from previously used quantities, are the following: (1) they are measure-theoretic concepts, more closely related to Shannon entropy than to computational complexity; and (2) they are observables related to ensembles of patterns, not to individual patterns. Indeed, they are essentially Shannon information needed to specify not individual patterns, but either measure-theoretic or algebraic properties of ensembles of patterns arising in a priori translationally invariant situations. Numerical estimates of these complexities are given for several examples of patterns created by maps and by cellular automata.