Convergence of Asynchronous Cellular Automata: Does Size Matter?
Biswanath Sethi, Souvik Roy and Sukanta Das
This paper studies convergence of elementary cellular automata to a fixed point under fully asynchronous update. We study four possible cases– convergence of automata for any size and for the sizes that are multiple of 2, multiple of 3 and multiple of 4 only. We identify 146 cellular automata rules that converge for any size. Further, we also identify 21 and 6 rules which converge when the sizes are multiple of 2 and 3 respectively. However, we do not find any convergent rule when the sizes are multiple of 4 only. In this work we study cellular automata in fully asynchronous update as absorbing Markov chains.
Keywords: Asynchronous cellular automata (ACAs), Markov chains, convergence, fixed point, absorbing state