On the nature and origin of complexity in discrete,homogeneous, locally-interacting systems

The observed complexity of nature is often attributed to an intrinsic propensity of matter to self-organize under certain (e.g., dissipative) conditions. In order better to understand and test this vague thesis, we define complexity as logical depth, a notion based on algorithmic information and computational time complexity. Informally, logical depth is the number of steps in the deductive or causal path connecting a thing with its plausible origin. We then assess the effects of dissipation, noise, and spatial and other symmetries of the initial conditions and equations of motion on the asymptotic complexity-generating abilities of statistical-mechanical model systems. We concentrate on discrete, spatially-homogeneous, locally-interacting systems such as kinetic Ising models and cellular automata.