规模可变的可逆因果图动力学

《Theoretical Computer Science》：Size-varying reversible causal graph dynamics

　　

# 摘要

考虑一个按照可逆的最近邻动力学演化的网络。动力学是否被允许改变网络的大小？一方面，节点似乎是信息的载体，因此如果不保持双射性，节点就不能被破坏。另一方面，从图集合到图集合存在大量不保持顶点的双射函数。这个问题已经以否定的方式得到解决——基于三个不同的理由。然而，在本文中，我们在三种放宽的设置下获得了可逆的局部节点创建/破坏，并证明了这三种设置的等价性以增强结果的稳健性。我们的工作既有理论计算机科学方面的动机（可逆计算、元胞自动机的扩展），也有理论物理学方面的考量（通向离散量子引力的基本形式化框架）。

# 引言

元胞自动机（CA）由 $\mathbb{Z}^n$ 网格上的相同单元组成，每个单元可取状态集 $\Sigma$ 中的状态，因此配置属于 $\Sigma^{\mathbb{Z}^n}$。单元的下个状态通过对单元及其邻居应用固定的局部规则 $f$ 同步且均匀地给出。CA 因此具有一系列类似物理的对称性：平移不变性（动力学在任何地方、任何时刻以相同方式作用）和因果性（信息传播速度有界）。CA 是公认的空间依赖计算模型之一：被广泛用于模拟空间依赖的计算问题（自复制机器、同步等）和多智能体现象（交通堵塞、人口学等）。但它们的起源在于物理学，在物理学中被不断用于建模波或粒子（例如作为偏微分方程的数值格式）。

由于量子力学和经典力学都是可逆的，为 CA 赋予这一另一种类似物理的对称性是自然的。可逆元胞自动机（RCA）的研究进一步得到了可逆计算具有更低能耗的承诺所推动。RCA 已经发展出了优美的数学理论，该理论依赖于拓扑刻画，例如证明了 CA 的逆运算也是 CA [1]——由于 [2] 显然这是非平凡的。RCA 的另一个基本性质是它们可以表示为局部可逆置换或"块"的有限深度电路 [3]、[4]、[5]。

因果图动力学（CGD）[6]、[7]、[8]、[9]、[10] 是 CA 的双重扩展。首先，底层网格被扩展到任意有界度图。非正式地说，这意味着图 $G$ 的每个顶点可以取状态集 $\Sigma$ 中的一个状态，因此配置属于 $\Sigma^{V(G)}$，而边规定了演化的局部性：顶点 $v$ 的下个状态仅取决于由与 $u$ 的图距离至多为 $r$ 的顶点诱导的子图 $G_u$。其次，图本身被允许随时间演化。非正式地说，这意味着配置属于所有可能的有界度图 $G$ 的 $\Sigma^{V(G)}$ 的并集，即 $\bigcup_G \Sigma^{V(G)}$。这导致一个模型，其中局部规则 $f$ 同步且均匀地应用于输入图的每个子圆盘上，从而产生输出图的小贴片，这些贴片的并集构成输出图。图 1 说明了这一概念。

CGD 的动机源于大量具有最近邻相互作用且邻域随时间变化的情况（例如，智能体交换联系方式、四处移动等）。许多现有模型（复杂系统、计算机进程、生化智能体、经济智能体、社交网络等）都属于这一类别，从而针对各自的目的推广了 CA（例如 [11] 中的自复制，[12] 中的离散广义相对论 à la Regge 微积分等）。CGD 是这些模型的理论框架。一些图重写模型，如融合图变换 [13] 和并行图变换 [14]、[15]，也研究出了在图中同步应用局部重写规则的严格方法，尽管采用的是不同的、基于范畴论的视角，其中最接近的实例是 [10]。在 [16]、[17] 中，其中一位作者在可逆制度下研究了 CGD，即可逆 CGD。[18]、[19] 中已描述了可逆 CGD 的具体实例。

从理论计算机科学的角度来看，目标是将 RCA 理论推广到任意的、有界度的、随时间变化的图。确实，[16]、[17] 中的两个主要结果是上述 RCA 两个基本性质的推广。然而，结果仅限于（近乎）保持顶点的 CGD。我们表明可以解除这一限制。

从数学角度来看，与 CA 在某些图类上的双射性相关的问题（更具体地说，对于由某些群生成的凯莱图，前单射性是否蕴含满射性 [20]、[21]、[22]）受到了相当多的关注。另一方面，本文提供了一个研究"随时间变化的图上 CA 的双射性"的背景。我们回答了以下问题：双射性是否必然使空间僵化（即强制保持每个顶点）？我们的分析指出了导致这种僵化的假设——以及如何绕过它们。

