3

From this paper.

"A (bi-directional, deterministic) cellular automaton is a triplet $A = (S;N;\delta)$, where $S$ is an non-empty state set, $N$ is the neighborhood system, and $\delta$ is the local transition function (rule). This function defines the rule of calculating the cell’s state at $t +1$ time step, given the states of the neighborhood cells at previous time step $t$"

I haven't found other "bidirectional" CA via Google, so I wonder what does the term say about this automaton's properties. Does it mean that the state $t+1$ can be used to find out the state t?

Mahdi Khosravi
  • 3,989
andandandand
  • 435

2 Answers2

2

The term is definitely an oddity. In the specific case $S=\mathbb Z$, it might refer to the fact that the neighborhood is two-sided, typically $N=\{-1,0,1\}$ instead of $N=\{0,1,2\}$. My advice is to forget this altogether.

Did
  • 279,727
  • I don't understand your neighborhood notation. Also, what do you mean by "two-sided", 2D neighborhood instead of 1D? – andandandand Jul 20 '13 at 18:50
  • "Two-sided" refers to the case where both states at $x-1$ and $x+1$ (and the third state at $x$) have an effect on the next state at $x$. Say, what kind of literature on automata are you familiar with? – Did Jul 20 '13 at 20:36
  • Am I? Looks very much 1D to me but since I am only able to do an old kind of science, obviously I cannot compete with NKS, can I? – Did Jul 20 '13 at 21:07
  • Well, no... now it's clear that I'm wrong at calling that 2D. Thanks. I guess that N = {-1,0,1} means the 1D neighbors at "left, self, right" and that N = {0, 1, 2} means "self, right, right+right". Right? (Kudos for the attitude, old man) – andandandand Jul 21 '13 at 02:56
2

I think that the notion is commonly called a reversible cellular automaton. We say that a cellular automaton $f:A^{\mathbb{Z}^{d}}\rightarrow A^{\mathbb{Z}^{d}}$ (i.e. a function defined by a local transition rule) is called reversible if there is a cellular automaton $g:A^{\mathbb{Z}^{d}}\rightarrow A^{\mathbb{Z}^{d}}$ where $f\circ g$ and $g\circ f$ are both the identity mapping. We have the following characterization of reversible cellular automata.

$\mathbf{Theorem}$ Let $f:A^{\mathbb{Z}^{d}}\rightarrow A^{\mathbb{Z}^{d}}$ be a cellular automaton. Then following are equivalent.

  1. $f$ is reversible.

  2. $f$ is bijective.

  3. $f$ is injective.

In other words, every injective cellular automaton is bijective and its inverse is also a cellular automaton. See this paper for more details on reversible cellular automata.

I don't think the authors were referring to bi-dimensional cellular automata since the author defines cellular automata for all dimensions, and I don't think the authors were referring to cellular automata mapping $\mathbb{N}^{d}$ to $\mathbb{N}^{d}$ since we are dealing with multiple dimensions. It seems like the authors were putting words in parentheses rather carelessly that time.

quid
  • 42,135
Joseph Van Name
  • 335
  • Can I find out the state t, only knowing the state t+1, in a reversible cellular automaton? – andandandand Jul 20 '13 at 21:24
  • If you know in advance that the cellular automaton is reversible, then there is clearly an algorithm that eventually produces the inverse cellular automaton and in this case you can calculate state $t$ from state $t+1$. After all, all you have to do is go through all the possible cellular automata rules and see which one happens to be the inverse. On the other hand, it is hard to tell whether a cellular automata is reversible or not. The problem of determining whether a cellular automata is reversible is decidable in the one-dimensional case, but it is undecidable for dimensions 2 and above. –  Jul 20 '13 at 21:32
  • if CA reversibility is undecidable in 2 dimensions would it make sense for the authors of the paper to call their automaton "reversible"? (They don't call it reversible and the automaton is designed to work in images) I'm thinking that the "bidirectional" description of the automaton is unfounded. – andandandand Jul 21 '13 at 02:44