## Volume 27, Number 1 (2018)

**Logical Universality from a Minimal Two-Dimensional Glider Gun**

José Manuel Gómez Soto and Andrew Wuensche

To understand the underlying principles of self-organization and computation in cellular automata, it would be helpful to find the simplest form of the essential ingredients, glider guns and eaters, because then the dynamics would be easier to interpret. Such minimal components emerge spontaneously in the newly discovered Sayab rule, a binary two-dimensional cellular automaton with a Moore neighborhood and isotropic dynamics. The Sayab rule's glider gun, which has just four live cells at its minimal phases, can implement complex dynamical interactions and the gates required for logical universality.
*Keywords*: universality; cellular automata; glider gun; logical gates

**Wireworld++: A Cellular Automaton for Simulation of Nonplanar Digital Electronic Circuits**

Vladislav Gladkikh and Alexandr Nigay

An enhanced version of the Wireworld cellular automaton called Wireworld++ is introduced. It can be considered as a generalization of Wireworld suitable for modeling digital electronic circuits that have intersections of unconnected wires. As most electronic circuits except trivial ones have wire crossings, Wireworld++ is a more convenient cellular automaton for modeling digital electronics than the conventional Wireworld. Wireworld++ is two dimensional; it has a small number of states and simple and intuitive rules. Despite that, it allows simulation of three-dimensional elements of digital circuits, for instance, wire crossings or electronic components placed on both sides of printed circuit boards. The key electronic parts, such as logic gates, implemented in Wireworld++ exhibit more symmetry and utilize fewer cells than their Wireworld counterparts. Wireworld++ can also be applied to simulation of computing devices in a sub-excitable, light-sensitive Belousov–Zhabotinsky medium organized in a rectangular grid of vesicles.
*Keywords*: Wireworld; digital electronics; wire crossings; logic gates; Belousov–Zhabotinsky reaction

**Definition and Identification of Information Storage and Processing Capabilities as Possible Markers for Turing Universality in Cellular Automata**

Yanbo Zhang

To identify potential universal cellular automata (CAs), a method is developed to measure the information processing capacity of elementary cellular automata (ECAs). Two features of CAs are considered: ability to store information and ability to process information. Local collections of cells are defined as particles of CAs and the information contained by particles is examined. By using this method, information channels and intersections of channels can be shown. By observing these two features, potential universal CAs are classified into a certain class, and all ECAs can be classified into four groups, which correspond to Wolfram's four classes: 1, homogeneous; 2, regular; 3, chaotic and 4, complex. This result shows that using the abilities of storing and processing information to characterize complex systems is effective and succinct. It is found that these abilities are capable of quantifying the complexity of systems.
*Keywords*: cellular automata; Turing universality; cellular automata classification

**Two-Step Markov Update Algorithm for Accuracy-Based Learning Classifier Systems**

Mohammad Razeghi-Jahromi, Shabnam Nazmi, and Abdollah Homaifar

In this paper, we investigate the impact of a two-step Markov update scheme for the reinforcement component of XCS, a family of accuracy-based learning classifier systems. We use a mathematical framework using discrete-time dynamical system theory to analyze the stability and convergence of the proposed method. We provide frequency domain analysis for classifier parameters to investigate the achieved improvement of the XCS algorithm, employing a two-step update rule in the transient and steady-state stages of learning. An experimental analysis is performed to learn to solve a multiplexer benchmark problem to compare the results of the proposed update rules with the original XCS. The results show faster convergence, better steady-state training accuracy and less sensitivity to variations in learning rates.
*Keywords*: two-step Markov update rule; accuracy-based classifier system; stability and convergence analysis; linear discrete-time dynamical system

**Exploring Halting Times for Unconventional Halting Schemes**

Katarzyna Krzyzanska

A common issue in the study of Turing machines (TMs) is the halting problem, or whether and when a TM will cease moving. Generally, this problem has been proved to be uncomputable, though it is possible to determine halting probabilities for more specific cases. In the following study, halting probabilities were determined using two unconventional definitions of halting. The first defines halting as the point where a machine reaches a certain, prespecified step; the second defines halting as the point where cell states stop changing (though head states may still differ from step to step). Due to computational limitations, the halting probabilities for TMs with fewer head and cell states have been more thoroughly studied than for more complicated machines, but nonetheless some data has been garnered concerning those. The TMs studied ranged from two possible head states and two possible cell states to six possible head states and six possible cell states.
*Keywords*: Turing machines; halting problem; complexity; estimation

*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

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 »