计算机结构（一） (6-4)

为了说明高阶可计算性的概念与直观，我们这里将其和拓扑进行一个类比。很多人或许会认为拓扑是在研究空间的性质，但基于范畴的观点更加自然地描述或许是拓扑空间是在描述连续函数的性质。完全类似的，计算理论实际上是在研究可计算函数的性质。在拓扑空间的语境下，我们需要考虑什么是两个空间之间的连续函数；但更进一步，我们还需要知道如何连续地选择两个拓扑空间上的连续函数。因此自然地，连续性也本质上是一个高阶的概念，而连续的高阶性在现代拓扑中起着非常重要的作用。如果采用范畴的语言，无论是可计算性还是连续性，高阶的含义实质上是要求我们所考虑的某个范畴是 Cartesian closed 的（在可计算性中由于我们要考虑部分函数 [partial function] 因此所有的范畴结构我们都只考虑弱版本的，即泛性质 [universal property] 只考虑存在性而不考虑唯一性）。对于所有的拓扑空间我们没有一个很好的解决方案，因为 Top 这个范畴并不是 Cartesian closed 的；但如果局限在紧致的 Hausdorff 空间下我们可以拓扑化两个拓扑空间之间连续函数所构成的空间，这个构造对高阶的连续性作出了一个很好的解答。在可计算性的语境下，我们也需要类似的 Cartesian closed 的结构来模拟高阶的可计算性。

为什么考虑可计算性时我们一定需要考虑高阶的可计算结构呢？其原因是多样的。在这里我们仅仅讨论两个和数理逻辑以及可计算理论最相关的原因。

首先，让我们对可计算函数的外延和内涵做一个区分。如果我们简单地采用程序语言的叙述方式，在某种意义上我们可以说任何一段输入输出均是自然数的程序都定义了一个部分可计算函数 [partial computable function]。但从直观上来讲，这一段程序比这一个单独的部分可计算函数包含了更多的信息，因为一段程序不仅仅能够给出正确的结果，它还包含了如何具体计算这个函数的步骤与方式。从另一个角度来讲，我们可以有另一段完全不一样的程序使用了另一种计算方式，但它们计算的是同一个部分可计算函数。换句话来说，尽管我们经常把程序和可计算的函数等价起来，在观念的层面它们是不一样的：一段程序是有内涵的 [intensional]，其对应的那个部分可计算函数仅仅表征了这一段程序的外延 [extension] 而已。因此，如果只单纯地考虑从ℕ 到 ℕ 的可计算函数这个集合，我们是仅仅在外延的层面考察可计算性，而忽略了其内涵。

对于大多数的编程语言，特别是许多现代的函数式编程语言比如 Lisp, Haskell 或者是 Lean，它们都支持将它们本身的一段程序作为数据而对它们进行编程和各种操作；直观地来说，它们都在它们的语言中包含了一份自身 [contains a copy of themselves]。在这些语言中，输入输出为 ℕ 的程序本身也能够成为输入和输出来考虑其上的可计算性。因此对这些编程语言而言，仅仅考虑可计算函数的外延是不够的。计算函数的内涵性往往是通过高阶可计算性来刻画和表达的。换句话说，在我们的高阶计算模型中，前面提到的 ℕ ⇒ ℕ 这个集合并不是所有从 ℕ 到 ℕ 的可计算函数的外延构成的集合，而是它们的内涵构成的集合。因此，如果我们想要刻画这一类编程语言的抽象结构，考虑高阶计算性是不可或缺的。高阶可计算模型的研究也的确有很大一部分是为了解决和许多程序语言的计算语义相关的问题。

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