计算机结构（一）

可计算性不总是基于自然数

我相信如果大家了解过一些递归论或者是可计算理论的内容，大多都会有一个模糊的印象，认为计算理论研究的是从ℕ 到 ℕ 的一个函数什么时候是可计算的，或者与之类似的相关问题。这个印象不能说是错的，对于自然数上可计算函数的研究的确是可计算性理论刚兴起时非常重要的内容。但在我们日常生活中或者在面对许许多多的数据结构的时候，这真的是我们唯一的对可计算性这个概念的理解方式吗？

首先，我们似乎不仅仅关心ℕ 上的可计算性问题。或许首先一个比较微不足道的观察是，在计算机理论中我们对 ℕ 有不同的表示方式，比如经常采用的是二进制数。因此严格来说，此时可计算性和可计算函数所基于的对象变成了 {0，1}* ，即 01-字符串构成的集合。当然，很多人会说这两者没有本质的区别，因此采用哪一个发展可计算性的理论没有关系；我们的经验也的确支持这种看法，因为它们二者是同构的。

但我们在日常生活中遇到的例子不是都像改变自然数的进制这样微不足道的。比如在编程中或者在理论计算机的研究中，我们经常遇见的情况是我们所想要考虑可计算性的数据集合上有更多的结构存在：比如在数据结构中我们经常使用树、图或者是表这样类型的数据结构，这些结构本质上和自然数的结构是不同的。如果采用递归类型 [inductive type] 或者是许多函数式编程 [functional programming] 语言中的表示方式，自然数ℕ 可以看作是如下的递归类型：

inductive N : Type :=

| zero : N

| succ : N -＞N

换句话说，ℕ 的结构是由 0 和后继函数 [successor function] 递归生成的自由结构。我们同样可以类似地定义二元树的数据类型：

inductive Btr : Type :=

| leaf : Btr

| node : Btr -＞Btr -＞Btr

可以看见的是，二元树的递归生成方式是和ℕ 不同的。自然数生成的方式是给定一个自然数，生成一个其后继；而二元树是给定两个二元树，可以通过一个点将二者连起来形成一个新的二元树。我们还有许多其他的递归数据类型，其上的结构也自然和二元树与自然数都是不同的。但几乎在任何一个高级编程语言中，我们都可以编写输入为自然数 ℕ 输出为二元树类型的程序；根据 Church-Turing Thesis, 所有由这样定义的函数都应是可计算的。因此，尽管 ℕ 和二元树的数据结构不同，我们仍然可以谈论什么是不同数据结构之间的可计算函数，并且对此具有一定的直观。

在一般的可计算理论分析中，我们解决上面这个问题的方式是考虑从一个结构到另一个结构的编码 [coding]。比如对于上面 ℕ 和二元树的数据结构，我们很容易看出来的是我们可以用二元树编码自然数。比如我们可以令满的二元树代表自然数，其层高对应着自然数的值；原则上，自然数的任意操作都可以在这套编码下采用二元树的操作来表达。但在实际的理论研究中我们更加熟悉的是用自然数来编码二元树。自然数这个集合是非常丰富的，其上的操作可以编码我们遇到许多数据结构。从某种程度上，这也是我们在可计算理论中主要考虑自然数上的可计算函数的原因之一。大家脑海中或多或少都会认为，由于这些编码函数的存在，我们只需要有了自然数这个结构上的可计算理论，其他的可计算函数均可以通过各种不同的编码来实现。

但这样对待可计算性理论的方式是有些不自然的。首先，采用编码的方式其实严格意义上并不能完全地解决我们的问题。如果我们使用自然数来编码二元树，通常的编码方式是找到一个从二元树到自然数的单射（或双射）Btr -＞N。通过这个编码函数，我们便可以将自然数上的可计算性概念迁移到二元树这个结构上。但为了使这个方法成立，我们必须要求这个编码函数本身是可计算的！如果我们选取了一个本身不可计算的编码函数，那么一个根据 Church-Turing Thesis 不可计算的二元树上的函数 Btr -＞Btr，根据这个编码转换成自然数上的函数后其也可能变成是可计算的。因此，为了选取一个合理的编码，从概念上我们还是无法逃脱需要首先知道什么是从二元树到自然数的可计算函数。

当然，在实际的可计算理论中，我们之所以可以不用发展更为一般的从二元树到自然数的可计算理论的原因是我们能找到许多直观上可计算的编码函数；一旦我们确定了这样一个编码，似乎我们就可以绕过上面这个问题了。但是，如果我们回到可计算性观念的层面，这样任意选取的编码函数对于我们理解可计算性这个概念的作用是微乎其微的。从更大的层面上来讲，可计算性这个概念没有任何先验的理由是特殊针对自然数 ℕ 的；对非常广泛的一类数学结构我们都能够非常直观地谈论它上面的可计算性，特别是在默认了 Church-Turing Thesis 成立的条件下。

