Investigating Transformational Complexity: Counting Functions a Region Induces on Another in Elementary Cellular Automata

Abstract

Over the years, the field of artificial life has attempted to capture significant properties of life in artificial systems. By measuring quantities within such complex systems, the hope is to capture the reasons for the explosion of complexity in living systems. A major effort has been in discrete dynamical systems such as cellular automata, where very few rules lead to high levels of complexity. In this paper, for every elementary cellular automaton, we count the number of ways a finite region can transform an enclosed finite region. We discuss the relation of this count to existing notions of controllability, physical universality, and constructor theory. Numerically, we find that particular sizes of surrounding regions have preferred sizes of enclosed regions on which they can induce more transformations. We also find three particularly powerful rules (90, 105, 150) from this perspective.