# reversible cellular automata

Let's suppose a cellular automaton has a value $b(r,t)$ belongs to $Q$ at site $r$ and time $t$, where $Q$ is the set of possible states at each site. Let $N(r, t)$ be the values of the states of all the sites in some (e.g., Von Neumann or Moore) neighborhood of $r$ at time $t$, taken in some canonical order.

The cellular automaton rule is then $$b(r, t + 1) = F(N(r, t))$$ where $F$ is the update function.

Let us suppose that $Q = \{0, 1\}$ so that we have a bit at each site. One way to construct reversible cellular automata (RCA) is to look at rules of the form $b(r, t + 1) = F(N(r, t)) \text{ xor } b(r, t − 1)$

To see why this is reversible, how to solve for $b(r, t −1)$ in terms of $b(r, t)$ and $b(r +1, t)$. Does it mean that this obeys a condition even stronger than reversibility?

One apparent disadvantage of this approach seems to be that computation of $b(r, t+1)$ requires knowledge of the state at time $t−1$ in addition to that at time $t$. Is there way to fix this problem by adding extra state at a site so that the state at time $t + 1$ depends only on that at time $t$? Are there other functions besides $\text{xor}$ that could be used to create RCA in the above fashion for $Q = \{0, 1\}$?

Let's assume that we have $$b(r,t+1) = P(\ F(N(r,t),\ b(r,t-1)\ ) .$$ What you need for this to work is that the function $P(x,\cdot)$ is reversible for fixed $x$. If you have a bit as an input, there are only two reversible functions, the identity and the NOT function. For the cellular automaton not to be trivial, $P(0,\cdot)$ should not be the same as $P(1,\cdot)$. This means that there are two possible functions that work: $$b(r,t+1)=F(N(r,t)) \oplus b(r,t−1)$$ and $$b(r,t+1)=F(N(r,t)) \oplus b(r,t−1) \oplus 1,$$ and it is easy to see that by replacing $F$ by $F\oplus 1$, both of these possibilities can be put into the form given by the OP.
To make the CA depend only on the state at time $t$ and not the states at both $t-1$ and $t$, all you need do is make a new CA where the state at time $t$ of the new CA comprises the state of the old CA at both times $t-1$ and $t$.