对于有限字母表上的元胞自动机,双射性已蕴含可逆性;而在无限字母表上,该蕴含关系可能不成立。Ceccherini-Silberstein 与 Coornaert 在《Cellular Automata and Groups》一书中将周期情形下剩余的障碍列为开放问题 2(Open Problem 2)。本文给出了一个精确的群论刻画:一个群 $G$ 是局部有限群,当且仅当对任意字母表 $A$,所有双射元胞自动机 $A^G \to A^G$ 均为可逆元胞自动机。等价地,若 $G$ 不是局部有限群,则对任意无限字母表 $A$,均存在一个双射元胞自动机 $A^G \to A^G$,其逆映射不是元胞自动机。该反例已在可数字母表上实现;其局部规则包含秩轨道(rank track)、方向轨道(direction track)与二进制数据轨道(binary data track);前向映射沿任意长度的有限有向链呈三角形式,因此其逆映射虽可逐点定义,却不具有统一的有限记忆。由此,开放问题 2 获得肯定回答,且负向结论无需周期性假设。
For cellular automata over finite alphabets, bijectivity already implies reversibility. Over infinite alphabets this implication may fail, and the remaining obstruction in the periodic case was recorded by Ceccherini-Silberstein and Coornaert as Open Problem 2 in \emph{Cellular Automata and Groups}. We prove an exact group-theoretic characterization. A group $G$ is locally finite if and only if, over every alphabet, every bijective cellular automaton $A^G\to A^G$ is reversible. Equivalently, if $G$ is not locally finite, then for every infinite alphabet $A$ there exists a bijective cellular automaton $A^G\to A^G$ whose inverse is not a cellular automaton. The counterexample is already obtained on a countable alphabet. Its local rule has a rank track, a direction track and a binary data track; the forward map is triangular along finite directed chains of arbitrary length, so its inverse is defined pointwise but has no uniform finite memory. As a consequence, Open Problem 2 has an affirmative answer, and the periodicity hypothesis is unnecessary for the negative direction.