Volume 30, Issue 2 (2021)

Formal Logic of Cellular Automata

Sukanta Das
Department of Information Technology
Indian Institute of Engineering Science and Technology
Shibpur, 711103, India
sukanta@it.iiests.ac.in
Mihir K. Chakraborty
School of Cognitive Science
Jadavpur University, Kolkata, 700032, India
mihirc4@gmail.com

Abstract

This paper develops a formal logic, named $L_{\mathrm{CA}}$, targeting modeling of one-dimensional binary cellular automata. We first develop the syntax of $L_{\mathrm{CA}}$, then give semantics to $L_{\mathrm{CA}}$ in the domain of all binary strings. Then the elementary cellular automata and four-neighborhood binary cellular automata are shown as models of the logic. These instances point out that there are other models of $L_{\mathrm{CA}}$. Finally it is proved that any one-dimensional binary cellular automaton is a model of the proposed logic.

Keywords: cellular automata; formal logic; spatial rule; temporal rules; evolution; derivation  

Cite this publication as:
S. Das and M. K. Chakraborty, “Formal Logic of Cellular Automata,” Complex Systems, 30(2), 2021 pp. 187–203.
https://doi.org/10.25088/ComplexSystems.30.2.187