倒过来的自动机

陈凯

一只兔子在自家菜园的田地中划出钻石状的格子，在其中种上胡萝卜，要知道，这是一只有强迫症的兔子，它所做的事情，都遵循一种叫做对称的规则。它在第一行的正中间种上一棵胡萝卜，然后从第二行开始，兔子站在格子中望向前一行的左前方和右前方，若所种的胡萝卜排列恰巧对称，那它就空出这块地方什么也不种，要是望出去不对称，就种下胡萝卜，其后的每一行也都是这样。照这个规则一直种胡萝卜的话，得到的图案如图1所示，看上去很熟悉，不是吗？

在往期的文章里，我们已经介绍了初等元胞自动机，并且在矩形网格中通过初等元胞自动机第90号规则得到了谢尔宾斯基三角形图案。现在，我们在钻石状网格中用更简单的规则得到了同样的图案，假如换成六角形形状的网格，结果仍然是相同的，这可真是奇妙。钻石状或六角形网格中的谢尔宾斯基三角形的生成规则可简叙为：00生成0；11生成0；10生成1；01生成1。

值得注意的是，在六角形网格中，我们可以任意选择图中所示的x、y、z这三个方向按以上规则来生成谢尔宾斯基三角形（如图2）。现在的问题是，能否选择a、b、c这三个方向，来“倒”着生成谢尔宾斯基三角形呢？换而言之，就是要寻找到某个规则，使二进制序列“0111111110”变化为“010101010”，同样的规则再使得“010101010”变化为“01100110”，进而为“0100010”、“011110”、“01010”、“0110”、“010”呢（如图3）？

把图形稍微旋转一点角度得到字符序列如图4，这样看起来就更清楚一些。

乍一看似乎难以找到这样的规则，因为逆向的谢尔宾斯基三角形的变化方式似乎具有很大的不确定性。例如，从第一行到第二行的变化中，我们既不能规定11生成1，也不能规定11生成0。实际上，同步更新的自动机无法胜任此工作，但或许我们可以尝试使用异步的自动机来生成谢尔宾斯基三角形。什么是异步自动机呢？下面演示的是字符序列中第二行前四个字符的生成过程，相信读者看了以后会有所领悟。

第一步：01生成1。

第二步：11生成0。

第三步：01生成1。

可以换一些更长的数字序列，比如“011111111111111110”，观察运用异步变化规则，能否顺利产生出谢尔宾斯基三角形。验证工作借助微软的Excel电子表格就能够实现，想到怎么做了吗？（答案在本期找）