论文
arXiv
CellularAutomata
中文标题
基于元胞自动机的局部有限群可逆性刻画
English Title
A Reversibility Characterization of Locally Finite Groups by Cellular Automata
Jiang Yang
发布时间
2026/6/29 16:35:57
来源类型
preprint
语言
en
摘要
中文对照

对于有限字母表上的元胞自动机,双射性已蕴含可逆性;而在无限字母表上,该蕴含关系可能不成立。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 获得肯定回答,且负向结论无需周期性假设。

English Original

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.

我的阅读记录

正在加载阅读记录…

元数据
arXiv2606.29958v1
来源arXiv
类型论文
抽取状态raw
关键词
CellularAutomata
math.GR
math.GN