递归函数(七)

乍一看,这样的�似乎是以循环方式定义的,因此,从表面上看,也不清楚为什么这样的程序必须存在。事实上,Soare (2016: 28–29) 指出,前述递归定理的证明“非常简短但神秘”,并且“最好将其视为失败的对角线论证”。为了澄清这一评论和证明,考虑图 1 中所示的矩阵,其行��不是枚举部分可计算函数的值,而是函数本身——即,行��将包含函数���(0)、���(1),…,并且如果��(�)↑,则���(�)表示完全未定义的函数。(这种描述最初归功于 Owings 1973 年。)

��0(0)��0(1)…��0(�)…��0(��)…��0(ℎ�(�))…��1(0)��1(1)…��1(��)…��1(�)…��1(ℎ �(�))…⋮⋱⋮���(0)…���(�)…���(�)…���(ℎ�(�))…⋮⋱⋮���(0)……���(�)...���(�)...��� (ℎ�(�))…���(ℎ�(�))…⋮⋱↑��ℎ�(�)(0)……��ℎ�(�)(�)…��ℎ�(�)(�)…��ℎ�(�)(ℎ�(�))…≃⋮⋱↓��ℎ�(�)(0)……��ℎ�(�)(�)…��ℎ�(�)(�)…��ℎ�(�)(ℎ�(�))…��ℎ�(�)(ℎ�(�))…⋮

图 1:递归定理 (3.5) 证明中使用的部分可计算函数矩阵

我们可以认为定理 3.5 中给出的函数 �(�) 在行上诱导变换,从而 �� 映射到 ��(�)。为此,让 ℎ�(�) 成为与 �� 组成的总可计算函数的索引,这样我们就有

�ℎ�(�)(�)≃�(��(�))

接下来考虑这个矩阵的对角线——即 �=��0(0),��1(1),…

由于组成 � 的函数的索引是有效给出的,因此 � 本身必须对应于某行 ��——即

(32)���(�)(�)≃���(�)(�) 对于所有 �∈�

但现在考虑 �� 在 � 下的图像——即行 �ℎ�(�)=��ℎ�(�)(0),��ℎ�(�)(1),… 从 (32) 可知我们必须有

(33)���(ℎ�(�))(�)≃��ℎ�(�)(ℎ�(�))(�)

