Volume 35, Number 1 (2026)

---

A Small Collatz Rule without the Plus One
Kevin Knight

The Collatz rule is one of the earliest examples of a simple, deterministic system that produces chaotic behavior. The rule takes any odd positive integer n to 3n+1 and any even positive integer n to n/2. Iterating this rule yields complex sequences whose dynamics are poorly understood; for example, it is unknown whether all such sequences reach 1 (the Collatz conjecture). It is reasonable to suspect that this complexity derives from the interplay of multiplication (3n) and addition (+1). However, in 2002, Monks was able to drop the +1 by constructing a 1$$021$$020-condition rule that simulates the Collatz rule using only multiplication. Monks’s rule greatly simplifies the Collatz dynamics but at the cost of an enormous rule. The current paper achieves the goal of removing addition with a significantly smaller 30-condition rule. We show how this rule replicates the Collatz process, and we place conditions on any cyclic trajectory purporting to be a counterexample to the Collatz conjecture.

Keywords: number theory; dynamical systems

Cite this publication as:
K. Knight, “A Small Collatz Rule without the Plus One,” Complex Systems, 35(1), 2026 pp. 1–9.
https://doi.org/10.25088/ComplexSystems.35.1.1

---

Exploring the Containment Hierarchy of Subrings over Rings ${\mathbb{Z}}_2$ to ${\mathbb{Z}}_9$ in Two-Dimensional Cellular Automata
Velvet Alexander, Ummity Srinivasa Rao, Kedar Shinde, Jayaram Balabaskaran, R. J. Hari, Asif Islam and Aqdus Bin Bari

This paper investigates the structural properties of two-dimensional cellular automata (2DCAs) over rings ${\mathbb{Z}}_2$ to ${\mathbb{Z}}_9$, focusing on rule composition, subring hierarchy and linear evolution. We prove that rule composition is commutative across all rings and that matrix transformations preserve hierarchical relationships. The subring containment is determined by the divisors of n: prime rings have only trivial subrings, while composite rings exhibit structured hierarchies. Let $I\in {\mathbb{Z}}_k^{n⨯n}$ be a configuration matrix. For rings in ${\mathfrak{S}}_1=\left\{{\mathbb{Z}}_2,{\mathbb{Z}}_4,{\mathbb{Z}}_8\right\}$, repeated elementwise addition modulo k maps the entries of I to their immediate subrings in the containment hierarchy. For ${\mathfrak{S}}_2=\left\{{\mathbb{Z}}_3,{\mathbb{Z}}_9\right\}$, triple summation modulo k similarly restricts the values to their corresponding subrings. Furthermore, we extend Moore neighborhood-based two-dimensional cellular automaton (2DCA) rules to rings from ${\mathbb{Z}}_2$ to ${\mathbb{Z}}_5$ and ${\mathbb{Z}}_7$ to ${\mathbb{Z}}_9$, proving that at time step t, rule matrices generate multiple non-overlapping replicas of the initial configuration across each ring and its subrings.
        Experiments in C++ across various rings and image sizes revealed two key patterns requiring further mathematical explanation. Rings with only trivial subrings—${\mathbb{Z}}_2$, ${\mathbb{Z}}_3$, ${\mathbb{Z}}_5$ and ${\mathbb{Z}}_7$—replicate the initial image at time steps $t=p^k$, where $p\in \left\{2,3,5,7\right\}$ and $k\ge 0$. In contrast, rings with nontrivial subrings—${\mathbb{Z}}_4$ and ${\mathbb{Z}}_8$—generate multiple replicas at $t=2^k$, while ${\mathbb{Z}}_9$ exhibits replication at $t=3^k$, producing both the original image and its subrings. The ring ${\mathbb{Z}}_6$, with disjoint subrings and no clear hierarchy, shows no such structured replication.

Keywords: two-dimensional cellular automata; rings; subrings; Moore neighborhood; linear rules; ${\mathbb{Z}}_2$ to ${\mathbb{Z}}_9$; image processing

Cite this publication as:
V. Alexander, U. S. Rao, K. Shinde, J. Balabaskaran, R. J. Hari, A. Islam and A. B. Bari, “Exploring the Containment Hierarchy of Subrings over Rings ${\mathbb{Z}}_2$ to ${\mathbb{Z}}_9$ in Two-Dimensional Cellular Automata,” Complex Systems, 35(1), 2026 pp. 11–38.
https://doi.org/10.25088/ComplexSystems.35.1.11

