Complex Systems
Current Issue

Volume 31, Number 2 (2022)

Charting a Course for “Complexity”: Metamodeling, Ruliology and More Download PDF
Stephen Wolfram

This is the first of a series of pieces I’m planning in connection with the upcoming 20th anniversary [1] of the publication of A New Kind of  Science [2] (September 23, 2021).

Cite this publication as:
S. Wolfram, “Charting a Course for “Complexity”: Metamodeling, Ruliology and More,” Complex Systems, 31(2), 2022 pp. 165–190.

Improved Majority Identification by the Coarsened Majority Automaton Download PDF
David Peak, Charles G. Torre and Jenny R. Whiteley

The initial majority identification task is a fundamental test problem in cellular automaton research. To pass the test, a two-state automaton has to attain a uniform configuration consisting of only the state that was initially in the majority. It does so solely through its local, internal dynamics—i.e., success in the task is an example of emergent computation. Finding new, better-performing automata continues to be of interest for what additional clues they might reveal about this form of computation. Here we describe a novel, coarsened version of one of the standard majority identifiers. We show that this coarsened system outperforms its parent automaton while significantly reducing the number of computations required to accomplish the task.

Keywords: cellular automata; majority identification; coarsened dynamics

Cite this publication as:
D. Peak, C. G. Torre and J. R. Whiteley, “Improved Majority Identification by the Coarsened Majority Automaton,” Complex Systems, 31(2), 2022 pp. 191–202.

The Effects of Interaction Functions between Two Cellular Automata Download PDF
Alyssa M. Adams

Biological systems are notorious for complex behavior within short timescales (e.g., metabolic activity) and longer timescales (e.g., evolutionary selection), along with their complex spatial organization. Because of their complexity and their ability to innovate with respect to their environment, living systems are considered to be open-ended. Historically, it has been difficult to model open-ended evolution and innovation. As a result, our understanding of the exact mechanisms that distinguish open-ended living systems from nonliving ones is limited. One of the biggest barriers is understanding how multiple, complex parts within a single system interact and contribute to the complex, emergent behavior of the system as a whole. How do interactions between parts of a system lead to more complex behavior of the system as a whole? This paper presents two interacting cellular automata (CAs) as an abstract model to address the effects of complex interactions between two individual entities embedded within a larger system. Unlike elementary CAs, each cellular automaton (CA) changes its update rules as a function of the system’s state as a whole. The resulting behavior of the two-CA system suggests that complex interaction functions between the two CAs have little to no effect on the complexity of each individual CA’s behavior and structure. However, having an interaction function that is random results in open-ended evolution regardless of the specific type of state-dependency.

Keywords: cellular automata; open-ended evolution; algorithmic complexity; interactions

Cite this publication as:
A. M. Adams, “The Effects of Interaction Functions between Two Cellular Automata,” Complex Systems, 31(2), 2022 pp. 203–217.

Graph Matching with Distance-Preserving Crossover Download PDF
Thomas Bärecke and Marcin Detyniecki

Graph models are fundamental to any kind of application on structured real-world problems. Any comparison between graphs by a graph distance measure requires the solution of the inexact graph matching problem, which constitutes a hard combinatorial optimization problem. An inexact matching problem includes in its formulation robustness to any type of perturbation, such as, for instance, noise, inherently present in real-world environments. In this paper, we introduce the concept of distance-preserving crossover operators for genetic algorithms for this task. For large graphs, our algorithm outperforms any state-of-the-art approximate algorithm—in particular, genetic algorithms with alternative crossover operators, which are to the best of our knowledge currently limited to no more than 50 nodes. We use a two-level local search heuristic to further enhance the results, pushing the limits to up to 300 nodes: a first local search step is directly integrated into the crossover operator; another one is applied independently during offspring generation.

Keywords: graph distance; evolutionary computation; genetic algorithm; inexact graph isomorphism; permutation encoding; crossover operator with local search

Cite this publication as:
T. Bärecke and M. Detyniecki, “The Effects of Interaction Functions between Two Cellular Automata,” Complex Systems, 31(2), 2022 pp. 219–246.

A Use of Variety as a Law of the Universe Download PDF
Furkan Semih Dündar

This paper explores the idea of a toy model universe as a character string where each character is either X or -. The string makes a transition between states that are of maximal variety. The definition of variety given by Barbour and Smolin is used in this paper. An interpretation of the toy model universe is given in terms of Everett’s many-worlds interpretation. The paper also discusses whether new maximal variety strings can be obtained by addition or subtraction of maximal variety strings. A few comments are included about the use of quantum computers, which may help find the maximal variety strings more quickly.

Keywords: maximal variety; character strings; Leibniz  

Cite this publication as:
F. S. Dündar, “A Use of Variety as a Law of the Universe,” Complex Systems, 31(2), 2022 pp. 247–260.

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 »