文摘

我们提出一个新颖的,信息化的初级细胞自动机分类。提出的分类方案避免了问题隔离是否实际上是固有的复杂性动态规则,或者仅仅作为一个产品出现的复杂的初始状态。传递熵变化处理细胞自动机把256分成三个基本规则信息类基于对初始条件的敏感性。这些类组成一个层次结构,粗粒度的转换中观察到基本规则主要发生在每个信息化类或更很少,沿着层次结构。

1。介绍

复杂性是很容易识别,但很难量化。试图将动力系统的复杂性因此到目前为止主要依靠定性标准。一个很好的例子就是细胞自动机(CA)的分类规则。CA是离散动力系统的复杂性科学的兴趣,因为他们捕获许多物理系统的两个关键特性:他们进化的根据当地的统一规则,甚至可以表现出丰富的紧急行为从非常简单的规则1]。因此研究CA的动力学可以提供洞察的困难问题是如何自然世界显得如此复杂,因为已知的物理定律都是本地的,(相对)简单。然而,在CA规则,有趣的紧急行为是例外而不是规则。这产生了广泛兴趣了解如何隔离这些当地规则,生成丰富的,紧急的行为,例如,滑翔机和颗粒,计算普遍性,从那些不等等(康威的开创性论文生命的游戏cf。2]。第一轮廓的普遍性证明二维游戏生活中可以找到的3,4]。证明nonelementary的普遍性,一维细胞自动机在[而不是5,6]。著名的证据的基本规则的普遍性110 cf。7])。出现并发症,输出一个CA规则的复杂性往往是高度依赖于输入的状态。这很难解决紧急的行为是一个产品的初始状态的内在的规则。这导致了歧义的分类的内在复杂性CA规则作为一个必须与一个特定的初始状态不可避免地执行一个CA规则为了表达其复杂性(或缺乏)。

第一个尝试分类CA规则是由Wolfram的分类提供初级细胞自动机(ECA) (8]。ECA是一些最简单的CA和维低廉的字母与加权更新规则操作 。尽管他们的简单,ECA,复杂的紧急行为的能力。初始化一个ECA在随机状态导致一些规则收敛在定点或振荡流动,而其他导致混乱的模式计算不可约(他们的动力是无法预测的初始状态和选择规则而不实际执行完整的模拟)。基于这些不同的行为,Wolfram识别四个不同复杂性类、表所示1。类我CA进化是那些最终导致细胞只有一种。二类CA导致分散稳定或振荡行为。第三类CA展示一种不能简化混乱的模式。四级CA可以同时表现出任何先前的行为,似乎拥有的那种复杂性是数学建模之间的接口和生命研究[9]。Wolfram的分类是一个里程碑的理解CA属性和仍是最广泛采用的分类方案。尽管如此,其定性性质是其主要限制。事实上,正如Culik二世和Yu显示,正式重新定义Wolfram的类10)表明,确定给定ECA实际上属于哪个类不可判定的。

尽管这样的结果,努力更好的分类CA并没有减少。李和帕卡德(11]介绍了分类方案细化Wolfram最初提议的方案,有明确的目标更好的区分本地和全球混乱的行为。兰顿介绍了第一次尝试定量分类(12]。他的分类实现CA的投影规则空间1 d闭区间:CA规则和类似的定性特性大致安排可比的兰顿参数值,发现最复杂的行为边界分离周期规则从混乱的。替代定量分类方法包括概括的概念从连续动力系统应用于CA,如最大李雅普诺夫指数(标定)13]。CA,大中型企业的定义布尔雅可比矩阵(14)和捕获的主要属性连续同行:编码CA的倾向,以回笼损害在最初配置或让它蔓延,由于混沌动力学。这种方法被证明是有用的在最近的分析稳定性和复杂性的CA的转变在拓扑变化而15- - - - - -18]。许多其他分类方案已经提出多年来,基于指数复杂性(19与d-spectrum[],密度参数20.,沟通的复杂性21),算法复杂度22),集成信息(23),等等。一个全面的检查超出本文的范围。感兴趣的读者指向马丁内斯(最近的评论24]和文献引用。

在本文中,我们报告的实验证明eca的内在复杂性的新定量分类,这不同于早些时候尝试利用主要弱点困扰许多定量分类方法。我们明确地利用表达的敏感性ECA规则,初始输入状态的复杂性。近年来,已经有越来越浓的兴趣使用信息理论工具量化动力系统的复杂性,尤其是在上下文中理解生物系统(25,26]。一个有前途的工具在这种情况下传输熵(),以下的测量指示两个交互部分之间的信息交换的动力系统(27]。接下来,我们采用TE作为候选人定量选择标准分类eca的内在复杂性探索TE的敏感性变化CA的初始状态。

