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).
翻译：Fungal Automata 是Bak、Tang和Wiesenfeld(Phys. Rev. Lett. 1987年)二维沙丘自动图的变体。 在每步中, 打印单元格只向根据特定更新序列选择的一些邻居发放粒子。 我们展示了如何将任何布林电路嵌入真藻自动图的初始配置中, 其更新序列为$HV$。 特别是, 我们给出了一个构造器, 根据电路的描述 $B$, 计算出所有单元格在 $O( log. ⁇ B ⁇ ) 空间嵌入配置的有限支持范围内的状态。 因此, 更新序列 $HV$ 的真鸟自动图的预测问题就是$\mathsf{P} $- 完成 。 这解决了 Goles et al. (Phys. Lett. A, 2020) 的公开问题 。
相关内容
微信扫码咨询专知VIP会员