Concurrent local dynamics in elementary cellular automata.

摘要

Cellular Automata provide a class of formal abstractions of natural systems which have simple components but complex overall behaviors. This study investigated the dynamics of cellular automata from a local perspective and concentrated on some generic local behaviors rather than on the changes of entire, infinite configurations of cellular automata. The concept of the local system and the state of the local system was first established. A cellular Automaton was viewed as a collection of an infinite number of local systems undergoing concurrent state-transitions. According to whether or not "influence" can pass through a local system, two different type of states was identified, namely, the permeable state and the impermeable state. The existence of stable local attractor within impermeable states distinguishes the periodic dynamical phase from chaotic and complex (emergent) dynamical phase, and the existence of quasi-stable attractor further separates complex behavior from chaos. The quasi-stable attractors are those attractors whose stabilities are not Turing-decidable. These type of attractors set up a sufficient and necessary condition upon which order can be generated from chaos. This understanding potentially opens up numerous applications, and also leads to a computational worldview that could unify science in a different way.