论文标题
明确解决凯奇问题的蜂窝自动机规则172
Explicit solution of the Cauchy problem for cellular automaton rule 172
论文作者
论文摘要
细胞自动机（CA）是部分偏微分方程（PDE）的完全离散替代方案。对于PDE，人们经常考虑Cauchy问题或初始值问题：找到满足给定初始条件的PDE的解决方案。对于第一阶的许多PDE，如果在$ t = 0 $中已知解决方案，则可以在$ t> 0 $的情况下找到解决方案的明确公式。 CA可以实现类似的事情吗？我们证明，在某些情况下，以基本CA规则172为例，这确实是可能的。假设所有单元的状态在$ n = 0 $上都知道，我们在规则172的$ n $迭代后为给定单元的状态提供了明确的表达。然后，我们证明此表达式（“ CA的解决方案”）可用于在$ n $迭代后获得给定单元的期望值，前提是初始条件是从Bernoulli分布绘制的。这可以针对有限和无限晶格进行，因此为研究CA中的有限尺寸效应提供了有趣的测试用例。
Cellular automata (CA) are fully discrete alternatives to partial differential equations (PDE). For PDEs, one often considers the Cauchy problem, or initial value problem: find the solution of the PDE satisfying a given initial condition. For many PDEs of the first order in time, it is possible to find explicit formulae for the solution at the time $t>0$ if the solution is known at $t=0$. Can something similar be achieved for CA? We demonstrate that this is indeed possible in some cases, using elementary CA rule 172 as an example. We derive an explicit expression for the state of a given cell after $n$ iteration of the rule 172, assuming that states of all cells are known at $n=0$. We then show that this expression ("solution of the CA") can be used to obtain an expected value of a given cell after $n$ iterations, provided that the initial condition is drawn from a Bernoulli distribution. This can be done for both finite and infinite lattices, thus providing an interesting test case for investigating finite size effects in CA.
