计算机构造（四） (2-1)

剩余的问题

在前面两节中我们表述了最基础的高阶计算模型的数学结构，并陈述了我们常见的两个计算模型，即基于图灵机的自然数上的可计算模型和基于 λ-calculus 的可计算模型，如何融入到我们所定义的数学框架中。但这仅仅是一个开始。在本篇文章的最后我们阐述一下在此基础之上我们还应该关心什么基本问题。这一节可以看作一个预告，里面提到的内容将会在下一篇文章中具体地阐述。

问题1：计算模型之间的关系？

首先，范畴的基本思想仍然指导着我们，一旦当我们定义了某种数学对象（比如我们这里定义的高阶计算模型），我们应该立刻关心这些数学对象之间的关系，即什么应该是它们之间的态射。在计算模型的语境下，两个计算模型之间的态射C → D 直观上来说应该对应着某种用 D 来模拟 C 中的计算的方式。在理解态射之后，进一步我们便可以询问什么情况下两个计算模型之间是等价的？

我们可以从上面所提到的两个计算模型的例子入手。在基础的可计算性理论中一个非常重要的结果便是，在 untyped[公式] -calculus 中定义的可计算函数和用图灵机定义的可计算函数是完全相等的——在我们的话语体系中更准确地应说它们定义了相同的可计算函数的外延。更具体一些，我们在 untyped λ-calculus 中可以定义形如 λf.λx.fⁿx 这样的闭项 [closed term] 作为数字 [numeral]，其中 fⁿx 是 将 f 作用在 x 上 n 次，即 f(f(· · · f(x))) 的简写。则在 untyped λ-calculus 模型中的可计算函数（即由某个项所表示的函数）和图灵可计算函数在外延上是完全一致的。

更进一步，从直观上来讲我们似乎也的确能够用其中一个模型来模拟另一个模型的计算。对于用自然数模型来模拟λ-calculus 的模型，我们只需要使用我们非常常见的编码手段，将 untyped λ-calculus 的语形用自然数编码，便非常容易能够看出 λ-calculus 上语形的操作能够用自然数的操作来进行模拟。但反过来也同样，对于任意自然数上的操作我们可以用前面定义的 λ-calculus 中的数字和闭项来模拟。因此直观上讲，对于这两个模型而言我们能够在一个模型中模拟另一个模型的计算。

但再继续深入地问，这样的双向模拟表示这两个计算模型之间是等价的吗？事实上，由前面的论述我们可以看出这两个模型也有许多非常不同的地方。比如在 untypedλ-calculus 当中所有的可计算函数全是完全函数，但在自然数模型中显然不是。它们到底是否是等价的，我们留到在下一篇文章中详细探讨。

问题2: 我们有没有类似代数拓扑中的不变量来描述计算模型之间的等价性？

在拓扑的语境下，我们一个很基本的问题是判断两个空间是否是同胚的。我们能够写下的所有连续函数都不构成同胚这件事并不能说明这两个拓扑空间之间没有任何的连续函数使得它们同胚，这个问题使用传统的办法是非常难以回答的。为了解决这个问题，在拓扑的语境下我们发展了代数拓扑的工具使得对于一个拓扑空间我们能够赋予其一系列代数的不变量；通过比较这些不变量，我们能够在某种含义的等价下（如同伦、弱同伦等价）判断两个拓扑空间是否属于同一个等价类。

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