本文的结构如下。节2,我们从最简单的开始,非平凡、ECA的初始配置和使用它来确定动态规则能够产生一个复杂的输出量化的(TE)由于其内在的复杂性。节3,我们重复我们的分析更一般的输入和识别那些复杂的输出是由输入的复杂性,而不是继承而不是规则。然后我们根据ECA规则进行分类的最大程度的变化输出它们产生不同的输入。我们将显示,三个定量和定性不同的类自然摆脱这种分析。节4,我们表明,该分类归纳半序层次结构之间的规则,这样粗粒度的给定类的ECA收益率的ECA同一个类,或者更简单1]。最后,我们将提出进一步的应用分类方法。

2。固有的复杂性

在下面,我们确定一个CA的复杂性大量的信息流程在时间演化。采用本文提供的信息处理的概念从动态信息29日- - - - - -32),动力系统的量化计算公式,利用信息论的方法。熵在信息动态,施赖伯转会[27)是确定的信息加工的两个元素之间的动力系统。在以下的措施,一个源之间传输的信息和目标量化的减少未来的不确定性的状态吗由于知识的现状。CA的来源和目标都是CA的细胞。

在形式上,TE被定义为源之间的互信息在特定的时间和目标在时间 ,条件在一个给定的数字之前的状态: 的地方(见图1)(我) 代表细胞的状态在时间 ;(2) 细胞的状态吗在以前的时间;(3) 是向量 之前的细胞的状态;(iv) 代表所有可能的集合的模式集的状态 。

计算TE,必须先从时间序列的CA。考虑到时间序列(见图1),发生数量的模式的状态 为每个组合数的细胞和在数组中。一旦规范化的总数(不一定是不同的)模式出现在时间序列,这些频率与概率确定 出现在(1)。的条件概率 和近似地计算。

改变历史长度的值可以影响的TE计算值相同的时间序列数据。我们发现TE的价值观非常相似 6,观察TE的相当大的减少 和 (cf部分。(32]),相对于TE的价值 。因此,我们考虑 的最优值正确地捕捉过去的历史这里给出的结果(见部分3的视觉解释为什么 代表了历史最佳长度)。

我们首先生成的时间序列的简单的初始状态为每个256种可能的ECA规则,我们数字标签后Wolfram的编号方案33,34]。在下面,周期性边界条件执行。因此,不同的颜色细胞的特定位置输入数组是无关紧要的。我们的初始状态 相当于国家获得通过 接合。例如,规则18 - 183下是等价的 接合。输入更新使用规则18和共轭输入使用183规则。ECA的对称特性的全面研究,可以发现在11),256种可能的ECA规则分为88种不同的等价类。每一个类包含不超过4个规则,显示相同的行为 交换,左右转换,或两者的结合转换。感兴趣的读者可以找到这样的分类总结表1引用的工作。Wolfram类III和IV (Wolfram最近的ECA分类方案正在实施Wolfram Alpha计算引擎[28)和(表复制在这里1为方便读者),等价类也显示在图的传说2。

我们计算的数量信息处理的CA在时空的补丁的平均值计算了那地方,指定为。为此,我们演化CA 250时间步长,然后删除第一次50次步骤从每个生成的时间序列。这使我们能够评估TE / CA的因果联系的一个区域初始输入每一点空间和时间。这确保了对动态的观察相关时空的补丁是由选择规则和初始状态。由此产生的时间序列用于评估101年²值。对于每个规则,平均价值如图2(一个)。等效规则,比如规则30、86、135,到149年,产生相同的值并由一个共同的标志。为了清晰起见,个人Wolfram I和II类规则没有显示,而不是取代虚线对应于最高任何个人类I或II统治。以上第三类规则谎言I和II类的范围。有趣的是,只有110规则及其等效规则的例外,所有四级规则范围内的谎言I和II类规则。

单细胞的输入被认为是极其罕见的空间内的所有可能的初始输入。黑色细胞的数量在一个国家中随机抽取不同的可能的输入是二项分布,这意味着国家包含50或51黑白细胞 倍比我们最初选定的输入。我们的动机考虑单细胞输入首先是它自动排除了许多琐碎的从我们的搜索复杂的规则。规则,重复琐碎的方式输入或湮灭产生或全部自然地产生 。这是同样的方法,最近被认为在中科院基础分类算法复杂度22]。选择的优势很多规则根据其内在的复杂性,而不是复杂的输入。然而,选择单细胞输入的主要缺点是,许多四级看起来比他们真正的简单规则。四级106规则是一个很好的例子。简单的输入的一个黑人,106规则函数来一点黑细胞转移到左边在每个时间步,生成一个微不足道的轨迹。然而,在输入情况下,允许两个黑色细胞相互作用,106规则可以表示的全部潜力。这是一个明确的例子一些ECA规则的行为的敏感性,他们的输入的复杂性,作为讨论的介绍。孤立的复杂性规则从继承的输入,因此,我们必须考虑一个随机样本的初始状态,下一步我们做。

