EUVIMEDEUVIMED entdecken
Crossref

A General Result Relating Totalistic Cellular Automata and Self-Referential Sentences

Shuwen Wu, Ming Hsiung

Complex Systems · 15.03.2026 · 35 (1) · 39-61

DOI: 10.25088/complexsystems.35.1.39 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Complex Systems, online erschienen am 15.03.2026. Verfasst von Shuwen Wu und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Wu, S., & Hsiung, M. (2026). A General Result Relating Totalistic Cellular Automata and Self-Referential Sentences. Complex Systems, 35(1), 39-61. https://doi.org/10.25088/complexsystems.35.1.39

Vancouver

Wu S, Hsiung M. A General Result Relating Totalistic Cellular Automata and Self-Referential Sentences. Complex Systems. 2026;35(1):39-61. doi:10.25088/complexsystems.35.1.39

BibTeX
@article{Wu2026,
  author = {Wu, Shuwen and Hsiung, Ming},
  title = {A General Result Relating Totalistic Cellular Automata and Self-Referential Sentences},
  journal = {Complex Systems},
  year = {2026},
  volume = {35},
  number = {1},
  pages = {39--61},
  doi = {10.25088/complexsystems.35.1.39}
}
Kostenlos starten →