# Can Sutner's (1991) quadratic algorithm for testing reversibility of Cellular Automata be applied to 1-D CA with even sized neighborhoods?

Admittedly I haven't fully wrapped my head around the paper yet, but I'm curious if this algorithm can be adapted to say, a one dimensional cellular automata with two states, and an even sized neighborhood, there are references in the paper to "neighbor radius" and neighborhood size of 2r+1. But the reversibility of neighborhoods of size 2, 4, and 6, for example, are also of interest to me.

A link to the paper is here: https://wpmedia.wolfram.com/uploads/sites/13/2018/02/05-1-3.pdf

I know of one other algorithm, from Amoroso and Patt (1972) that seems to be generally applicable to even numbered neighborhoods from a brief overview of the paper, but I can't seem to find a time complexity analysis of it within or without. Although, other papers seem to imply it is worse than quadratic. (And I have been less able to understand the paper)

## 1 Answer

A CA with neighborhood size $$s$$ can be trivially emulated by a CA with any neighborhood size $$s' > s$$ that just ignores the extra cells in the neighborhood. So if the method works for CA with odd neighborhood size, then it can also be applied to CA with an even neighborhood size simply by adding one cell to the neighborhood to make its size odd.

That said, based on an (admittedly very quick) skim of the paper, I suspect that this trick is actually unnecessary here, and that the method described in the paper can in fact be directly applied to even neighborhood sizes with few if any substantial changes. In particular, I suspect that nothing really breaks if you let $$2r$$ take any positive integer value, not just even values.

• Ah, that is a very good point about even neighborhoods just being even neighborhoods in which you don't change behavior based on one end value. Feb 17, 2023 at 17:12