A General Result Relating Totalistic Cellular Automata and Self-Referential Sentences
Shuwen Wu
Fudan University
Shanghai, 200433, P. R. China
Ming Hsiung
South China Normal University
Guangzhou, 510631, P. R. China
Abstract
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
