聚合和平铺作为多计算过程 – 搞英语 → 看世界

Aggregation and Tiling as Multicomputational Processes

多路系统的重要性

这一切都与系统有关，其中实际上可以有许多可能的历史路径。在像元胞自动机这样的典型标准计算系统中，总是只有一条路径，由从一种状态到下一种状态的演化来定义。但在多路系统中，可能有许多可能的下一个状态，因此也有许多可能的历史路径。多路系统在我们的物理项目中发挥着核心作用，特别是在与量子力学相关的方面。但现在正在出现的是，多路系统实际上是一个全新的“多计算”建模范式的相当普遍的基础。

我的目标是双重的。首先，我想使用多路系统作为基于聚合和平铺的增长过程的最小模型。其次，我想使用这个具体的应用程序来进一步发展对一般多路系统的直觉。在其他地方，我探索了字符串的多路系统、基于数字的多路系统、多路图灵机、多路组合器、多路表达式评估以及基于游戏和谜题的多路系统。但在研究用于聚合和平铺的多路系统时，我们将处理一些更加物理和有形的东西。

当我们想到“聚合增长”时，我们通常会想象一个“随机过程”，其中新的部分“随机”添加到某些东西中。但这些“随机可能性”中的每一个实际上都定义了不同的历史路径。多路系统的概念就是捕获所有这些可能性。在典型的随机（或“随机”）模型中，人们只是追踪一条历史路径，并且人们想象没有足够的信息来说明它将是哪条路径。但在多路系统中，人们会关注所有路径。在这样做的过程中，从某种意义上说，我们正在为可能发生的事情的“整个故事”建立一个模型。

单一路径的选择可以是“不确定的”。但整个多路系统是确定性的。通过研究“确定性整体”，通常可以做出有用的、相当笼统的陈述。

人们可以将多路系统演化中的某个特定时刻视为统计力学中研究的那种状态集合。但是，多路系统的一般概念及其在离散步骤中的离散分支，取决于传统统计力学中相当陌生的基本离散性水平，尽管以计算甚至数学方式定义是非常简单的。

对于聚合来说，建立一个最小离散模型是很容易的——至少如果模型允许显式随机性的话。但我们在这里要做的一个要点是“超越”随机性，根据整个确定性多路系统建立我们的模型。

通过观察整个多路系统我们可以学到什么？嗯，例如，我们可以看到是否总是会增长——无论随机选择是什么——或者增长是否有时甚至总是停止。在许多实际应用中（例如肿瘤），了解生长是否总是停止或通过什么途径继续生长可能非常重要。

我们首先要做的很多事情都涉及了解当地限制对增长的影响。稍后，我们还将研究几何效果，并将研究不同形状的对象如何聚合或最终平铺。

从某种意义上说，我们将介绍的模型非常简单——将最简单的多路结构与最简单的空间结构相结合。由于这种极简性，模型几乎不可避免地会成为各种系统的理想化，并成为这些系统的良好模型的基础。

乍一看，多路系统似乎相当抽象且难以掌握——考虑到我们人类倾向于顺序思考，这也许是不可避免的。但是，通过了解多路系统在增长过程的具体案例中如何发挥作用，我们可以建立自己的直觉并形成更扎实的观点，这将使我们在探索多路系统的其他应用时处于有利地位，并且总体上有助于我们整个多计算范式的术语。

最简单的案例

它是随机离散增长的终极最小模型（通常称为伊甸园模型）。在方形网格上，从一个黑色单元格开始，然后在每一步中随机将一个新的黑色单元格附加到不断增长的“簇”上：

10,000 步后我们可能会得到：

但所有可能发生的事情有哪些呢？为此，我们可以构建一个多路系统：

许多这样的簇仅因微小的翻译而有所不同。通过翻译规范化我们得到

或在另一步骤之后：

如果我们还减少旋转和反射，我们会得到

或在另一步骤之后：

t步骤之后的可能簇集就是具有t细胞的可能的多联骨牌（或“方格动物”）。连续t的这些数量是

对于大t ，其增长大致类似于k ^t ，其中k略大于 4：