另外从技术的角度，许多现代对于计算这个概念的发展和研究所基于的数学对象和结构并不全都能够用自然数来进行编码了。例如在最近十多年发展得越来越多的基于余代数 [coalgebra] 或者自动机 [automata] 来模拟的无穷计算 [infinite computation]，其考虑的就是诸如ℕℕ 这一类集合上的可计算性。再或者我们想要模拟物理世界的可计算性，我们需要考虑的是在无穷时间的延伸下可能发生的各个物理事件之间的集合上的可计算性。和之前的二元树或其他的递归定义的数据结构不同的是，这些集合都不再是可数的了，因此用自然数编码来研究这些集合结构上的可计算性是根本行不通的了。这些无穷计算不仅仅是有理论研究价值的，目前一些函数式编程语言早已支持对这些无穷的数据进行编程操作了（如 Haskell 中非常重要的 lazy 特性就能够支持这一点）；另外，如果我们考虑人和计算机之间的交互，我们在一连串时间中不断按下的键盘和点击的鼠标也可以被模拟成在连续时间上的无穷事件。这些应用也都侧面地印证了，考虑这些不可数集合上的计算结构同样是重要的。

回到观念的层面上来看，我们所需要的是一个更加广泛与抽象的框架来研究与描述一般对象上的可计算性概念，而不仅仅是聚焦在自然数这单单一个集合上。此处可以跟我们对一般空间的研究做一个类比。我们对几何的研究有非常深的历史，早在古希腊我们对平面几何和立体几何就有了非常多的知识。但所有的这些知识都是对某几个空间中的某几类几何结构作出的描述，因此它们都可以看作是我们对某一些常见的数学对象所收集的知识。但我们对空间——或者以范畴论的视角来看，连续性——这个抽象概念的一般认识是要到在数学中发明了一般拓扑空间的这个抽象概念之后才真正有了质的突破。正因如此，拓扑这个概念在现代数学中的重要性怎样强调似乎也不为过。事实上，可计算性和连续性这两个概念有着千丝万缕异常紧密的联系，这个联系也是我们介绍的这本书中的一大主题。但限于篇幅，在这篇文章中或许我们没有机会提到了，只能如此非常粗略地告诉大家这个结论而已。与几何的发展完全类似的是，在可计算性领域许多顶尖的数学家以及逻辑学家，包括 Turing、Church、Kleene 等的工作之后，我们收集了许许多多的对于某些具体的计算模型的知识，并对于它们之间的关系有了很多初步的结果。但我们目前缺乏的是如同拓扑的概念一样谈论一般可计算性概念的抽象框架。基于拓扑的概念，我们能够谈论一般空间之间的连续函数；同样的，我们或许也需要有一个对可计算性的一般框架来考虑一般不同数据结构之间的可计算函数，同时比较不同计算模型之间的关系。

从某种意义上来说，我们介绍的这本书初步地解决了上面的这个问题。在书中给出了一般抽象意义上的计算模型的定义，并据此研究了一般可计算函数的性质。根据上一段的描述，书中自然地采取了范畴的框架。在这篇文章中我们并不会介绍书中给出的计算模型的具体数学定义；这将会是下一篇文章的内容。接下来我则会继续探讨一下对于可计算性这个概念其他方面的反思。

可计算性是一个高阶的概念

我们这次介绍的这本书的名字叫 Higher-Order Computability，即高阶可计算性。高阶可计算性的含义是，如果对于两种不同的数学结构A，B 我们有了什么是从 A 到 B 的可计算函数的概念，则我们同样需要考虑的是某种函数空间 A ⇒ B（目前可以粗略地看作所有从 A 到 B 的可计算函数集合）上的可计算性。比如，我们希望知道以什么方式选择一系列从 A 到 B 的可计算函数其本身是可计算的；采用更加数学化的语言，即我们同样想要了解什么是 ℕ 到 A ⇒ B 的可计算函数。当然完全类似的，我们还可以考虑相应更高阶的可计算性，如集合 ℕ ⇒ (A ⇒ B) 上的可计算性。

