Cross-boundary Behavioural Reprogrammability Reveals Evidence of Pervasive Universality
Jürgen Riedel and Hector Zenil
We exhaustively explore the reprogrammability capabilities and the intrinsic universality of the Cartesian product P × C of the space P of all possible computer programs of increasing size and the space C of all possible compilers of increasing length such that p ∈ P emulates p’ ∈ P with T |p’| = |p| under a coarse-graining transformation T. Our approach yields a novel perspective on the complexity, controllability, causality and (re)programmability discrete dynamical systems. We find evidence that the density of (qualitatively different) computer programs that can be reprogrammed grows asymptotically as a function of program and compiler size. To illustrate these findings we show a series of behavioural boundary crossing results, including emulations (for all initial conditions) of Wolfram class 2 Elementary Cellular Automata (ECA) by Class 1 ECA, emulations of Classes 1, 2 and 3 ECA by Class 2 and 3 ECA, and of Classes 1, 2 and 3 by Class 3 ECA, along with results of even greater emulability for general CA (neighbourhood r = 3/2), including Class 1 CA emulating Classes 2 and 3, and Classes 3 and 4 emulating all other classes (1, 2, 3 and 4). The emulations occur with only a linear overhead and can be considered computationally efficient. We also found that there is no hacking strategy to compress the search space based on compiler profiling in terms of e.g. similarity or complexity, suggesting that no strategy other than exhaustive search is viable. We also introduce emulation networks, derive a topologically-based measure of complexity based upon out- and in-degree connectivity, and establish bridges to fundamental ideas of complexity, universality, causality and dynamical systems.
Keywords: Cellular automata; intrinsic universality; sensitivity; computer simulation; automata theory; compilers; dynamical systems; reprogrammability; causality; turing-universality; controllability