顺便说一句，通过翻译进行规范化总是将可能的簇数量减少t倍。如果簇不具有对称性（对于大型簇来说这种可能性越来越大），则通过旋转和反射进行规范化可以将数量减少 8 倍，并且簇具有的对称性越小，则簇的对称性越高，如下所示：

通过规范化，经过 7 个步骤后的多路图具有以下形式

使用替代渲染看起来并没有更简单：

如果我们想象在每一步中，单元都以相等的概率添加到簇上的每个可能位置，或者等效地，非规范化多路图中给定簇的所有传出边都以相等的概率跟随，那么我们可以得到分布获得的不同典型簇的概率——此处显示了 7 个步骤后的结果：

我们一开始看到的大型随机簇的一个特征是它有一些漏洞。经过 7 个步骤后，带孔的簇开始形成，最小的是：

可以通过多路系统的子集到达该集群：

事实上，在大簇的限制下，存在洞的概率似乎接近 1——尽管被洞覆盖的总面积比例接近 0。

描述“可能的簇的空间”的一种方法是通过在多路图中向后一步连接具有共同祖先的每对簇来创建分支图：

所有这些图的连通性反映了这样一个事实，即根据我们使用的规则，在任何步骤中总是可以通过一系列删除一个单元格/添加一个单元格更改从一个集群转到另一个集群。

这里的鳃图还显示了由底层晶格的对称性产生的 4 重对称性。将状态规范化，我们得到更小的鳃图，不再显示任何此类对称性：

总体约束增长（4 单元邻域）

根据我们到目前为止讨论的规则，要附加的新单元可以位于集群上的任何位置。但是，如果我们通过要求新细胞周围必须有一定数量的现有细胞来限制生长呢？具体来说，让我们考虑一下规则任何给定位置周围的邻居，并且仅当邻域中存在指定数量的现有单元时才允许在那里存在新单元。

从黑色单元格的交叉开始，以下是 20 步后获得的一些随机簇示例，其中包含此类所有可能的规则（开头的“4”表示这些是 4 邻域规则）：

不允许新单元最终只有一个现有邻居的规则只能填充其初始条件下的角落，并且不能进一步增长。但是任何只允许一个现有邻居增长的规则都会产生永远持续增长的集群。以下是 10,000 步后可以得到的一些随机示例：

最后一个是我们上面已经讨论过的无约束（伊甸园模型）规则。但让我们更仔细地看看第一种情况——只有当一个新的单元格最终只有一个邻居时才会出现增长。本例中的规范化多路图为：

这里可能的簇对应于“始终为一个单元宽”（即没有 2×2 块）的多联骨牌，或者等效地，在步骤t处具有周长 2 t + 2 。这种规范化集群的数量增长如下：

这在多骨骨牌总数中所占的比例越来越大，这意味着大多数大型多骨骨牌都采用这种“细长”的形式。

具有约束的规则的一个新特征是并非集群周围的所有位置都允许增长。这是上面多路系统的一个版本，如果允许新的生长，每个簇周围的细胞用绿色注释，如果不允许，则用红色注释：

在更大的随机集群中，我们可以看到，使用此规则，大部分内部都是“死的”，因为规则的约束不允许那里进一步增长：

顺便说一下，由这个规则生成的簇总是可以直接用它们的“骨架图”来表示：

查看上述所有（与 1-邻居一起增长）规则的随机集群，我们在每种情况下都会看到不同的孔模式：

这里总共区分了五种类型的小区，反映了不同的邻居配置：

以下是使用 4:{1,3} 规则生成的示例集群：

单元格用已经有太多邻居，因此永远无法添加到集群中。单元格用具有要立即添加的正确数量的邻居。单元格用目前没有足够数量的邻居可供增长，但如果邻居已填满，则可能可以添加它们。有时会发现，当邻居单元格被填充，它们实际上会阻止单元格被添加（这样它就变成了）——在此处所示的特定情况下，2×2 块发生细胞。

此处显示的规则的多向图在性质上都很相似，但存在细节差异。特别是，至少对于许多规则来说，相对于所有情况下的增长 4:{1,2,3,4} 规则，越来越多的状态“缺失”——或者，在换句话说，由于限制，越来越多的多联骨牌无法生成：

