论文标题
三元细胞自动机和三元密度分类问题的探索
Explorations of ternary cellular automata and ternary density classification problems
论文作者
论文摘要
虽然已经详细研究了二进制最近的邻居地窖自动机（CA），但从许多不同的角度进行了研究，但对于三元（三态）CA规则不能说相同的话。我们介绍了我们对三元规则庞大空间的一小部分探索的一些结果，即具有添加剂不变的规则。我们首先用四个不同的添加剂不变性列举规则，然后我们研究是否可以使用任何一个规则来构建广义密度分类问题（DCP）的两组解决方案。我们表明，使用一对三元规则，第一个规则是全面的，而第二个状态则可以降低第二个规则。我们提出的另一个版本的DCP类似的负面结果：对称间隔DCP。最后，我们展示了一对规则的示例，该规则求解了至少一个零的初始配置的非对称间隔DCP。
While binary nearest-neighbour cellar automata (CA) have been studied in detail and from many different angles, the same cannot be said about ternary (three-state) CA rules. We present some results of our explorations of a small subset of the vast space of ternary rules, namely rules possessing additive invariants. We first enumerate rules with four different additive invariants, and then we investigate if any of them could be used to construct a two-rule solution of generalized density classification problem (DCP). We show that neither simple nor absolute classification is possible with a pair of ternary rules where the first rule is all-conserving and the second one is reducible to two states. Similar negative result holds for another version of DCP we propose: symmetric interval-wise DCP. Finally we show an example of a pair of rules which solve non-symmetric interval-wise DCP for initial configurations containing at least one zero.
