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
Wolfram Institute
akshaj.devireddy@gmail.com
Abstract
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