第一个无法到达的多联骨牌（出现在步骤 4 中）是：

在第 6 步，规则 4:{1,3} 和 4:{1,3,4} 无法到达的多联骨牌是

而对于 4:{1} 和 4:{1,4} 则附加多联骨牌

也无法到达。

在步骤 8 中，多联骨牌

可以使用 4:{1} 和 4:{1,3} 访问，但不能使用 4:{1,4} 和 4:{1,3,4} 访问。

值得注意的是，排除多骨牌的规则都无法达到：

总体约束增长（8 单元邻域）

如果考虑对角邻居和正交邻居，从而在一个单元周围总共有 8 个邻居，会发生什么？在这种情况下有 256 种可能的规则，对应于Range [8]的可能子集。以下是他们从初始阶段开始 200 步后所做的示例簇：

这里至少最初显示出增长的两种情况是（“8”表示这些是 8 邻域规则）：

在 {2} 情况下，多路图开始于：

人们可能会假设该图中的每个分支都会永远持续下去，并且增长永远不会“停滞”。但事实证明，经过 9 个步骤后，生成了以下簇：

对于这个簇，不可能进一步增长：边界周围的位置没有恰好有 2 个邻居。在最多 10 个步骤的多路图中，事实证明这是唯一可以生成的“终端簇”——总共 1115 个可能的簇中：

那么如何到达终端集群呢？这是导致它的多路图的片段：

如果我们不修剪所有“误入歧途”的方式，该片段将显示为更大的多路图的一部分：

如果随机遵循未修剪（且未规范化）的多路图中的所有路径（即在每一步，以相同的概率选择每个分支），则事实证明，到达该特定终端簇的概率仅为：

（事实上，这个数字相当小意味着系统远未汇合；例如，有许多路径没有收敛到与该终端簇相对应的固定点。）

如果我们继续发展多路系统，我们将到达其他终端集群； 12步后出现以下结果：

对于上面的 {3} 规则，多路系统需要更长的时间才能“开始”：

再次出现终端集群，导致系统卡住；其中第一个出现在第 14 步：

并且终端集群再次作为整个多路系统中的孤立节点出现：

导致它的多路图片段是：

到目前为止，我们一直在通过等待终端集群出现在多路系统的演化中来寻找它们。但还有另一种方法，类似于填充诸如平铺之类的内容时可能使用的方法。这个想法是，终端簇中的每个单元都必须有不允许进一步增长的邻居。换句话说，终端集群必须由某些约束不允许增长的“局部块”组成。但是局部图块的配置有哪些可能呢？为了确定这一点，我们将图块的匹配条件转换为逻辑表达式，其变量为True和False ，具体取决于模板中的特定位置是否包含簇中的单元格。通过解决这些逻辑表达式的组合的可满足性问题，可以找到可以想象地对应于终端集群的小区配置。

按照此过程，针对区域最多为 6×6 个单元的 {2} 规则，我们发现：

但现在还有一个额外的限制。假设从连接的初始簇开始，则生成的任何后续簇也必须连接。删除未连接的情况，我们得到：

那么给定这些终端簇，什么初始条件可以导致它们呢？为了确定这一点，我们必须有效地反转聚合过程——最终给出一个多路图，其中包括可以生成给定终端集群的所有初始条件。对于最小的终端簇，我们得到：

我们的 4 单元“T”初始条件出现在这里，但我们看到还有更小的 2 单元初始条件，它们会导致相同的终端簇。

对于我们之前展示的所有终端簇，我们可以从通向它们的最小初始簇开始构建多路图：

对于像这样的终端集群

没有重要的多路系统可以显示，因为这些簇只能作为初始条件出现；它们永远不可能在进化中产生。

有相当多的小簇只能作为初始条件出现，并且在聚合规则下不具有原像。以下是适合 3×3 区域的情况：

{3} 规则的情况与 {2} 规则非常相似。最多 5×5 的可能终端簇为：

然而，其中大多数只有相当有限的一组可能的原像：

例如我们有：

事实上，除了我们上面已经展示的 (size-17) 示例之外，这里没有出现可以从 T 初始条件生成的其他终端簇。然而，进一步采样，会出现额外的终端簇（从大小 25 开始）：

