论文标题
将任意布尔电路嵌入真菌自动机中
Embedding arbitrary Boolean circuits into fungal automata
论文作者
论文摘要
真菌自动机是Bak，Tang和Wiesenfeld的二维砂型自动机的一种变体（Phys。Rev.Lett。1987）。在每个步骤中，浇灌单元仅根据特定的更新序列选择的某些邻居发出晶粒。我们展示了如何将任何布尔电路嵌入具有更新序列$ hv $的真菌自动机的初始配置中。特别是，我们给出了一个构造函数，鉴于电路的描述$ b $，在$ o（\ log | b |）$ space中嵌入配置的有限支持中计算所有单元格的状态。结果，带有更新序列$ hv $的真菌自动机的预测问题是$ \ mathsf {p} $ - 完成。这解决了Goles等人的开放问题。 （Phys。Lett。A，2020）。
Fungal automata are a variation of the two-dimensional sandpile automaton of Bak, Tang, and Wiesenfeld (Phys. Rev. Lett. 1987). In each step toppling cells emit grains only to some of their neighbors chosen according to a specific update sequence. We show how to embed any Boolean circuit into the initial configuration of a fungal automaton with update sequence $HV$. In particular we give a constructor that, given the description $B$ of a circuit, computes the states of all cells in the finite support of the embedding configuration in $O(\log |B|)$ space. As a consequence the prediction problem for fungal automata with update sequence $HV$ is $\mathsf{P}$-complete. This solves an open problem of Goles et al. (Phys. Lett. A, 2020).
