An algebraic measure of complexity

Discrete dynamical systems are defined as a set S of states provided with an evolution operator U: S → S; evolution proceeds in discrete time steps. A reading operator σ acting on S that generates a group (σ), is introduced and determines what are the state aspects that are observable. State configurations are thus defined as sets of states that cannot be resolved by σ. The set of configurations is ordered in complexity layers, defined as classes of configurations that are stabilized by isomorphic subgroups of (σ). Layers are indexed by the quotient (σ)/H, where H⊂(σ), up to an isomorphism, stabilizes the configurations in a given layer. Generally, the algebraic complexity is defined as (σ)/H, while for a finite (σ) a complexity number, κσ(x)=[(σ):Gx], is defined, where x ε{lunate} S, and Gx⊂(σ) stabilizes x. Irreversibility of evolution implies that Gx⊂GU.x or, for finite (σ), Δκσ≥0, at every time step in evolution, provided that [σ, U] = 0. This effect of complexity degredation gives the dynamical system the property of self-similarity. Translation complexity is used to study one-dimensional cellular automata. © 1991.

VIVO