计算机构造（三） (6-1)

在正式进入主题之前，我们先规定一些这篇文章讲要使用的符号。对于两个集合间的部分函数f：A → B 和任意 A 中的元素 α，α' ，我们规定：

• ↓f(α) 表示 f(α) 有定义， ↑f(α) 表示 f(α) 无定义；

• f(α)＝f(α') 表示 f(α)，f(α') 均有定义，且两者的值相等；

• f(α)≃f(α') 表示如果 f(α)，f(α') 二者之中一个有定义，则另一个也有定义，且这种情况下二者的值相等。

计算模型

在数学和计算机领域中，计算这个概念不总是基于自然数的。因此我们需要一个能够处理多种数据类型之间的可计算函数的理论框架。很自然的，不同的数据结构可以看作是不同的类型 [type]；我们假设我们有一个集合T ，其是所有数据类型名称 [type names] 的集合。例如如果我们只想考虑自然数和真值上的计算函数，集合 T 应就只包含两个元素 T＝{nat，bool} 。

我们将T 上的一个计算模型 C 定义为包含如下信息的对象：

• 其给出了以 T 为索引的一系列集合 |C|＝{C(τ)│τ∈T} ，其中每一个集合 C(τ) 都可以看作是类型 τ 下的数据集；

• 对于任意两个类型 σ，τ∈T ，其给定一个集合 C[σ，τ] ，其中的每一个元素都是从 C(σ) 到 C(τ) 的一个部分函数 [partial function]；

• 我们要求 C 在部分函数的复合操作下构成一个范畴。

简单地说，一个T 上的计算模型 C 便是一个对象集合同构于 T 的 Setp 的子范畴 [subcategory]，其中 Setp 是集合和部分函数所构成的范畴。注意，对于我们所关心的大多数计算模型而言， C 都不是 Setp 的一个满子范畴 [full subcategory]，因为一般而言不是所有从 C(σ) 到 C(τ) 部分函数都是可计算的。

这样的定义是符合我们对于可计算性的直观的。对于不同的数据类型，其必定对应着不同的数据集合作为它的值，这便是C(σ) 这些集合所代表的含义。当然，也有可能不同的类型对应着相同的（或同构的）数据集合；我们将在后面看到这一点。在不同的数据类型之间，显然一个从 σ 到 τ 的可计算函数应该至少为一个从 C(σ) 到 C(τ) 的部分函数。直观上来说，至少所有恒等映射应该是可计算的，且两个可计算函数的复合也应该是可计算的。因此，要求 C 构成一个范畴看起来是其构成一个计算模型的必要条件。从这个定义出发，我们来看看常见的一些计算结构如何融入到我们所定义的框架中来。

例子1: 自然数的计算模型. 从现有的研究来看，自然数应该算得上是最基础的计算模型了。我们能很自然地将其纳入上面的框架当中。此时的类型名称集合 T＝{nat} 只包含一个元素，且自然地我们有 C(nat)＝ℕ 。而对于态射我们自然也有 C[nat，nat] 是所有从 ℕ 到 ℕ 地部分可计算函数所构成的集合。容易验证其构成一个范畴。

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