从理论物理学的角度来看，微观物理（量子力学、牛顿力学）的可逆性能否与宏观物理（相对论）的随时间变化的拓扑协调一致，是一个重大挑战。本文提供了一个严格的离散玩具模型，在该模型中可逆性和随时间变化的拓扑共存并相互作用——以一种允许空间膨胀的方式。事实上，这些结果为量子因果图动力学 [23]、[24] 铺平了道路，允许顶点创建/破坏——这反过来可能为量子引力 [25]、[26] 提供一个严格的基本形式化框架。

# 章节节选

## 可逆性与节点创建/破坏之间的矛盾

**问题。** 考虑一个按照最近邻相互作用可逆演化的网络。它的动力学能否创建/破坏节点？

**问题 1。** 因为网络仅按照最近邻相互作用演化，相同的局部原因必须产生相同的局部效果。换句话说，如果节点 $u$ 的邻域看起来与节点 $v$ 的邻域相同，那么 $u$ 和 $v$ 处必须发生相同的事情。因此，节点的名称对于动力学必须是无关的。这当然最

## 简明概述：可逆因果图动力学

以下提供可逆 CGD 的直观介绍。严格的形式化见 [8]。

**网络。** 无论是图上的 CA [29]、多智能体建模 [30] 还是基于智能体的分布式算法 [31]，都常处理节点邻居有编号的图。因此我们的"图"或网络是通常的、连通的、无向的、可能有界度的图，但有一些额外约束：
- 每个顶点可用的端口集合 $\pi$ 是有限集。
- 该

**定义** 可逆 CGD 是保持顶点的。尽管如此，我们可以考虑使用它们来模拟不保持顶点的动力学，方法是区分"可见物质"和"不可见物质"，并确保每个可见节点都配备自己的"不可见"节点储备——从中可以提取。为了使该方案可以迭代，并且创建的节点能够创建更多节点，将储备设计为处处无限的二叉树是方便的。

**定义 9 不可见物质图** 考虑 $X = X_{\Sigma,\pi}$，$T = X_{\{\text{不可见}\},\{m,l,r\}}$

**匿名解** 拥有指针对于表达因果性是必要的，但在可逆性方面却很繁琐。获得两者优点的直接方法仅是考虑通过将因果动力学从 $X_{\Sigma,\pi}$ 投影到 $X^\circ_{\Sigma,\pi}$ 所得到的动力学。

**定义 14 匿名因果图动力学** 考虑 $X^\circ_{\Sigma,\pi}$ 上的函数 $F^\circ$。我们说 $F^\circ$ 是 ACGD 当且仅当存在 CGD $(F, R\bullet)$ 使得 $F$ 在 $X_{\Sigma,\pi}$ 上诱导 $F^\circ$ 在 $X^\circ_{\Sigma,\pi}$ 上。更正式地说，$F^\circ$ 是使得对于所有 $X \in X$，$F(X)^\circ = F^\circ(X^\circ)$ 的动力学。

**注 1** 平移不变性

**定义** 到目前为止我们一直在处理同构意义下的（标记）图，然而具名图在实现中更易于处理，并且在量子制度下甚至是必需的 [24]。在这种背景下，能够在不破坏局部性的情况下创建新顶点意味着能够仅从局部可用的名称生成新名称。例如，如果动力学 $F$ 将顶点 $u$ 分裂为两个新顶点，自然的选择是将这些顶点命名为 $u.l$ 和 $u.r$。现在，假设我们应用一个

# 结论

**贡献总结。** 先前的工作提出了并行可逆计算是否允许局部创建/破坏节点的问题。[6]、[7]、[16] 中给出了三个不同的否定答案。但我们刚刚描述了三种允许这种情况发生的放宽设置：全匿名化图上的因果图动力学（ACGD）；带有不可见物质储备的指针图模同构上的 CGD（IMCGD）；以及顶点名称在代数中的图上的 CGD。

# CRediT 作者贡献声明

Pablo Arrighi：审阅与编辑、原创草稿撰写、概念构思。
Amélia Durbec：原创草稿撰写、概念构思。
Aurélien Emmanuel：原创草稿撰写、概念构思。

# 利益冲突声明

作者声明以下可能被视为潜在利益冲突的财务利益/个人关系：

Amelia Durbec 报告获得 John Templeton Foundation 的财务支持。合作者 P.A. 是 Theoretical Computer Science 的编辑成员。如果还有其他作者，他们声明不存在可能影响本文所报告工作的已知的竞争性财务利益或个人关系。

Pablo Arrighi | Amélia Durbec | Aurélien Emmanuel