Complex Systems
Current Issue

Volume 28, Number 2 (2019)

On Patterns and Dynamics of Rule 22 Cellular Automaton Download PDF
Genaro J. Martínez, Andrew Adamatzky, Rolf Hoffmann, Dominique Désérable, and Ivan Zelinka

Rule 22 elementary cellular automaton (ECA) has a three-cell neighborhood, binary cell state, where a cell takes state “1” if there is exactly one neighbor, including the cell itself, in state 1. In Boolean terms, the cell state transition is an XOR function of three cell states. In physico–chemical terms, the rule might be seen as describing propagation of self-inhibiting quantities/species. Spacetime dynamics of rule 22 demonstrate nontrivial patterns and quasi-chaotic behavior. We characterize  the phenomena observed in this rule using mean field theory, attractors, de Bruijn diagrams, subset diagrams, filters, fractals and memory.

Keywords: elementary cellular automata; rule 22; chaos and complex dynamics

A Decidability Result for the Halting of Cellular Automata on the Pentagrid Download PDF
Maurice Margenstern

In this paper, we investigate the halting problem for deterministic cellular automata on the pentagrid. We prove that the problem is decidable when the cellular automaton starts its computation from a finite configuration and when it has two states, one of them being a quiescent state.

Keywords: tilings; hyperbolic plane; cellular automata; halting problem; decidability

Strong and Weak Spatial Segregation with Multilevel Discrimination Criteria Download PDF
Philippe Collard

This paper is influenced by the research of Thomas Schelling on spatial segregation; in his seminal work on the subject he used simple simulations to show that even highly tolerant individuals end up being spatially aggregated far beyond the local requirement of their tolerance level. In this paper we are not seeking to find the conditions, in terms of density of population and tolerance level, that lead to a global stable state where all the individuals are satisfied in view of their own neighborhoods. Here the context is: (i) a space full of agents where each individual is in continual contact with a maximum number of neighbors; and (ii) where both a principal and a secondary discrimination criterion compel people to leave their places. As, in general, the first hypothesis does not allow the population to converge within the meaning of Schelling, only incomplete segregation phenomena are observable. So the problematic will be to determine, according to the respective strength of the two discrimination criteria, the spatial repartition of the agents resulting from their moves; in such a general context, we will refer to segregation as being strong or weak or even mixed.

Keywords: spatial segregation; computational sociology; agent-based simulation; multilevel discrimination criteria

A Measure for the Complexity of Elementary Cellular Automata Download PDF
Thorsten Ewert

A new measure for the complexity of elementary cellular automata (ECAs) is presented. This measure is based on the minimization of Boolean functions with three variables that represent the elementary cellular automaton (ECA) rules. The minimized Boolean functions reduce the number of input bits of the truth table, which is equivalent to the rule table of an ECA. This results in a fractalized number of Boolean variables that are equal to the state variables of a dynamic system. Furthermore, the dynamic nature of complexity in ECAs is considered. Therefore, a new method of defining and deriving the complexity of all 256 ECA rules given in bits is proposed. The results then can be described, classified and grouped. As for other continuous or discrete dynamic systems, the complexity grows with the number and the usage of the state variables. In ECAs, the numbers of the effective state variables range from 0 to 3, resulting in four classes of behavior.

Keywords: complexity; measure; elementary cellular automaton

Neural Control Model for an Inverted Double Pendulum Download PDF
Alexander M. Coxe

Rolling cart stabilization for the inverted double pendulum in analog to the usual system of the inverted pendulum is explored. An appropriate linearization for the equations of motion near equilibrium is noted, and a proportional derivative controller is developed. This system is run from many initial conditions through many time steps to generate multiple time series of algorithm response to the imbalanced system. These time series are repurposed as a list of associations and used as a large training set for an artificial neural network. When applied to the inverted double pendulum system, the trained neural network is seen to provide much more stable control than the algorithm from which it was trained. It appears the neural network learns predictive stabilization from the training set and is able to react to the system more quickly than the algorithm can compute a correction.

Keywords: neural networks; control systems, optimal control; computational irreducibility

Current issue Subscribe

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