计算机构造（五） (5-4)

计算模型的集群范畴

我们提到了定义计算模型之间的模拟和转换后，也即定义了 Cmp 这个 2阶-范畴后，更进一步的问题。在我们现在的定义中，几乎所有出现的都是弱结构，在其他数学分支中较少见到，检验各个定义也比较繁琐。这也使得直接研究 Cmp 的结构变得比较困难。性质更好的数学结构，使得我们有从 Cmp 到这个结构的函子，能够反应计算模型的基本性质。这和我们在拓扑中寻找代数不变量的基本想法是非常类似的：一个拓扑空间可能是通过各种粘接和分割的操作构造而成的，其自身可能比较复杂；但当我们考虑这个空间上的代数不变量时，我们可以对这个空间的基本性质有非常好的描述。

在计算模型的语境下，这样的构造叫集群范畴 [category of assemblies]。对于任意一个计算模型 C ，我们可以构造它对应的集群范畴 Ass(C) 。限于篇幅，我们并不再详细地介绍集群范畴的具体定义了，只是在这里指出这个构造满足如下一些非常良好的性质：

• Ass(一) 的构造构成了一个从 Cmp 到 CAT 的 2阶-函子 [2-functor]（事实上，这个构造是从 Cmp 到 CAT/Set 的 2阶-函子）；

• Ass(C) 和 Ass(D) 之间的函子是从 C → D 之间的模拟生成的当且仅当其保持 Ass(C) 中一定的范畴结构；特别地， C 和 D 作为计算模型是等价的当且仅当 Ass(C) 和 Ass(D) 这两个范畴是等价的；

• Ass(C) 反映了计算模型 C 的结构： C 具有弱笛卡尔积结构、弱笛卡尔积闭结构、当且仅当 Ass(C) 是具有笛卡尔乘积、是一个笛卡尔闭范畴；

• 若 C 只有一个计算类型，即 T 是一个单点集 [singleton]，且其具有是弱笛卡尔积闭结构，则 Ass(C) 是一个伪拓扑斯 [quasi-topos]，且其能够进一步生成实现拓扑斯 [realisability topos]，这和直觉主义逻辑以及可计算理论之间有着十分深刻的关联；

直观上来说，Ass(C) 可以看作是由那些可以用 C 这个具体的计算模型表示的抽象数据结构 X 所构成的范畴。换而言之，它在某种意义上是所有那些可以通过计算模型 C 具体实现的抽象数据类型。这样构造的存在性和它具有的良好的数学性质从侧面印证了我们对于计算模型之间模拟和计算转换的定义是有实际数学意义的。通过研究范畴性质更好的集群范畴，我们可以对计算模型的性质有更好地把握。例如，我们可以通过集群范畴的性质判断之前提到的 C₁，C₂ 两个计算模型之间不是等价的。

集群范畴在其他方面还有更多的应用，此处我们也不过多展开了，感兴趣的读者可以去阅读原著 Higher-Computability Theory，或者是 Realizability: An Introduction to its Categorical Side.

结语

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。