其中前几个的多路图片段是：

随机进化

我们在上面已经看到，对于我们一直在研究的规则，终端集群在多路系统的可能状态中是相当罕见的。但如果我们随机进化会发生什么呢？我们多久会遇到一个终端集群？当我们说“随机进化”时，我们的意思是，在每一步中，我们都会查看所有可能的位置，在这些位置中，新单元格可以添加到迄今为止存在的簇中，然后我们将选择其中实际添加新单元的概率相同。

对于 8:{3} 规则，会发生一些令人惊讶的事情。尽管终端簇在多路图中很少见，但事实证明，无论其初始条件如何，它最终总是会到达终端簇，尽管这通常需要一段时间。例如，这里有一些可能的终端簇，并标注了到达它们所需的步数（也等于它们包含的单元格数量）：

终止步骤数的分布似乎非常粗略呈指数分布（此处基于 10,000 个随机案例的样本），平均寿命约为 2300，半衰期约为 7400：

下面是一个大型终端集群的示例，需要 21,912 个步骤才能生成：

这是一张地图，显示了该簇的不同部分发生增长的时间（蓝色是最早的，红色是最晚的）：

这张图表明，星团的不同部分在不同的时间“积极增长”，如果我们看一下增长随时间变化的“时空”图，我们可以证实这一点：

事实上，这表明正在发生的事情是，集群的不同部分最初是“肥沃的”，但后来不可避免地“耗尽”——因此最终没有任何可能的位置可以发生增长。

但最终的终端簇可以形成什么形状呢？我们可以通过查看“紧凑性度量”（通常用于研究不公正划分）来获得一些想法，该度量粗略地给出了从每个簇中心到其中每个单元格的距离的标准差。 “非常拉丝”和“大致呈圆形”的星团都相当罕见。大多数集群介于两者之间：

如果我们不看 8:{3} 而是看 8:{2} 规则，情况就会大不相同。正如多路图所示，再次可以到达终端集群。但现在随机进化几乎永远不会到达终端簇，而是几乎总是“逃跑”以生成无限簇。在这种情况下生成的簇通常比 8:{3} 情况更“紧凑”

这也体现在“时空”版本中：

平行增长和因果图

到目前为止，在构建集群时，我们一直假设单元是按顺序添加的，一次一个。但如果两个单元相距足够远，我们实际上可以“同时”并行添加它们，并最终构建相同的集群。我们可以将每个单元的添加视为更新集群状态的“事件”。然后，就像在我们的物理项目和多重计算的其他应用中一样，我们可以定义一个因果图来表示这些事件之间的因果依赖性，然后这个因果图的叶状结构告诉我们可能的整体更新序列，包括并行。

举个例子，考虑“总是增长”4：{1,2,3,4}规则中的状态序列——其中每一步新的单元格都被涂成红色（我们包括“无”状态）在开头）：

连续状态之间的每次转换都定义一个事件：

如果第二个事件中添加的单元格与第一个事件中添加的单元格相邻，则一个事件与另一个事件存在因果依赖性。因此，例如，存在因果关系，例如

和

在第二种情况下，添加了额外的“空间分离”单元，这些单元不涉及因果依赖性。将所有因果依赖性放在一起，我们得到了这一演变的完整因果图：

我们可以通过选择这些事件的特定顺序来恢复原始的状态序列（此处由它们添加的单元格的位置表示）：

该路径具有始终遵循因果边方向的属性，我们可以通过对因果图使用不同的布局来使其更加明显：

但一般来说，我们可以使用与因果图一致的任何事件顺序。另一种排序（在本例中共有 40,320 种可能性）是

给出了状态序列

具有相同的最终集群配置，但中间状态不同。

但现在的重点是，因果图隐含的约束并不要求所有事件都按顺序应用。有些事件可以被视为“空间分离”，因此可以同时应用。事实上，因果图的任何叶状结构都定义了应用事件的特定顺序——顺序或并行。因此，例如，这是因果图的一种特定叶状结构（用因果图的两种不同渲染显示）：

这是获得的相应状态序列：