为了说明高阶可计算性的概念与直观，我们这里将其和拓扑进行一个类比。很多人或许会认为拓扑是在研究空间的性质，但基于范畴的观点更加自然地描述或许是拓扑空间是在描述连续函数的性质。完全类似的，计算理论实际上是在研究可计算函数的性质。在拓扑空间的语境下，我们需要考虑什么是两个空间之间的连续函数；但更进一步，我们还需要知道如何连续地选择两个拓扑空间上的连续函数。因此自然地，连续性也本质上是一个高阶的概念，而连续的高阶性在现代拓扑中起着非常重要的作用。如果采用范畴的语言，无论是可计算性还是连续性，高阶的含义实质上是要求我们所考虑的某个范畴是 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]。在这些语言中，输入输出为 ℕ 的程序本身也能够成为输入和输出来考虑其上的可计算性。因此对这些编程语言而言，仅仅考虑可计算函数的外延是不够的。计算函数的内涵性往往是通过高阶可计算性来刻画和表达的。换句话说，在我们的高阶计算模型中，前面提到的 ℕ ⇒ ℕ 这个集合并不是所有从 ℕ 到 ℕ 的可计算函数的外延构成的集合，而是它们的内涵构成的集合。因此，如果我们想要刻画这一类编程语言的抽象结构，考虑高阶计算性是不可或缺的。高阶可计算模型的研究也的确有很大一部分是为了解决和许多程序语言的计算语义相关的问题。

高阶可计算性以及对可计算函数内涵和外延的区分，更是直接地与直觉主义逻辑的构造性或可计算性阐释息息相关，因此它对数理逻辑的研究也非常的重要。从高阶可计算性研究的历史来讲，的确也有很大一部分贡献和发展来自于对数理逻辑中直觉主义逻辑相关的研究。直观上来讲，我们常常声称直觉主义逻辑有某种构造性阐释，即某个命题在直觉主义逻辑下可证明当且仅当我们能够给出某种构造来直接地验证或说明它是正确的。在现代数学的语境下，构造数学 [constructive mathematics] 和直觉主义数学 [intuitionistic mathematics] 在很多时候是作为同义词被大多数数学家使用的。例如，在直觉主义的构造性阐释下，对于推出连接词A → B 的证明或构造指的是一个把 A 的证明或构造转化成 B 的证明或构造的一个程序。但在这种解释下，如果没有对高阶可计算性的刻画我们是无法理解有嵌套的推出连接词，如 (A → B) → C 等公式的构造性解释的：套用前面的说法，对 (A → B) → C 的一个证明是一个把将 A 的证明转化到 B 的证明的程序转化为 C 的证明的程序（这句话用自然语言写出来非常难读，正是因为其涉及可计算性的高阶嵌套）。对于涉及到多个存在量词嵌套时直觉主义逻辑公式的构造性解释也完全类似。为了能够给这些嵌套的直觉主义逻辑公式一个严格地构造性阐释，有一个准确的语言来描述高阶的可计算性是必要的。

比较不同计算模型之间的关系

本文的最后一节我们来探讨一下不同计算模型之间的关系。在上世纪三十年代，Turing、Church、Kleene 等人的工作让我们非常惊讶地发现，许许多多完全不同的定义ℕ 上可计算函数的方式所给出的是完全一样的同一族函数。Church 对于可计算函数的刻画是基于 λ-calculus 的，其中对数字和可计算函数的表示都是基于 λ-calculus 中的项 [terms]，是一个完全从语言和语形出发给出的构造。Turing 定义的图灵机则有完全不同的直观，它是基于某种特殊的物理可实现的机器，这些机器也被称为图灵机 [Turing machine]。而 Kleene 创立的递归论则是一个从复合 [compositionality] 和递归 [recursion] 结构出发的进路。事实上我们还有许许多多的计算模型，比如和现代计算机更加接近的基于暂存器 [register machine] 的计算结构，或者从纯逻辑的证明角度出发基于一阶算数系统的计算结构。所有关于这些计算模型的讨论可以参见[2]。令人震惊的是，这些看似完全不同——有着完全不同直观且基于完全不同的出发点——的计算模型所最终定义的可计算函数是完全一样的！这个事实也可以看作是可计算性能够作为一个数学中值得研究的抽象概念存在的最有力证据。

但值得注意的是，这里我们所谓的这些不同的计算模型给出完全一样的可计算函数指的是在外延的层面上。换句话说，从 ℕ 到 ℕ 的部分可计算函数这个外延集合具有非常高的鲁棒性。但这些不同的计算模型给出相同的可计算函数外延是否真的表明这系计算模型是等价的？这个问题从我刚开始接触可计算理论就一直困惑着我；直到我看到这本书，才感到有一个足够普遍的数学理论框架能够真正意义上对这个问题进行一个回答。

首先，现代数学或者说范畴论的经验告诉我们，要回答关于等价的问题，事实上是要回答态射的问题（顺嘴一提，这一点也说明有等价这个概念的地方就有范畴论的身影，如果再推广到无穷范畴则是有若等价这个概念的地方就有无穷范畴的身影；这从侧面解释了为何范畴和无穷范畴能够作为现代数学的语言而存在）。在可计算性的语境下，我们要考虑的态射则应该是某种模拟 [simulation]，即在一个计算模型中能够作出的计算能否平行的用另一个计算模型来进行模拟。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。