论文标题
Oracles可以教给我们关于生命的最终命运的什么？
What can oracles teach us about the ultimate fate of life?
论文作者
论文摘要
我们解决了有关康威生活的两个长期开放问题，即二维蜂窝自动机。我们解决了广义的祖父问题：对于所有$ n \ geq 0 $，存在具有$ n $ th前任的配置，但没有$（n+1）$ st One。我们还解决了（一种解释）独特的父亲问题：存在有限的稳定配置，其中包含一个有限的副标题，除了本身以外，没有前身模式。特别是这给出了一个难以置信的静物的第一个例子。新的关键概念是具有独特的预图链的时空周期性配置（琼脂）。我们表明，该属性是半确定的，并使用SAT求解器找到了此类琼脂的示例。 我们关于生活游戏拓扑动态的结果如下：它永远不会达到其极限设置；它在极限设置上的动态是链式的，特别是它不是拓扑传递的，并且没有密集的周期性点；并且其极限集的空间动力学是非sofic的，并且不接受基本方向上的套管半径（尤其不是块状）。我们的可计算性结果是，生命的可及性问题以及其极限集的语言是pspace-hard。
We settle two long-standing open problems about Conway's Life, a two-dimensional cellular automaton. We solve the Generalized grandfather problem: for all $n \geq 0$, there exists a configuration that has an $n$th predecessor but not an $(n+1)$st one. We also solve (one interpretation of) the Unique father problem: there exists a finite stable configuration that contains a finite subpattern that has no predecessor patterns except itself. In particular this gives the first example of an unsynthetizable still life. The new key concept is that of a spatiotemporally periodic configuration (agar) which has a unique chain of preimages; we show that this property is semidecidable, and find examples of such agars using a SAT solver. Our results about the topological dynamics of Game of Life are as follows: it never reaches its limit set; its dynamics on its limit set is chain-wandering, in particular it is not topologically transitive and does not have dense periodic points; and the spatial dynamics of its limit set is non-sofic, and does not admit a sublinear gluing radius in the cardinal directions (in particular it is not block-gluing). Our computability results are that Game of Life's reachability problem, as well as the language of its limit set, are PSPACE-hard.