由于在该叶状结构的某些部分中，多个事件“并行”发生，因此达到最终配置的速度“更快”。（碰巧的是，这种叶状结构就像我们物理项目中的“宇宙静止框架叶状结构”，并且涉及每个切片上发生的最大可能数量的事件。）

不同的叶状结构（在这种情况下总共有 678,972 种可能性）将给出不同的状态序列，但最终状态始终相同：

请注意，我们在这里所做的任何事情都不取决于我们使用的特定规则。例如，对于具有状态序列的 8:{2} 规则

因果图是：

值得评论的是，我们在这里所做的一切都是针对特定的状态序列，即多路图中的特定路径。实际上，我们所做的就是经典时空物理学的模拟——追踪特定进化历史中的因果关系。但总的来说，我们可以看到整个多向因果图，其中的事件不仅是时间或空间上分离的，而且是分支上分离的。如果我们对这个图进行叶化，我们不仅会得到“经典”时空状态，而且还会得到“量子”叠加状态，需要用多空间之类的东西来表示（其中在每个空间位置，都有可能的单元格值的“分支堆栈”）。

一维情况

到目前为止，我们一直在考虑二维聚合过程。但是一维呢？在一维中，“簇”仅由一系列细胞组成。最简单的规则允许在单元格与已存在的单元格相邻时添加该单元格。从单个细胞开始，根据这样的规则，这是可能的随机进化，如下所示：

我们还可以为此规则构建多路系统：

规范化状态给出了简单的多路图：

但就像在 2D 情况下一样，如果增长受到限制，事情就会变得不那么琐碎。例如，假设在放置新单元格之前，我们计算距离 1 或距离 2 的单元格数量。如果允许的单元格数量只能恰好为 1，我们会得到如下行为：

对应的多路系统为

或规范化后：

这里t步骤之后的不同序列的数量由下式给出

可以用斐波那契数来表示，对于大的t大约是。

该规则实际上生成所有可能的类似莫尔斯电码的序列，由 2 单元（“长”）黑色块或 1 单元（“短”）黑色块组成，散布着单个白色单元的“间隙” 。

该系统的鳃图具有以下形式：

查看此类所有可能规则的随机演化，我们得到：

相应的规范化多路图是：

到目前为止，我们看到的规则纯粹是总体性的：是否可以添加新单元格仅取决于其邻域中的单元格总数。但是（就像在元胞自动机中一样）也可以制定规则，其中是否可以添加新单元取决于邻域中单元的完整配置。然而，大多数情况下，此类规则似乎非常像极权主义规则。

其他概括包括，例如，具有多个单元“颜色”的规则，以及取决于不同颜色的单元总数或其详细配置的规则。

三维案例

我们对 2D 和 1D 聚合系统所做的分析可以轻松扩展到 3D。作为第一个示例，考虑这样的规则：只要单元与现有单元相邻，就可以沿着 3D 网格中 6 个坐标方向中的每一个方向添加单元。以下是在这种情况下形成的随机簇的一些典型示例：

对第一个切片进行连续切片（并按“年龄”着色），我们得到：

如果我们仅允许在某个单元与一个现有单元相邻时添加该单元（对应于规则 6：{1}），我们会得到从外部看起来几乎无法区分的簇

但它有一个“更通风”的内部结构：

就像在 2D 中一样，有 6 个邻居，除非在邻居中只有 1 个单元格时可以添加单元格，否则不可能无限增长。但与 2D 中发生的情况类似，当我们允许“角邻接”并拥有 26 个单元邻域时，事情会变得更加复杂。

如果只要有至少一个相邻单元格就可以添加单元格，则结果与 6 个相邻单元格的情况类似，只是现在可能存在“角相邻的分支”

整个结构“仍然更加通风”：

对于像 26:{2} 这样的规则，质量变化不大，其中增长只能在正好 2 个邻居的情况下发生（此处从 3D 二聚体开始）：

但什么时候增长、什么时候不增长这个普遍问题是相当复杂和微妙的。特别是，即使有特定的规则，通常也有一些初始条件可以导致无限增长，而另一些则不能。

