Reversibility of additive CA as function of cylinder size

Valeriy Bulitko

Published 2014-08-07Version 1

Additive CA on a cylinder of size $n$ can be represented by 01-string $V$ of length $n$ which is its rule. We study a problem: a class $S$ of rules given, for any $V\in S$ describe all sizes $n', n'>n,$ of cylinders such that extension of $V$ by zeros to length $n'$ represents reversible additive CA on a cylinder of size $n'$. Since all extensions of $V$ have the same collection of positions of units, it is convenient to say about classes of collections of positions instead of classes of rules. A criterion of reversibility is proven. The problem is completely solved for infinite class of "block collections", i.e. $\{(0,1,\dots,h)|h\in\mathbb Z^+\}$. Results obtained for "exponential collections" $\{(1,2,4,\dots,2^h)|h\in\mathbb Z^+\}$ essentially reduce the complexity of the problem for this class. Ways to transfer the results on other classes of rules/collections are described. A conjecture is formulated for class $\{(0,1,2^m)|m\in\mathbb Z^+\}$.