逆转箭头

2020-02-23 本文已影响0人十酒三

设元胞自动机（CA）运行第i步的位形为 $C_{i}$ ，若位形中只包含0和1两种元胞，则任一迭代规则 $C_{i+1} ：=\Phi （C_{i}）$ 都可以改成可逆的元胞自动机规则，方法如下：

$C_{i+1} ：=\Phi （C_{i}） XOR （C_{i-1}）$

式中XOR为逐位异或函数，表示对两个位形中逐个位元做异或操作。

由异或基本性质 $A=(A xor B) xor B$ 容易推得上述规则存在逆变换

$C_{i-1} ：=\Phi （C_{i}） XOR （C_{i+1}） \Rightarrow C_{i-2} ：=\Phi （C_{i-1}） XOR （C_{i}）$

从而只要存储相邻两步的位形即可任意变换演化的方向（“时间箭头”）。

若原来的CA规则是通用的，例如Conway著名的“生命游戏”，则可逆化后也保持通用性。