有时会出现一段时间的增长，但随后就停止了。例如，根据规则 26:{9}，3×3×3 块的一种可能的演化路径是：

在这种情况下，完整的多路图终止，确认无限增长是不可能的：

然而，在其他初始条件下，该规则可以增长更长的时间（此处每 10 步显示一次）：

据我们所知，所有规则 26:{ n } 都会导致无限增长，并且不为。

多边形形状

到目前为止，我们一直在研究 2D、1D 和 3D 网格中的“填充单元格”。但我们也可以考虑在没有网格的情况下“放置瓷砖”，每个新瓷砖都将边缘连接到现有瓷砖上。

对于方形瓷砖，没有真正的区别：

多路系统与我们最初在 2D 网格上的“随处生长”规则相同：

下面是三角形瓷砖的情况：

多路图现在生成所有polyiamonds （三角形polyforms）：

由于等边三角形可以镶嵌在规则的晶格中，我们可以将其视为“填充晶格中的单元格”，而不仅仅是“放置瓷砖”（就像正方形的情况一样）。以下是本例中随机簇的一些较大示例：

正六边形基本上也会发生同样的情况：

多路图生成所有多边形：

以下是一些较大簇的示例，显示出比三角形情况更多的“卷须”：

在像这样的“有效网格”情况下，我们还可以继续对邻域配置施加约束，就像我们在上面前面的部分中所做的那样。

但是，如果我们考虑不将平面细分的形状（例如正五边形），会发生什么？我们仍然可以“顺序放置图块”，但任何新图块都不能与现有图块重叠。通过这条规则，我们得到例如：

以下是一些“随机生长”的较大簇，内部显示出各种不规则形状的间隙：

（是的，正确生成这样的图片绝非易事。在“有效晶格”的情况下，多边形之间的重合相当容易准确确定。但在五边形的情况下，这样做需要以高度解方程代数数域。）

然而，多路图与“有效晶格”情况的多路图并没有显示出任何立即明显的差异：

如果我们快速查看最后一步显示的结果，可以更容易地了解发生了什么：

本例中的鳃图具有以下形式：

这是一个由五边形组成的更大的簇：

请记住，其构建方式是通过测试每个“暴露的边缘”并查看在哪种情况下五边形将“适合”，在每一步中顺序添加一个五边形。与我们所有其他示例一样，“外部”边缘与“内部”边缘没有优先权。

请注意，虽然“有效晶格”簇最终总是会填满所有孔，但对于五边形情况而言并非如此。在这种情况下，在极限情况下，大约 28% 的总面积被孔占据。顺便说一句，存在一个明确的“动物园”，其中至少有一些可能的小漏洞，这里用它们的（对数）概率绘制：

那么其他正多边形会发生什么情况呢？这是一个八边形的示例（在这种情况下，孔所占的限制总面积约为 35%）：

顺便说一句，在这种情况下，这是“漏洞动物园”：

对于五边形，很明显会出现难以解决的几何情况。人们可能会认为八边形可以避免这些。但仍然存在很多奇怪的“不匹配”，例如

不容易表征或分析。顺便说一句，人们应该注意，任何时候形成“闭合孔”，与形成其边界的边缘相对应的矢量必须总和为零——实际上定义了一个方程。

当正多边形的边数变大时，我们的簇将近似圆形堆积。这是一个 12 边形的示例：

但当然，因为我们坚持一次添加一个多边形，所以得到的结构比真正的圆形包装“更通风”——通过“推动边缘”获得的那种（至少在 2D 中）集群的。

多骨牌瓷砖

在上一节中，我们考虑了由正多边形构造的“顺序平铺”。但我们使用的方法非常通用，可以应用于由任何形状（或者至少是可以识别“附着边缘”的任何形状）形成的顺序平铺。

作为第一个例子，考虑多米诺骨牌或二聚体形状——我们假设它可以垂直和水平定向：

这是由二聚体形成的稍大的簇：

这是本例中的规范化多路图：

这是鳃图：

那么其他多骨骨牌形状又如何呢？当我们尝试按顺序平铺这些元素（有效地制作“多聚骨牌”）时，会发生什么？

以下是基于 L 形多骨牌的示例：

这是一个更大的集群