---

A General Result Relating Totalistic Cellular Automata and Self-Referential Sentences
Shuwen Wu and Ming Hsiung

We investigate the relationship between totalistic cellular automata (TCAs) and self-referential statements. It is well known that cellular automata (CAs) give rise to many undecidability issues related to self-referential statements. The study of self-referential statements and CAs can be traced back to the work of M. Hsiung [1], who established the connection between elementary cellular automata (ECAs) and self-referential paradoxes in terms of their evolution processes. We further deepen the connection between CAs and self-referential sentences. Specifically, we demonstrate the relationship is not only evident in one-dimensional ECAs but also extends to more complex two-dimensional TCAs. We elaborate on commonly applied TCAs, including Moore and von Neumann types. By studying their connection with self-referential sentences, we propose an algorithm for determining the fixed points of these CAs. Then, we classify them based on the (in)stability characteristics observed in their evolutionary processes. Additionally, we discuss certain specific self-referential paradoxes induced by these automata. Finally, we present a general result between TCAs and self-referential sentences.

Keywords: totalistic cellular automata; self-referential sentences; fixed point; paradox

Cite this publication as:
S. Wu and M. Hsiung, “A General Result Relating Totalistic Cellular Automata and Self-Referential Sentences,” Complex Systems, 35(1), 2026 pp. 39–61.
https://doi.org/10.25088/ComplexSystems.35.1.39

---

Phase Transitions in Complexity: Active Cell Growth, Shannon Entropy and Kolmogorov Complexity in Dependent Cell Ranges of Mobile Automata with Non-local Rules
Akshaj Devireddy

This paper investigates phase transitions in complexity within mobile automata governed by non-local rules. Unlike traditional cellular automata, mobile automata involve a single active cell navigating and updating a one-dimensional array of binary-state cells based on a rule set. By varying the number and symmetry of dependent cells in non-local rules, we observe abrupt changes in system behavior that we identify as computational phase transitions. Using active cell growth and three complementary metrics (Shannon block entropy and estimates of Kolmogorov–Chaitin complexity based on block decomposition and lossless compression), we quantitatively analyze the complexity of automata across a range of dependent cell configurations. Our results reveal that certain increases in non-locality trigger dramatic shifts in entropy and compressibility, while other expansions produce negligible or even simplifying effects. We categorize the observed transitions into categories based on their entropy and growth patterns and demonstrate that complexity does not scale linearly with non-locality. This paper provides a formal foundation for understanding structural complexity in mobile automata and contributes to the broader theory of emergent computation in simple rule-based systems.

Keywords: mobile automata; non-local rules; phase transitions; Shannon block entropy; Kolmogorov–Chaitin complexity; active cell growth; emergent behavior; cellular automata

Cite this publication as:
A. Devireddy, “Phase Transitions in Complexity: Active Cell Growth, Shannon Entropy and Kolmogorov Complexity in Dependent Cell Ranges of Mobile Automata with Non-local Rules,” Complex Systems, 35(1), 2026 pp. 63–88.
https://doi.org/10.25088/ComplexSystems.35.1.63

---

A 10-Bit S-Box Generated by Feistel Construction from Cellular Automata
Thomas Prévost and Bruno Martin

We propose a new 10-bit S-box generated from a Feistel construction. The subpermutations are generated by a five-cell cellular automaton (CA) based on a unique, well-chosen, local transition rule and bijective affine transformations. In particular, the CA rule is chosen based on empirical tests of its ability to generate good pseudorandom output on a ring CA. Similarly, the Feistel network layout is based on empirical data regarding the quality of the output S-box.
        We perform cryptanalysis of the generated 10-bit S-box: testing the properties of algebraic degree, algebraic complexity, nonlinearity, strict avalanche criterion, bit independence criterion, linear approximation probability, differential approximation probability, differential uniformity and boomerang uniformity. We relate the properties to those of the AES S-box. We find security properties comparable to or sometimes even better than those of the standard AES S-box. We believe that our S-box could be used to replace the five-bit substitution of ciphers like ASCON.

Keywords: S-box; block cipher; cellular automata; Feistel permutation; Boolean functions

Cite this publication as:
T. Prévost and B. Martin, “A 10-Bit S-Box Generated by Feistel Construction from Cellular Automata,” Complex Systems, 35(1), 2026 pp. 89–118.
https://doi.org/10.25088/ComplexSystems.35.1.89