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

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

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

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

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

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