这是仅 1 步后的规范化多路图

and after 2 steps:

The only other 3-cell polyomino is the tromino:

(For dimers, the limiting fraction of area covered by holes seems to be about 17%, while for L and tromino polyominoes, it’s about 27%.)

Going to 4 cells, there are 5 possible polyominoes—and here are samples of random clusters that can be built with them (note that in the last case shown, we require only that “subcells” of the 2×2 polyomino must align):

The corresponding multiway graphs are:

Continuing for more steps in a few cases:

Some polyominoes are “more awkward” to fit together than others—so these typically give clusters of “lower density”:

So far, we’ve always considered adding new polyominoes so that they “attach” on any “exposed edge”. And the result is that we can often get long “tendrils” in our clusters of polyominoes. But an alternative strategy is to try to add polyominoes as “compactly” as possible, in effect by adding successive “rings” of polyominoes (with “older” rings here colored bluer):

In general there are many ways to add these rings, and eventually one will often get stuck, unable to add polyominoes without leaving holes—as indicated by the red annotation here:

Of course, that doesn’t mean that if one was prepared to “backtrack and try again”, one couldn’t find a way to extend the cluster without leaving holes. And indeed for the polyomino we’re looking at here it’s perfectly possible to end up with “perfect tilings” in which no holes are left:

In general, we could consider all sorts of different strategies for growing clusters by adding polyominoes “in parallel”—just like in our discussion of causal graphs above. And if we add polyominoes “a ring at a time” we’re effectively making a particular choice of foliation—in which the successive “ring states” turn out be directly analogous to what we call “generational states” in our Physics Project .

If we allow holes (and don’t impose other constraints), then it’s inevitable that—just with ordinary, sequential aggregation—we can grow an unboundedly large cluster of polyominoes of any shape, just by always attaching one edge of each new polyomino to an “exposed” edge of the existing cluster. But if we don’t allow holes, it’s a different story—and we’re talking about a traditional tiling problem, where there are ultimately cases where tiling is impossible, and only limited-size clusters can be generated.

As it happens, all polyominoes with 6 or fewer cells do allow infinite tilings. But with 7 cells the following do not:

It’s perfectly possible to grow random clusters with these polyominoes—but they tend not to be at all compact, and to have lots of holes and tendrils:

So what happens if we try to grow clusters in rings? Here are all the possible ways to “surround” the first of these polyominoes with a “single ring”:

And it turns that in every single case, there are edges (indicated here in red) where the cluster can’t be extended—thereby demonstrating that no infinite tiling is possible with this particular polyomino.

By the way, much like we saw with constrained growth on a grid, it’s possible to have “tiling regions” that can extend only a certain limited distance, then always get stuck .

It’s worth mentioning that we’ve considered here the case of single polyominoes. It’s also possible to consider being able to add a whole set of possible polyominoes —“ Tetris style”.

Nonperiodic Tilings

We’ve looked at polyominoes—and shapes like pentagons—that don’t tile the plane. But what about shapes that can tile the plane, but only nonperiodically? As an example, let’s consider Penrose tiles . The basic shapes of these tiles are

though there are additional matching conditions (implicitly indicated by the arrows on each tile), which can be enforced either by putting notches in the tiles or by decorating the tiles:

Starting with these individual tiles, we can build up a multiway system by attaching tiles wherever the matching rules are satisfied (note that all edges of both tiles are the same length):

So how can we tell that these tiles can form a nonperiodic tiling? One approach is to generate a multiway system in which at successive steps we surround clusters with rings in all possible ways:

Continuing for another step we get:

Notice that here some of the branches have died out. But the question is what branches exist that will continue forever, and thus lead to an infinite tiling? To answer this we have to do a bit of analysis.

The first step is to see what possible “rings” can have formed around the original tile. And we can read all of these off from the multiway graph:

But now it’s convenient to look not at possible rings around a tile, but instead at possible configurations of tiles that can surround a single vertex. There turns out to be the following limited set:

The last two of these configurations have the feature that they can’t be extended: no tile can be added on the center of their “blue sides”. But it turns out that all the other configurations can be extended—though only to make a nested tiling, not a periodic one.

