Complex Systems
Current Issue

Volume 31, Number 3 (2022)

Homotopies in Multiway (Nondeterministic) Rewriting Systems as n-Fold Categories Download PDF
Xerxes D. Arsiwalla, Jonathan Gorard and Hatem Elshatlawy

We investigate algebraic and compositional properties of abstract multiway rewriting systems, which are archetypical structures underlying the formalism of the Wolfram model. We demonstrate the existence of higher homotopies in this class of rewriting systems, where homotopical maps are induced by the inclusion of appropriate rewriting rules taken from an abstract rulial space of all possible such rules. Furthermore, we show that a multiway rewriting system with homotopies up to order n may naturally be formalized as an n-fold category, such that (upon inclusion of appropriate inverse morphisms via invertible rewriting relations) the infinite limit of this structure yields an ∞-groupoid. Via Grothendieck’s homotopy hypothesis, this ∞-groupoid thus inherits the structure of a formal homotopy space. We conclude with some comments on how this computational framework of homotopical multiway systems may potentially be used for making formal connections to homotopy spaces upon which models relevant to physics may be instantiated.

Keywords: Wolfram model; multiway rewriting systems; rulial space; homotopy theory; higher category theory

Cite this publication as:
X. D. Arsiwalla, J. Gorard and H. Elshatlawy, “Homotopies in Multiway (Nondeterministic) Rewriting Systems as n-Fold Categories,” Complex Systems, 31(3), 2022 pp. 261–277.

Infinitely Growing Configurations in Emil Post’s Tag System Problem Download PDF
Nikita V. Kurilenko

Emil Post’s tag system problem posed the question of whether or not a tag system {N=3, P(0)=00, P(1)=1101} has a configuration, simulation of which will never halt or end up in a loop. Over the subsequent decades, there were several attempts to find an answer to this question, including a recent study, during which the first 2 84 initial configurations were checked. This paper presents a family of configurations of this type in the form of strings A n B C m that evolve to A n + 1 B C m + 1 after a finite number of steps. The proof of this behavior for all non-negative n and m is described later in this paper as a finite verification procedure, which is computationally bounded by 20000 iterations of tag.

Keywords: tag systems; chaotic systems

Cite this publication as:
N. V. Kurilenko, “Infinitely Growing Configurations in Emil Post’s Tag System Problem,” Complex Systems, 31(3), 2022 pp. 279–286.

Dissipative Arithmetic Download PDF
William B. Langdon

Large arithmetic expressions are dissipative: they lose information and are robust to perturbations. Lack of conservation gives resilience to fluctuations. The limited precision of floating point and the mixture of linear and nonlinear operations make such functions anti-fragile and give a largely stable locally flat plateau a rich fitness landscape. This slows long-term evolution of complex programs, suggesting a need for depth-aware crossover and mutation operators in tree-based genetic programming. It also suggests that deeply nested computer program source code is error tolerant because disruptions tend to fail to propagate, and therefore the optimal placement of test oracles is as close to software defects as practical.

Keywords: information loss; irreversible computing; entropy; evolvability; arithmetic; software mutational robustness; optimal test oracle placement; evolution of complexity; data dependent computational irreducibility; effective computational equivalence; experimental mathematics; algorithmic information dynamics

Cite this publication as:
W. B. Langdon, “Dissipative Arithmetic,” Complex Systems, 31(3), 2022 pp. 287–309.

Parametric Validation of the Reservoir Computing–Based Machine Learning Algorithm Applied to Lorenz System Reconstructed Dynamics Download PDF
Samuele Mazzi and David Zarzoso

A detailed parametric analysis is presented, where the recent method based on the reservoir computing paradigm, including its statistical robustness, is studied. It is observed that the prediction capabilities of the reservoir computing approach strongly depend on the random initialization of both the input and the reservoir layers. Special emphasis is put on finding the region in the hyperparameter space where the ensemble-averaged training and generalization errors together with their variance are minimized. The statistical analysis presented here is based on the projection on proper elements method.

Keywords: reservoir computing; Lorenz system; hyperparameters; error quantification; machine learning

Cite this publication as:
S. Mazzi and D. Zarzoso, “Parametric Validation of the Reservoir Computing–Based Machine Learning Algorithm Applied to Lorenz System Reconstructed Dynamics,” Complex Systems, 31(3), 2022 pp. 311–339.

Elementary Cellular Automata along with Delay Sensitivity Can Model Communal Riot Dynamics Download PDF
Souvik Roy, Sukanta Das and Abhik Mukherjee

This paper explores the potential of elementary cellular automata to model the dynamics of riot. Here, to model such dynamics, we introduce probabilistic loss of information and delay perturbation in the updating scheme of automata to capture sociological parameters—presence of anti-riot population and organizational presence of communal forces in the rioting society, respectively. Moreover, delay has also been incorporated in the model to capture the nonlocal interaction of neighbors. Finally, the model is verified by an event of riot that occurred in Baduria of West Bengal, India.

Keywords: elementary cellular automata (ECAs); delay; probabilistic loss of information; phase transition; riot dynamics

Cite this publication as:
S. Roy, S. Das and A. Mukherjee, “Elementary Cellular Automata along with Delay Sensitivity Can Model Communal Riot Dynamics,” Complex Systems, 31(3), 2022 pp. 341–361.

Current issue Subscribe

Complex Systems ISSN 0891-2513
© 1987–2022
Complex Systems Publication, Inc.

Published four times annually
Complex Systems Publications, Inc.
P.O. Box 6149
Champaign, IL 61826 USA

Subscribe Now


Join the leading edge of complex systems research today. There are no publication charges. Authors are provided with 25 reprints of papers published in Complex Systems. Papers may be submitted via the web or email. Find out more »