Cross-boundary Behavioural Reprogrammability Reveals Evidence of Pervasive Turing-Universality

New paper sheds light on the pervasiveness of Turing universality by showing 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. The paper also introduces a concept of emulation networks, deriving a topologically-based measure of complexity based upon out- and in-degree connectivity establishing bridges to fundamental ideas of complexity, universality, causality and dynamical systems.

Source: www.oldcitypublishing.com