逆转箭头

设元胞自动机（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著名的“生命游戏”，则可逆化后也保持通用性。

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容