And a first indication of this is that larger copies of tiles (“supertiles”) can be drawn on top of the first three configurations we just identified, in such a way that the vertices of the supertiles coincide with vertices of the original tiles:

And now we can use this to construct rules for a substitution system:

Applying this substitution system builds up a nested tiling that can be continued forever:

But is such a nested tiling the only one that is possible with our original tiles? We can prove that it is by showing that every tile in every possible configuration occurs within a supertile. We can pull out possible configurations from the multiway system—and then in each case it turns out that we can indeed find a supertile in which the original tile occurs:

And what this all means is that the only infinite paths that can occur in the multiway system are ones that correspond to nested tilings; all other paths must eventually die out.

The Penrose tiling involves two distinct tiles. But in 2022 it was discovered that —if one’s allowed to flip the tile over—just a single (“hat”) tile is sufficient to force a nonperiodic tiling:

The full multiway graph obtained from this tile (and its flip-over) is complicated, but many paths in it lead (at least eventually) to “dead ends” which cannot be further extended. Thus, for example, the following configurations—which appear early in the multiway graph—all have the property that they can’t occur in an infinite tiling:

In the first case here, we can successively add a few rings of tiles:

But after 7 rings, there is a “contradiction” on the boundary, and no further growth is possible (as indicated by the red annotations):

Having eliminated cases that always lead to “dead ends” the resulting simplified multiway graph effectively includes all joins between hat tiles that can ultimately lead to surviving configurations:

Once again we can define a supertile transformation

where the region outlined in red can potentially overlap another supertile. Now we can construct a multiway graph for the supertile (in its “bitten out” and full variant)

and can see that there is a (one-to-one) map from the multiway graph for the original tiles and for these supertiles:

And now from this we can tell that there can be arbitrarily large nested tilings using the hat tile:

Personal Notes

Tucked away on page 979 of my 2002 book A New Kind of Science is a note (written in 1995) on “ Generalized aggregation models ”:

And in many ways the current piece is a three-decade-later followup to that note—using a new approach based on multiway systems.

In A New Kind of Science I did discuss multiway systems (both abstractly, and in connection with fundamental physics ). But what I said about aggregation was mostly in a section called “ The Phenomenon of Continuity ” which discussed how randomness could on a large scale lead to apparent continuity. That section began by talking about things like random walks, but went on to discuss the same minimal (“Eden model”) example of “random aggregation” that I give here. And then, in an attempt to “spruce up” my discussion of aggregation, I started looking at “ aggregation with constraints ”. In the main text of the book I gave just two examples:

But then for the footnote I studied a wider range of constraints (enumerating them much as I had cellular automata)—and noticed the surprising phenomenon that with some constraints the aggregation process could end up getting stuck, and not being able to continue.

For years I carried around the idea of investigating that phenomenon further. And it was often on my list as a possible project for a student to explore at the Wolfram Summer School . Occasionally it was picked, and progress was made in various directions. And then a few years ago, with our Physics Project in the offing, the idea arose of investigating it using multiway systems—and there were Summer School projects that made progress on this. Meanwhile, as our Physics Project progressed, our tools for working with multiway systems greatly improved—ultimately making possible what we’ve done here.

By the way, back in the 1990s, one of the many topics I studied for A New Kind of Science was tilings . And in an effort to determine what tilings were possible, I investigated what amounts to aggregation under tiling constraints—which is in fact even a generalization of what I consider here:

谢谢

First and foremost, I’d like to thank Brad Klee for extensive help with this piece, as well as Nik Murzin for additional help. (Thanks also to Catherine Wolfram, Christopher Wolfram and Ed Pegg for specific pointers.) I’d like to thank various Wolfram Summer School students (and their mentors) who’ve worked on aggregation systems and their multiway interpretation in recent years: Kabir Khanna 2019 (mentors: Christopher Wolfram & Jonathan Gorard) , Lina M. Ruiz 2021 (mentors: Jesse Galef & Xerxes Arsiwalla) , Pietro Pepe 2023 (mentor: Bob Nachbar) . (Also related are the Summer School projects on tilings by Bowen Ping 2023 and Johannes Martin 2023 .)