但请注意,根据 ℎ� 的定义,�ℎ�(�)(ℎ�(�))=�(��(ℎ�(�)) 因此也从 (33)

(34)���(ℎ�(�))(�)≃��(��(ℎ�(�))(�)

但现在请注意,由于 �、�� 和 ℎ� 都是总数,因此值 ��(ℎ�(�)) 是定义的。因此,设置 �=��(ℎ�(�)) 从 (34) 可知 ��(�)≃��(�)(�) 如所期望的那样。

如上所述,递归定理通常可用于呈现传统上描述为的结果的紧凑证明涉及自指。例如,一个直接的结果是,对于每个�(�),都有一个�使得��=��(�)。要理解这一点,请注意定理 3.5 意味着存在这样一个�,使得对于每个可计算的�(�),��(�)≃��(�)。但由于函数的定义域必须重合,因此��=��(�)。

记录递归定理的以下替代形式很有用:

推论 3.2:对于每个部分可计算函数�(�,�),都有一个指标�使得��(�)≃�(�,�)。

证明:根据 s-m-n 定理 (3.1),对于某个�,�(�,�)≃��12(�,�)(�)。但是,通过将定理 3.5 应用于 �12(�,�),可以得出所需的 � 的存在。 □

下面是利用此公式得出的一些上述精神的简单推论:

有一个数 � 使得 ��(�)=�+�。(这可以通过在推论 3.2 中取 �(�,�)=�+� 得出。类似的观察得出 � 的存在,使得 ��(�)=�×�,��(�)=��,等等。)

有一个数 � 使得 ��={�}。(在推论 3.2 中取

�(�,�)={0if �=�↑otherwise

。)

考虑一个术语 �,它对应于一个“程序”,它确定具有索引 ⌜�⌝ 的部分可计算程序(如第 2.2.2 节所述)。如果对于所有输入�,� 的计算结果为� 的输出为⌜�⌝,则我们称这样的程序是自复制的。由于为了构造�,我们似乎需要提前知道⌜�⌝,因此似乎不需要存在自复制程序。但是请注意,换回我们的官方术语,这种程序的存在等同于存在一个数字�,使得��(�)=�。通过将推论 3.2 应用于函数�(�,�)=�,可以保证这一点。

有关递归定理在自指和可计算性理论中更高级应用方面的进一步讨论,请参见 Cutland (1980: ch. 11)、Rogers (1987: ch. 11)、Odifreddi (1989: ch. II.2) 和 Y. Moschovakis (2010)。

在结束递归定理之前,最后有必要思考一下它与第 1 节和第 2 节中讨论的递归可定义性的一般概念的关系。例如,考虑一个简单的定义,如

(35)ℎ(0)=�ℎ(�+1)=�(ℎ(�))

在�(�) 为原始递归的情况下,我们已经指出,可以通过外部集合论论证证明存在一个满足 (35) 的唯一函数ℎ(�)。但我们也可以考虑这样一种情况,即假设�(�) 相对于某种计算模型�是可计算的,这种计算模型不同于原始递归函数,因为它本身并不支持递归作为一种计算模式——​​例如,图灵机模型�或无限寄存器机模型�。如果我们简单地将 (35) 作为这种情况下的定义,那么即使�(�) 是可计算的,我们也无法先验地保证ℎ(�) 相对于�是可计算的。

然而,经过检查,很明显,定理 3.5 的证明所依赖的计算模型的唯一特征是存在一个索引,而 s-m-n 定理 (3.1) 的一个版本可用于该索引。如果 � 满足这些条件,则 ℎ(�) 相对于 � 可计算的说法等同于 ℎ(�)≃��(�),其中 � 是从 � 可计算函数的某些适当索引中得出的索引。但由于 � 的 s-m-n 定理允许我们将索引视为变量,我们也可以考虑由以下函数定义的函数

�(�,0)=��(�,�+1)=�(��(�))

现在请注意,推论 3.2 再次保证了 � 的存在,使得 �(�,�)≃��(�)。这反过来得出

��(0)=���(�+1)=�(��(�))

这说明了满足递归定义(如 (35))的可计算函数的存在如何从递归定理得出,即使我们一开始没有将“可计算函数”描述为第 1 节中讨论的非正式意义上的“递归”定义的函数。这反过来有助于解释为什么定理 3.5 被称为递归定理。

3.5 可约性和度数

当代可计算性理论的一个中心主题是相对可计算性的研究——即,如果我们假设我们能够决定给定集合中的成员资格或计算给定函数,那么我们能够决定或计算哪些其他集合或函数?这个问题可以用将一个集合�归约到另一个�的概念来研究,这个概念是由柯尔莫哥洛夫(1932)非正式地提出的,作为将�的“解”转化为�的“解”的一种手段。[25] 图灵(1939)在他的序数逻辑研究中首次正式定义了计算归约。然而,波斯特在他影响深远的论文“正整数的递归可枚举集及其决策问题”(1944)中首次提出系统地研究可归约性概念及其相关的度结构。

波斯特在其中解释了归约的基本思想及其重要性如下:

与问题可解性或不可解性问题相关的是一个问题可归约或不可归约到另一个问题。因此,如果问题�1 已归结为问题�2,则�2 的解立即产生�1 的解,而如果证明�1 不可解,则�2 也必定不可解。对于不可解问题,可归结性概念导致不可解度概念,如果两个不可解问题各自可归结为另一个,则它们具有相同的不可解度;如果一个可归结为另一个,但另一个不能归结为另一个,则它们具有比另一个更低的不可解度;如果两个都不能归结为另一个,则它们的不可解度无法比较。递归可枚举集理论的一个主要问题是确定其中不可解决策问题的不可解度。我们很快就会看到,对于这样的问题,肯定存在最高的不可解度。我们的整个发展主要集中在一个问题上:在这些问题中,是否存在比这更低的不可解程度,或者它们是否都具有相同的不可解程度。(Post 1944:289)

为了理解这段话,再次将集合�⊆�视为与决定�中成员资格的问题相关联是有用的——例如,给定一个自然数�,�是素数吗?(即�∈PRIMES?)或者输入�的第�个部分可计算函数是否定义?(即�∈�?)。但即使有了这种对应关系,问题�的解“立即产生”�的解这一断言仍然可以用多种不同的方式来分析。其中两种最重要的可能性如下:

假设存在一种用于决定形式为�∈�的问题的算法,那么就可以指定一种用于决定形式为�∈�的问题的算法。

假设我们能够使用一个“神谕”,它能够在一个步骤中回答任意形式为�∈�的问题,那么就可以指定一个使用该神谕来决定�∈�的算法。

这些问题之间关系的形式化导致了多一可约性和图灵可约性的概念,它们对“� 不比 � 难解,且 � 的不可解性 (或难度) 程度等于 �”这两个概念提供了截然不同但互补的分析。[26] 后一个概念在历史上最早出现,由图灵 (1939) 提出,克莱恩 (1943) 提出了一个等效形式。然而,正是波斯特 (1944) 不仅提出了前一个概念,也开启了对图灵可约性的普遍研究。事实上,上面引用的段落的最后一句话描述了一个关于图灵度的重要技术问题,它将影响可计算性理论的早期发展(即下面问题 3.1 中给出的“Post 问题”)。

3.5.1 多一度

我们已经在 Rice 定理 (3.4) 的证明中看到了多一可归约性的一个例子。具体来说,证明表明,确定 � 中的成员资格的问题可以归结为确定任何非平凡索引集 � 中的成员资格的问题,其含义如下:对于所有 �,如果 �∈�,则 �12(�,�)∈�。因此,如果存在一种确定 � 中成员资格的算法,我们就可以通过使用它来测试 �12(�,�)∈� 来决定 �∈�。因此,函数 �12(�,�)(其可计算性由 s-m-n 定理给出)是所谓的 � 到 � 的多一约化。

正式定义将此示例概括如下:

定义 3.3:给定集合 �,�⊆�, � ,如果存在可计算函数 �(�) ,使得对于所有 �∈�,

�∈� 当且仅当 �(�)∈�,则称其为多一(或 m-一)可约化为 �

在这种情况下,我们写为 �≤��。

使用此符号,前面的示例因此表明 �≤��。这些观察结果可以概括如下:

命题 3.5:假设 �≤��。

如果 � 是可计算的,那么 � 也是可计算的。

如果 � 是可计算枚举的,则 � 也是可计算的。

通过与命题 3.5 相对照,可以得出,为了证明集合 � 是不可计算的(或非 c.e.),只需证明存在一个已知的不可计算的(或非 c.e.)�,使得 � 可以多一约化为 �。例如,假设我们首先证明了对角线停机问题 �={�:��(�)↓}=� 是不可计算的。然后,为了证明停机问题 HP={⟨�,�⟩:��(�)↓}=� 也是不可计算的,只需注意到 �(�)=⟨�,�⟩——即 � 与自身的可计算配对函数——是一个多一约化,表示 �≤�HP。

可约性概念通常还带有一个相关概念,即指定集合相对于一类集合而言是完整的,即类中的每个集合都可以归约成一个集合,并且该集合本身是该类的成员。作为初始示例,我们有以下内容:

定义 3.4:仅当以下条件成立时,集合 � 才被称为对可计算可枚举集的多一(或 m )完整的:

� 是可计算可枚举的;

对于所有可计算可枚举集 �,�≤��。

完整 c.e. 集的一个明显例子是 HP。因为 HP={⟨�,�⟩:∃��1(�,�,�)} 并且 �1(�,�,�) 是可计算关系,所以根据命题 3.2,HP 是 c.e。另一方面,如果 �=��,则 �∈�当且仅当 ⟨�,�⟩∈HP,从而表明 ��≤�HP。

尽管如此,标准做法是将 � 而不是 HP 作为规范的完全 c.e。虽然乍一看 � 似乎比 HP 包含“更少的计算信息”,但不难看出 � 也是这样的,每个 c.e. 集都可以 m 约化为它。假设�=��,我们可以定义一个函数

�(�,�)={1 if ��(�)↓ (即 �∈�)↑否则

由于 �(�,�) 显然是部分可计算的,s-m-n 定理 (3.1) 给出了一个完全递归函数 �12(�,�) 使得 �(�,�)≃��12(�,�)(�)。然后我们有

�∈� ⇔ ��(�)↓ ⇔ ��12(�,�)(�12(�,�))↓ ⇔ �12(�,�)∈�

这些双条件成立,因为 ��(�)↓ 只在 ��12(�,�)(�) 为 const1(�)(即常数 1 函数)的情况下成立,而不是 ��12(�,�)(�12(�,�))↓ 为处处未定义的函数。但由于后一个条件等同于 �12(�,�)∈�,�12(�,�) 是一个多一归约,表示 �≤��。

这说明,在某种意义上,确定 � 中的成员资格也可以理解为可计算可枚举集的通用性,或者,没有比 � 更“难”解决的 c.e. 集。尽管如此,有些问题比�更难解决,即使我们拥有�的决策算法,也无法解决这些问题。例如,从下面给出的结果可以看出,虽然�可以m-约化为TOT,但TOT不能m-约化为�。这说明了如何使用m-约化来研究解决计算问题的相对难度。

这些考虑自然而然地导致了难度的概念——另一个可以根据不同的可约化概念精确化的概念。多一可约化的版本由以下定义给出:

定义3.5:如果�和�可以多一约化为彼此——即�≤��和�≤��——那么我们说�和�是多一等价的,我们写为�≡��。

(本章完)

相关推荐