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.

Once you consider reversible cellular automata having more than two states, there are lots of possibilities for rules of this type.

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.