The complexity of cellular automata is traditionally measured by their computational capacity. However, it is difficult to choose a challenging set of computational tasks suitable for the parallel nature of such systems. We study the ability of automata to emulate one another, and we use this notion to define such a set of naturally emerging tasks. We present the results for elementary cellular automata, although the core ideas can be extended to other computational systems. We compute a graph showing which elementary cellular automata can be emulated by which and show that certain chaotic automata are the only ones that cannot emulate any automata non-trivially. Finally, we use the emulation notion to suggest a novel definition of chaos that we believe is suitable for discrete computational systems. We believe our work can help design parallel computational systems that are Turing-complete and also computationally efficient.
翻译：细胞自动数据的复杂性历来以其计算能力来衡量。 但是, 很难选择一套适合这些系统平行性质的具有挑战性的计算任务。 我们研究自动数据是否有能力相互仿效, 我们用这个概念来定义这组自然产生的任务。 我们展示了基本细胞自动数据的结果, 尽管核心想法可以推广到其他计算系统。 我们计算了一个图表, 显示哪些基本细胞自动数据可以被复制, 并显示某些混乱的自动数据是唯一无法不重复地模仿任何自动数据的方法。 最后, 我们使用模拟概念来提出一种我们认为适合离散计算系统的混乱的新定义。 我们相信我们的工作可以帮助设计平行的计算系统, 这些系统是图灵的, 并且计算效率也很高 。
相关内容
微信扫码咨询专知VIP会员