复杂性的回旋之路
在我的最后一篇关于向幼儿教授量子计算基础知识的文章中，我谈到了计算复杂性这一主题，并指出该领域不应与例如在圣达菲研究所可能遇到的更一般性的复杂性研究相混淆。 我想用这篇文章在更复杂的一般领域上进行一些扩展，也许不是将其教给学步儿童，而是将其面向青少年（他们因此能够自己做出一些演绎，推论）。 我将使用基本单元自动机，音乐和插图的概念的类似插图。 此处使用元胞自动机的灵感来自斯蒂芬·沃尔夫拉姆（Stephen Wolfram）的《一种新型的科学》（在这里我将其缩写为NKS），并且许多讨论将以该工作中涉及的主题为指导。 我还将从Wolfram的《简单程序图集》中借用这些自动机的几张图像。
尽管NKS并不是主要写关于复杂性的文章，但它是我较早接触该概念的部分之一，部分启发了梅兰妮·米切尔（Melanie Mitchell），斯图尔特·考夫曼（Stuart Kauffman），乔治·约翰逊（George Johnson），穆雷·盖尔曼（Murray Gell-Mann），扬尼尔·巴耶姆（Yaneer Bar-Yam）等作家的阅读旅程-对于希望了解更多有关该主题的人，这些作者是不错的起点，圣塔菲研究所的“复杂性浏览器”也提供了MOOC。
- 本杰明·科里（Benjamin L. Corey）的“ Unafraid”评论
- 书评：“手表，经过彻底修订”，吉恩·斯通和斯蒂芬·普尔维尔恩特
- 书评：边界：玛丽亚·格鲁兹德瓦（Maria Gruzdeva）的俄罗斯边缘之旅
- 书评：《 Kind of Blue》，肯·克拉克（Ken Clarke）
- 书评：《我的灵魂》一书中的鼓舞人心的诗歌–米歇尔·蕾妮·基德威尔
首先简要介绍细胞自动机。 基本的细胞自动机基本上是一组规则，用于确定二进制（黑色/白色）单元的2D网格的值的进展，该网格从顶部开始向下发展。 网格以输入行作为种子（此处的大多数示例将具有单个黑色单元的种子或一排随机放置的黑白单元的种子），然后根据种子行的值，规则将确定网格中的单元的值。随后的每一行，并且类似地向下，所得的输出图像具有一些有趣的形状，复杂程度各不相同。 对于简单版本，我们将在此处讨论，这些规则将仅基于紧接在上一行中的三个父单元格得出子单元格的值。 由于将有2³= 8个需要规则的父单元格组合，因此有8个子单元格的潜在输入，因此我们可以得出，将有2⁸= 256个基本细胞自动机的潜在变体，传统上使用编号约定来识别为0-255。
此处显示的是256条规则中的一些突出规则，这些规则将演示各种潜在输出形状。 尽管其中一些（如128或136）在此处显示为带有一些种子细胞以展示某些特定行为，但大多数显示的种子在顶部排有一个黑色细胞的种子。 通常，单个种子细胞会导致某种三角形的输出，因为该细胞的影响范围在随后的每一行中都扩大了，尽管对于某些规则（其中三个白色父细胞导致一个黑色子细胞），可能会进行行范围的转换立即。
没有计算机来模拟细胞自动机的研究就不会很实际。 这变成了NKS的主题之一，即计算机模拟如何为科学发现的新途径（也称为“新型科学”）打开大门。 基本的细胞自动机值得关注，因为即使在它们非常有限的256个简单规则空间中，也可能发现大量潜在行为和复杂性。 我们可以将潜在行为分为四类。 1类是最简单的，其初始条件导致某些统一的最终状态（示例包括规则0、4、255等）。 第2类可能具有许多潜在的最终状态，但它们都是一组简单的统一或重复形状（示例包括规则1、50、190等）。 第3类是事物开始变得有趣的地方，在这些规则中，行为随着表观随机性和形状的分形嵌套而变得更加复杂（示例包括规则22、30、90等）。 第4类也许是最有趣的，它涉及顺序和随机性的混合，其局部结构可能看起来很简单，但通过逐步移动并以复杂的方式彼此交互-这种行为在更复杂的播种之后变得更加明显。一个单元格，我们将进行一些演示（示例包括规则110、124、137等）。 应该注意的是，这四个类别之间的界限并不牢固，某些规则可能会在一定程度上显示多个类别的属性。 如果您还记得关于基本细胞自动机的一件事，那就应该是：这些规则说明，即使是非常简单的规则，也有可能产生系统的高度复杂且不可还原的行为。
根据行为将这些细胞自动机分为四类，是对它们的复杂性的一种度量。 研究人员根据各种指标（例如，系统描述的难易程度，创建的难易程度或组织的程度）对系统的复杂性进行了更一般的描述-塞斯（Seth）收集了42个此类描述的代表性清单劳埃德在这里。 请注意，劳埃德（Lloyd）并不声称此清单是详尽无遗的，实际上是要求提交其他指标，这可能暗示着对于研究人员之间复杂性定义的正式协议有些含糊。 梅兰妮·米切尔（Melanie Mitchell）有帮助地阐明：“到目前为止，复杂性还不是一门统一的科学； 相反，用威廉·詹姆斯（William James）来解释，它仍然是“科学的希望”。 我相信这个希望很有希望。”
就像工业工程师的工具箱基于概率和统计数据一样，复杂性研究的工具也是通过计算机仿真的模型。 这篇文章将主要介绍细胞自动机的仿真，其进化规则是基于相邻细胞的值，但是还有许多其他类型的系统可以使用更精细的规则进行模拟，例如人群动态，街道交通模式或甚至电网分配系统。 通过基本细胞自动机行为的模拟，我们将在此处尝试探索一些复杂性特征。
