An algebraic measure of complexity (Q2640205)

The notion of an algebraic measure of complexity is discussed: Given a discrete dynamical system U: \(S\to S\), where S is the set of states, a reading operator \(\sigma\) acting on S is introduced which determines which state aspects are observable and this generates a group (\(\sigma\)). State configurations are thus defined as sets of states that cannot be resolved by \(\sigma\). The set of configurations is ordered in complexity layers, defined as classes of configurations that are stabilized by isomorphic subgroups of (\(\sigma\)). These layers are indexed by (\(\sigma\))/H where H, up to an isomorphism, stabilizes the configuration of a given layer. The algebraic complexity is given as (\(\sigma\))/H and for finite (\(\sigma\)) a complexity number is introduced. The notions of complexity degradation and translation complexity are discussed with particular reference to one-dimensional cellular automata.