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

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

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

首先，我们似乎不仅仅关心ℕ 上的可计算性问题。或许首先一个比较微不足道的观察是，在计算机理论中我们对 ℕ 有不同的表示方式，比如经常采用的是二进制数。因此严格来说，此时可计算性和可计算函数所基于的对象变成了 {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, 所有由这样定义的函数都应是可计算的。因此，尽管 ℕ 和二元树的数据结构不同，我们仍然可以谈论什么是不同数据结构之间的可计算函数，并且对此具有一定的直观。

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