论文标题
可逆的蜂窝自动机和单头机器的结合性
Conjugacy of reversible cellular automata and one-head machines
论文作者
论文摘要
我们表明，可逆细胞自动机的结合性是不可抑制的，无论是由另一个可逆的细胞自动机还是由一般同构形态性执行。这引起了一个有限生成的群体的新家族，这些群体具有不可抑制的共轭问题，其描述可以说不涉及任何类型的计算。对于许多子缩合的自多态群，以及Cantor集的异步传感器和同构群的组，我们的结果意味着存在两个元素，因此每个包含两者的有限生成的亚组都有不可抑制的共偶有性问题。我们说，这些群体中的共轭最终在本地是不可决定的。我们还证明，Brin-Thompson集团$ 2V $和一组可逆的Turing Machines存在不可抗解的共轭问题，并证明了自动形态群体的问题和每一个完整转变的拓扑完整组最终都是本地Co-NP完整的。
We show that conjugacy of reversible cellular automata is undecidable, whether the conjugacy is to be performed by another reversible cellular automaton or by a general homeomorphism. This gives rise to a new family of finitely-generated groups with undecidable conjugacy problems, whose descriptions arguably do not involve any type of computation. For many automorphism groups of subshifts, as well as the group of asynchronous transducers and the homeomorphism group of the Cantor set, our result implies the existence of two elements such that every finitely-generated subgroup containing both has undecidable conjugacy problem. We say that conjugacy in these groups is eventually locally undecidable. We also prove that the Brin-Thompson group $2V$ and groups of reversible Turing machines have undecidable conjugacy problems, and show that the word problems of the automorphism group and the topological full group of every full shift are eventually locally co-NP-complete.