3所示。遗传的复杂性和信息分类

我们接下来考虑更一般的输入,随机选择的 不同的可能性。作为输入不再是对称的,我们现在需要考虑在选择等效输入反射关联规则。场景变化完全在这种情况下,如图2 (b)的最高价值二类对应规则,85年,170年和240年,包括15日产生微不足道,波行为。这些规则像106规则(尤其是170年和240年)在初始化一个单细胞的输入时,但是他们不提供任何新的,紧急重要的特性,当附近的细胞相互作用。为所有目的少内在的复杂。只有110规则及其等效规则的例外,四级像许多规则的II类和展览大量增加复杂性,定性观察和定量捕捉到为了应对更复杂的输入。

值得注意的是,所有的规则的初始值躺在I和II类的上限 位在最简单的输入情况下仍有计算高于这个值在变化的输入。特别是,价值最高的规则不影响输入的变化。我们天真地使用的上限类I和II规则新兴从图2(一个)我们称之为之间的边界线低和高的值。我们可以总结在不同输入如下所示的更改。有规则的价值低的输入。有规则的价值在最简单的情况下,低但高越复杂。最后也有规则的高价值在这两种情况下。有趣的一点是我们发现没有规则的价值 高是最简单的随机输入的输入和低吗。这相当于说,没有规则生成的复杂性对于简单的输入,但湮灭复杂的。这个观察的重要性在于,它使分类的转变在一个时空地区应对其输入的变化利用的主要限制使定量分类eca如此困难,,ECA敏感,他们的初始状态,并利用它为了实现这样的分类。

确认这确实是一个可行的定量分类方法,我们必须考虑的不仅仅是两个输入。因此,我们首先随机选择20个不同的人。多少被感兴趣可以改变我们不同的输入,对于每个规则我们选择的最大绝对值的变化百分比之间的随机输入()和单细胞输入()认为:

结果如图所示3,最大的变化百分比是策划的函数。等效规则是由一个单一的标记和分享相同的值的最大相对变化。事实上,两个规则和共享一个对称,它总是可以找到两个输入和这样的规则初始化为和规则初始化为产生相同的值。

最大的水平虚线分隔规则变化是不到一个数量级从那些可以接受改变至少10倍。垂直的虚线表示的最高价值Wolfram I和II类,如图2(一个)。该地区右边的垂直线和水平线以上无效的ECA规则。分地区将对应的值为最简单的输入和高能力高的变异,例如,CA规则,可以湮灭输入的复杂性,我们不观察。这个特性产生了一个独特的笔数的分配规则与规则在每个区域共享良好定义的属性。

因此,自然,信息化eca可以分类如下:类 :非常小的简单的输入和保持对于复杂的输入。这是最密集的课程,包括几乎所有的Wolfram I和II类规则,规则18 - 146及其等价的第三类规则。类 :小为最简单的输入,但它经历了剧烈的变化(一个数量级或更多)当输入是复杂的。这样对许多Wolfram II类和一些四级规则(如。,54和106及其等效规则)。类 :最简单的输入具有很高的价值,这种价值大约是通过改变输入的影响。大多数Wolfram第三类规则属于这个类,以及四级110规则及其等效规则。

我们的分类总结表2。尽管我们边界的任意位置线的边界地区,它显示了一个明确的划分归类为最多数的规则和。

随机采样输入导致偏见支持近五千零五十黑色和白色细胞的分布,由于他们的二项分布。因此我们也验证了这种分类使用不同分布的输入,在黑色细胞数量的增加在一个常规的方式从2到50,同时保持黑色细胞的特定位置输入数组中随机的。我们认为20个不同的输入,每个都包含 ,50黑细胞(更高的数字是不被认为是由于 结合)。除了轻微变化的数据点,应用相同的程序如上收益率相同的分类如图3强劲,表明我们的分类方案。

我们强调考虑的重要性大系统(订单细胞)而不是一个(如小得多。,订单)。而对于后者扫描整个输入空间计算是可行的(实际上我们进行这些实验),它隐藏的一个主要特性使信息化分类,类的存在规则,形成最稳定的类对我们的TE建立复杂性度量。类规则产生时间序列在很大程度上独立于初始状态,以30规则图3,只有在大系统(功能明显被组合计算的结果,TE计算时间与细胞的数量呈指数级增长。ECA数组约100个细胞是最小的大小,我们可以安全地考虑更大的比图的域3和一个完整的扫描规则空间和一个足够大的输入可以合奏。我们也认为与200年和400年细胞单独运行,发现我们的数值结果是稳定的CA 100或更多的细胞,但波动与50个或更少的细胞CA)。

