Cross-boundary Behavioural Reprogrammability of Cellular Automata from Emulation Networks.
Jürgen Riedel, Héctor Zenil · arXiv (Cornell University) · 2015
We explore the reprogramming capabilities of computer programs using cellular automata (CA). We show a series of boundary crossing results, including cases of Wolfram Class 1 Elementary Cellular Automata (ECA) emulating Class 2 ECA, Class 2 ECA emulating Class 3 ECA, and Class 3 ECA emulating Class 2 ECA, along with results of a similar type for general CA (neighbourhood $r=3/2$), including Class 1 CA emulating Class 3 CA, Classes 3 and 4 CAs emulating Class 4 CAs, and Class 4 emulating Class 3 CAs. The emulations occur with only a linear overhead and are therefore computationally efficient. By constructing emulation networks through an exhaustive search in the compiler space, we show that topological properties determining emulation direction, such as ingoing and outgoing hub degrees, suggest a topological classification of complexity based on computing capabilities. We provide a new Turing-universality result in ECA space based on a composition of ECA rules emulating ECA rule 110. The results suggest that complexity is, or can be, completely driven by initial conditions, and these are therefore in this sense more fundamental than the computer program code/rules. The approach yields a novel perspective on complexity, controllability, causality, and reprogrammability of even the simplest computer programs providing strong evidence of ubiquitous intrinsic and Turing-universality.