Number Conservation Property of Elementary Cellular Automata under Asynchronous Update
Raju Hazari*
Sukanta Das†
Department of Information Technology
Bengal Engineering and Science University, Shibpur
Howrah, West Bengal, India 711103
*hazariraju0201@gmail.com
†sukanta@it.becs.ac.in (corresponding author)
Abstract
This paper studies the number conservation property of elementary cellular automata (ECAs) under asynchronous update. In asynchronous update, any number of cells can be updated in each time step. It is, however, shown in the beginning of the study that no elementary cellular automaton (ECA), in general, can be claimed as number conserving under asynchronous update. Our goal was to search for some ECAs that conserve the number of 1s and 0s of any initial configuration for at least one update pattern. As a result of this search, we get a set of 64 ECAs. Each of these ECAs can sometimes show the number conservation property under asynchronous update. The probability of showing the number conservation property of these 64 ECAs may be small, but it is nonzero. However, in the update of these number-conserving ECAs, only passive transitions may be observed. We proceed by searching some ECAs (from the set of 64 ECAs) that show the number conservation property even with active transitions against some initial configurations. Here we identify 49 ECAs that obey this criterion. We finally extract nine ECAs from these 49 ECAs that can show the number conservation property with only active transitions against each of the possible initial configurations except for two homogeneous configurations: one with cell state 0 and the other with cell state 1. We conclude our study after presenting an asynchronous update scheme for these number-conserving ECAs.