典型的、订单10细胞的长度域出现在图3是同样的原因吗 历史是最优值长度参数。较小的和更大的价值将无法解决这种晶格尺寸类的独立特性吗规则(32)(图4)。

4所示。粗粒度的和信息的层次结构

也许最有趣的特性的定量分类,Wolfram第三类和第四类规则是分布在不同的信息化类。这种行为看起来就不那么令人吃惊的发现的粗粒度的转换在ECA以色列和Goldenfeld [1]。物理世界的一个重要方面是粗粒度的描述通常足以使有关行为的预测。指出,以色列和Goldenfeld采用一种系统化的过程来粗粒ECA规则。处方由在附近的组成细胞CA给定大小的数组变成超晶胞,根据一些指定的超晶胞单细胞的信件(布尔CAs,这种可能的应用存在),和一个给定的时间常数。寻找一个粗粒度的规则在于寻找一个新的CA规则,运行最初的CA时间步长,然后分组vortex,产生相同的输出分组初始数组,然后采用新的CA规则时间的步骤。新的CA规则、时间常数和超晶胞的大小都是未知的;因此,这种搜索需要扫描这些参数的所有可能的组合。以色列和Goldenfeld成功粗粒度的240年256年的ECA规则,许多其他ECA规则,执行一个完整的扫描所有兼容的可能性 。重要的是,规则的复杂性没有观察到在粗粒度的增加,引入偏序中CA规则。

从我们的信息分类相同的顺序出现,如图5,箭头表示了粗粒度的转换(1]。这些转换引入完全有序的层次结构 这样粗粒度的从未观察到层次结构,和绝大多数的规则可能只进行粗粒度的转换中相同的信息类。这种顺序有时被预期,像在我们的许多类规则,波模式是粗粒度的自相似,或非常相似的模式。有时它看起来更深刻,就像在Wolfram第三类146规则。规则是在非平凡,它可以是粗粒度的128规则(Wolfram类我规则),由于共享敏感信息的处理在一个特定的时空补丁,其输入状态。如前所述(1),这一事实可能(ECA规则的计算不可约性的确凿证据146失踪)计算不可约规则(8]像小学146规则可以粗粒度可预测的动态(例如,128)表明,计算不可约性可能缺乏良好的物理测量的复杂性的特点。我们领导认为定义的粗粒度的层次更有可能保存信息属性,对于更复杂的规则,Wolfram分类出现较低的层次,如果他们可以粗粒度与常见的灵敏度不太复杂的输入状态。

5。结论

物理系统进化的时间根据当地,统一规则,但却表现出复杂、紧急行为。复杂性产生的初始状态或规则,或两者的某种组合。确定的复杂性是由规则的模糊或州已经困扰了先前的努力孤立的复杂性内在对于一个给定的规则。在这项工作中,我们引入了一个定量,ECA的信息化、分类。提出的分类方案避免了困难产生由于表达的敏感性ECA规则的初始状态的复杂性。(平均)直接的信息交换(TE)的各个部分之间一个ECA用作衡量它的复杂性。单细胞的识别输入(部分2)作为重要的国家最少的复杂性假设工作假说,为我们的分析提供了一个参考点的ECA规则的复杂性的变化程度不同的输入。根据我们的分析,我们确定了三个不同的类,他们对初始条件的敏感性不同。类ECA总是处理小信息,类总是处理高信息,和类可以根据输入低或高。它仅仅是为类表达的复杂性是内在的,而不是产品的复杂性由输入。

最复杂的规则,我们的分析是在课堂上,其中包括Wolfram的大部分第三类规则和四级110规则及其等效规则。这些规则形成一个封闭的组织下粗粒度的转换中发现(1]。真正复杂的规则仍是那些复杂的描述,即使在一个宏观的行为是不敏感的初始状态。

我们正在调查扩展我们的措施的可能性更少的基本动力系统,以及理想化的生物系统(例如,网络监管的基因)。受到护士的想法35),信息存储和流的优化可能代表生物功能的独特特征,我们发现有趣的信息动态识别最复杂的ECA动力学与那些至少依赖他们的初始状态。这个特性,唤起冗余无处不在的生物学、生物学可能代表之间的联系和信息动力学(36我们认为值得进一步研究。

信息披露

的观点是作者和出版不一定反映邓普顿世界慈善基金会的观点。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

这个出版成为可能通过支持从邓普顿世界慈善基金会的资助。作者感谢道格拉斯·摩尔和赫克托耳Zenil他们有用的评论。