Complex Systems
Current Issue

Volume 27, Number 2 (2018)

The Time Evolution of a Greenberg–Hastings Cellular Automaton on a Finite Graph
Nobutaka Doba

The Greenberg–Hastings cellular automaton (GHCA) is a probabilistic two-dimensional cellular automaton with a Moore or von Neumann neighborhood to mimic pattern formations of excitable media. It is also defined on a graph, where a vertex corresponds to a cell and its adjacent vertices to the neighborhood of the cell. In this paper, we study a three-valued GHCA on an arbitrary finite connected graph analytically, though it has been mainly investigated numerically. We prove that “maximum cycle density” completely decides asymptotic behavior of its time evolution. Keywords: Greenberg–Hastings cellular automaton; graph cellular automaton

Nonlocal and Light Cone Dynamics Emergent from Information-Propagating Complete Graph
Thomas L. Wood

Theories relating to the discretization of spacetime and results from quantum information theory have indicated that physically observable behavior may be emergent from such an underlying yet unknown microscopic theory. In this paper, a candidate discrete system, based on the structure presented in [1] is explored, via direct computational implementation. The microstates of the system evolve via information transfer mechanisms on dynamic complete graphs built upon substitution networks developed in [1]. Using the positive integer edge weights as measures of distance, the system is artificially embedded in by treating the flat space violations as stress, resulting in a curved geometry (Figure 1). This stress then effects a force on the vertices. In this paper, light cone dynamics of the motion of the minima of this stress are observed, along with superluminal motion of the vertices. We argue that this superluminal velocity corresponds to the quantum mechanical discontinuous motion of particles and provides possibilities for descriptions of entanglement and particle spin within the system. Further to this, that the compatibility of this type of dynamics with relativistic behavior makes this system nontrivial and worthy of further investigation. Keywords: point particle; interaction edge; space element; state graph; duplication; reduction; microstate; stress minimization; embedding; cumulative velocity; minimized velocity

Using Elementary Cellular Automata to Model Different Research Strategies and the Generation of New Knowledge
Georg Jäger

In this study, elementary cellular automata (CAs) are used to model the process of generating new knowledge. Each research goal is formulated as a target state of an elementary cellular automaton, while the scientific method used to reach this goal is represented as a rule. This system has many similarities to the actual process of knowledge generation, mainly caused by the possible complex behavior of CAs. The proposed model is then used to compare different strategies of scientific research like inter- and intradisciplinary cooperation in different scenarios. The obtained results are in agreement with reality and therefore substantiate the assumption that CAs are suitable to model the process of scientific research. Keywords: knowledge generation; modeling complex systems; interdisciplinary cooperation; elementary cellular automata

Complexity Steering in Cellular Automata
Bar Y. Peled and Avishy Y. Carmi

A cellular automaton is presented whose governing rule is that the Kolmogorov complexity of a cell’s neighborhood may not increase when the cell’s present value is substituted for its future value. Using an approximation of this two-dimensional Kolmogorov complexity, the underlying automaton is shown to be capable of simulating binary logic circuits. A similar automaton whose rule permits at times the increase of a cell’s neighborhood complexity is shown to produce animated entities that can be used as information carriers akin to gliders in Conway’s Game of Life. The element that repeatedly generates gliders, the glider gun, is constructed in this automaton using a number of self-replicating mechanisms. Moreover, gliders’ annihilation and creation allow constructing logic gates as well as data encoding mechanisms. Keywords: cellular automata; Kolmogorov complexity; universal computation; self-replication; negentropy

The Slowdown Theorem: A Lower Bound for Computational Irreducibility in Physical Systems
Jonathan Gorard

Following from the work of Beggs and Tucker on the computational complexity of physical oracles, a simple diagonalization argument is presented to show that generic physical systems, consisting of a Turing machine and a deterministic physical oracle, permit computational irreducibility. To illustrate this general result, a specific analysis is provided for such a system (namely a scatter machine experiment (SME) in which a classical particle is scattered by a sharp wedge) and proves that it must be computationally irreducible. Finally, some philosophical implications of these results are discussed; in particular, it is shown that the slowdown theorem implies the existence of classical physics experiments with undecidable observables, as well as the existence of a definite lower bound for the computational irreducibility of the laws of physics. Therefore, it is argued that the hypothesis that “the universe is a computer simulation” has no predictive (i.e., only retrodictive) power. Keywords: computational irreducibility; computational equivalence; computational complexity; Turing machines; physics; simulations;  slowdown; experiments

Current issue Subscribe

Complex Systems ISSN 0891-2513
© 1987–2018
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 »