远程细胞自动机

(本文最初发表于NKS论坛.)

NKS 2004会议我做了我现在传统的“实时计算机实验”。这次我选择的话题是在会议前的小课程上有人问的一个问题:增加细胞自动机的“范围”对它的行为有很大的影响吗?

我决定研究这个问题的一个简单版本。

在普通的r=1元胞自动机中,特定细胞的新颜色依赖于偏移量为- 1,0,1的细胞先前的颜色。我当时问的问题是:如果抵消更大会发生什么?

在最简单的非平凡细胞自动机中,一个细胞的颜色取决于两个细胞之前的颜色。在普通的短程情况下,单元格的偏移量为- 1,1。但是现在我们可以问如果它们有-1 m的偏移会发生什么。

很容易看到这个内置的CellularAutomaton函数Mathematica.你只是使用CellularAutomaton{n, k, {{-1}, {m}}, init, t,在那里n规则编号是,和k是颜色的数量。(偏移量放在子列表中,以区别于多维范围规范。)

当k=2种颜色时,有16个这样的规则。下面的例子显示了通常的短距离情况下的偏移量- 1,1。这里最复杂的模式是嵌套模式,对应于基本规则90(这里是规则6)。


下面的图像显示了偏移- 1,2(在左边)和- 1,3(在右边)的情况。图像是扭曲的,但基本上与- 1,1的情况完全相同。



这种情况发生并不奇怪。在通常的- 1,1情况下,已经有两个独立的子格:偶数阶上的偶数格,偶数阶上的奇数格。在-1 m的情况下,有m+1个子格,但每一个子格都有完全相同的依赖结构在-1的情况下,只是逐渐移动。(在规则14的棋盘模式中,这一点尤为明显。)

那么三细胞依赖的情况呢?偏移量- 1,0,1 (k=2颜色)给出通常的256个基本元胞自动机,如上图所示。现在第二个和第三个例子分别给出了- 1,0,2和- 1,0,3种情况。




发生的事情相当有趣。当m=2或m=3时,许多- 1,0,m规则给出的模式与m=1时类似。尽管有很多细节上的差异。当m=1时(比如22、41和54),一些在某种程度上“最初很复杂”的规则,在m=2时变得更明显复杂。一个例子是规则22,对于m=1,当有一个黑色的初始单元格时,它产生一个嵌套的模式,但在某些较大的初始条件下产生一个更复杂的模式(参见NKS的书,263页).

不依赖于所有三个邻居的规则也会显示简单的移动,就像-1,m的情况一样。加法规则,如90和150,总是为任何偏移量提供嵌套模式。规则90的那些只是移位了。但是对于第150条规则,它们有逐渐不同的形式(见下面的例子)。人们仍然可以使用NKS书中的程序来计算它们的分形维数,955页;m=1到5的结果为{1.69,1.727,1.736,1.745}。






看看规则30随着偏移量的增加会发生什么是很有趣的(见下面的例子)。确实有一些令人惊讶的地方。特别地,对于某些m(特别是4的倍数),规则30的模式似乎变得粗糙得多。一开始,它可能看起来像它的中心列重复。但事实似乎并非如此。











在NKS 2004,在观众的帮助下,我花了一个小时研究所有这些。很难停下来……我从会议中生成的原始笔记本有48兆。这里我只附上了一个小笔记本(Inputs.nb)的输入。

关于远程细胞自动机,有很多很多显而易见的东西需要研究。是什么使特定的偏移导致更粗糙的模式?是什么决定了它们的粗糙程度?不同补偿的总体增长率是多少?如果使用不同的补偿集会发生什么?(-m, 0, m只是给出了- 1,0,1模式的延伸版本,但是其他的呢?)更重要的是,如果一个人在时间和空间上使用补偿会发生什么(比较437页) ?也有很多关于特定规则的有趣的具体问题。比如对于m>1, 121法则的右边边是怎么回事?






发布:新型科学

Baidu