论文标题
四个头大于三头
Four heads are better than three
论文作者
论文摘要
我们构建具有有限的扭转的有限生成的扭转组，其单词问题是与给定的递归枚举集合的词相等的（尤其是正相等的）。这些组可以被解释为有限状态机器的组或拓扑完整组的亚组，在其他扭转组上的有效乘坐。我们定义了一组自然数的递归理论特性，称为无罪性。它粗略地指出，图灵机可以枚举数字，以便每台图灵机偶尔会（通过停止）是否在集合中猜测，即使给出了集合前缀的甲骨文。我们证明存在不可递归的枚举集。通过[SaloandTörmä，2017]结合这些结构并略微适应了结果，我们得到的是，四头群体行走的有限状态自动机比包含整数副本的三头自动机的次要更严格地定义，从而确认了[salo andtörmä，2017年]的猜测。这些是第一个组的第一个示例，其中四个头比三个更好，它们表明有限头部层次结构的最大高度确实是四个。
We construct recursively-presented finitely-generated torsion groups which have bounded torsion and whose word problem is conjunctive equivalent (in particular positive and Turing equivalent) to a given recursively enumerable set. These groups can be interpreted as groups of finite state machines or as subgroups of topological full groups, on effective subshifts over other torsion groups. We define a recursion-theoretic property of a set of natural numbers, called impredictability. It roughly states that a Turing machine can enumerate numbers such that every Turing machine occasionally incorrectly guesses (by either halting or not) whether they are in the set, even given an oracle for a prefix of the set. We prove that impredictable recursively enumerable sets exist. Combining these constructions and slightly adapting a result of [Salo and Törmä, 2017], we obtain that four-headed group-walking finite-state automata can define strictly more subshifts than three-headed automata on a group containing a copy of the integers, confirming a conjecture of [Salo and Törmä, 2017]. These are the first examples of groups where four heads are better than three, and they show the maximal height of a finite head hierarchy is indeed four.
