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

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

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

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

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

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