SEP：可计算性与复杂性（二） (5-1)

2.4 The Unsolvability of the Halting Problem

图灵问到，对于所有自然数集来说是否其都是可判定的。通过下面的计数论证，我们非常容易地就能知道答案是否定的。N有不可数数量的子集，但由于我们只有可数数量的图灵机，所以也只有可数数量的集合是可判定的。那么最后就是，多数集合都是不可判定的。

图灵实际上构造了一个不可判定集。如我们将看到的那样，他是通过运用对角线法(diagonal argument)来做到的。对角线法可以追溯到康托尔用其去表明实数是不可数的。哥德尔在他对不完备性定理的证明中，也用了一个相似的对角线法，他在数论中构造了这样一个句子J，这个句子的意思是，它本身不可证。

图灵如下地构造了一个对角线式停机集K：

K＝{n│Mₙ(n)↓}.

这是指K由那些，输入它们自己的程序后最终会停机的图灵机所组成。

不难看到，K是递归可枚举的。为了构造矛盾，假设，K也是共递归可枚举的，并让d为接受K的元素的一台图灵机的数。这样，对于任何n，n ∉ K ⇔ Md(n)↓

但考虑一下，当我们在上面用d代替n时会发生些什么：

d ∉ K ⇔ Md(n)↓

但K的定义告诉我们，

d ∈ K ⇔ Md(d)↓.

这样，我们就有了，

d ∈ K ⇔ d ∉ K

而这是一个矛盾，因此，我们对K是共递归可枚举的假设是错误的。也因此，K将不是递归的。这可以推出，对于一个给定的图灵机及其输入，并判定其最终是否能够停机的问题来说，这不是一个可计算问题，即，停机问题是不可解的。(译注：最先的定义告诉我们d属于K等价于Md输入d时停机，但因为，K是递归可枚举且共递归可枚举的，所以对于任何数n都可以使M停机而不管是其是否属于K，而当我们将d代到其不属于K的n的情况下时，其当然也可以停机，并等价推出d ∈ K，这样就出现了矛盾)

1. Primitive Recursive Functions

我们接下来定义*原始递归函数(primitive recursive functions)*的类(class)。这是一个非常有有意思的函数类，其由Skolem (1923)给出，并被哥德尔运用到了他对不完备性定理的证明中。我们关注于从Nʳ到N的函数f，对于r＝0，1，2，. . .，我们称r为函数f的元数，即其中变元的数目。哥德尔从三个非常简单的函数开始，初始函数，以及两个自然闭包运算，合成(composition)与原始递归，它们中都每一个都使用某个已经被定义好的函数，然后去定义一个新函数。下面我们将细节性地解释一下他的定义。这节将比较技术化，你跳过了也没啥关系。关键思想是，原始递归函数由一个非常大且强有力的可计算函数类组成，并且所有它们都以非常简单的方式被生成出来。

我们从三个初始的原始递归函数开始：

• ζ为，元数0的零函数(zero function)，ζ()＝0；

• η为，元数1的恒等函数(identity function)，η(n)＝n；以及

• σ为，元数1的后继函数(successor function)，σ(n)＝n＋1。

然后考虑下面两个运算：

• Composition：如果f是一个元数α的原始递归函数，以及g₁，. . .，gα为元数r₁，. . .，rα的原始递归函数, 并且k ∈ N，那么下面是一个元数k的原始递归函数：

h(x₁，. . .，xₖ)＝f(g₁(ω₁)，. . .，gα(ωα))

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