标题： 同胚移位的块粘合类的不可判定性 显示英文标题

标题： Undecidability of the block gluing classes of homshifts

摘要： 一个同态移位是一个$d$维的有限型移位，它作为从网格图$\mathbb Z^d$到有限连通无向图$G$的图同态空间而出现。 虽然已知有限型移位被不可判定的沼泽所困扰，但同态移位似乎表现得更好，并且曾有希望所有同态移位的性质都是可判定的。 在本文中，我们基于 Gangloff、Hellouin de Menibus 和 Oprocha（arxiv:2211.04075）的工作，证明了更精细的混合性质对于一般多维有限型移位的不可判定性原因完全不同。 受 Gao、Jackson、Krohne 和 Seward（arxiv:1803.03872）工作的启发以及基本的代数拓扑，我们将 Gangloff、Hellouin de Menibus 和 Oprocha 引入的正方形覆盖从拓扑角度进行解释。 利用这种解释，我们证明了判断一个同态移位是否为$\Theta(n)$块粘合是不可判定的，这是通过将这个问题与有限表示群的有限性问题相关联来证明的。 显示英文摘要

摘要： A homshift is a $d$-dimensional shift of finite type which arises as the space of graph homomorphisms from the grid graph $\mathbb Z^d$ to a finite connected undirected graph $G$. While shifts of finite type are known to be mired by the swamp of undecidability, homshifts seem to be better behaved and there was hope that all the properties of homshifts are decidable. In this paper we build on the work by Gangloff, Hellouin de Menibus and Oprocha (arxiv:2211.04075) to show that finer mixing properties are undecidable for reasons completely different than the ones used to prove undecidability for general multidimensional shifts of finite type. Inspired by the work of Gao, Jackson, Krohne and Seward (arxiv:1803.03872) and elementary algebraic topology, we interpret the square cover introduced by Gangloff, Hellouin de Menibus and Oprocha topologically. Using this interpretation, we prove that it is undecidable whether a homshift is $\Theta(n)$-block gluing or not, by relating this problem to the one of finiteness for finitely presented groups.