|
Kaleidoscope of Life Susumu Adachi, Jia Lee, One of the challenges of cellular automaton research is finding models with a low complexity and at the same time a rich dynamics. A measure of low complexity is the number of states in the model and the number of transition rules to switch between those states. In this paper, we propose a 2-dimensional 2-state cellular automaton that|though governed by a single simple transition rule|has a sufficiently rich dynamics to be computationally universal. According to the transition rule, a cellfs state is determined by the sum of the states of the cells at orthogonal or diagonal distances one or two from the cell (distance-2 Moore neighbourhood), but not by the previous state of the cell itself. Notwithstanding its simplicity, this model is able to generate a great variety of patterns, including several types of stable configurations, oscillators and patterns that move over cellular space (gliders). We prove the computational universality of the model by constructing a universal set of logic gates (NOT and AND) from these patterns. A key element in this proof is the shifting of phases and positions of signals such that they meet the input requirements of the logic gates. Similarities of the model with classical spin systems are also discussed. doi:10.1016/j.physd.2007.10.015 |