递归函数(六)
这里函数���(�,�→)应该被认为是作用于�+�元部分可计算函数的索引�以及其第一个�个参数的值�→。此函数返回另一个部分可计算函数的索引,该函数通过执行 ���+� 确定 n 元函数,其第一个 � 参数 �→ 固定,但保留接下来的 � 变量 �→ 作为输入。虽然 s-m-n 定理的表述乍一看可能很技术性,但它的用法将在下面的 Rice 定理 (3.4) 和递归定理 (3.5) 的证明中得到说明。
范式定理的另一个推论如下:
定理 3.2:对于每个 �∈�,都有一个 �+1 元偏可计算函数 ��,它是通用的,因为对于所有 k 元偏可计算函数 �(�→),都有一个 �∈� 使得 ��(�,�→)≃�(�→)。
这直接由定理 2.3 得出,取 ��(�,�→)=�(����(�,�→,�)),其中 � 在 k 元偏可计算函数的枚举中使得 �(�→)≃���(�→)。由于 ��(�,�→) 可用于在其索引中均匀计算所有 k 元偏可计算函数的值,因此它通常被称为 k 元通用偏可计算函数。
值得注意的是,虽然我们刚刚为每个�定义了这样一个函数,但也可以定义一个二元函数�(�,�),它将第二个参数视为有限序列�0,…,��−1 的代码,然后以与 k 元通用函数相同的方式计算,因此我们有�(�,⟨�0,…,��−1⟩)≃��(�,�0,…,��−1)。这提供了一种用一元函数的单个枚举替换先前的 k 元偏可计算函数枚举的方法
�0(�),�1(�),�2(�),…,��(�),…
其中
��(⟨�0,…,��−1⟩)≃�(�,⟨�0,…,��−1⟩)≃���(�0,…,��−1)
定理 3.1 和定理 3.2 与定理 2.3 一起编纂了计算模型的基本属性,使其适合于开发可计算性的一般理论。在第 2 节中,这种模型已以偏递归函数的形式定义。但正如第 2.2.2 节末尾简要讨论的那样,也可以为第 1.6 节中讨论的其他计算模型获得这些结果的版本。这允许更自由地使用基于计算机的类比和其他诉诸丘奇论题的方法,这些方法在当代大多数可计算性理论的处理中都得到运用,在本条目的其余部分也将明智地加以运用。
3.2 不可计算函数和不可判定问题
刚刚看到有一个通用的部分可计算函数 �(�,�),一个自然的问题是这个函数是否也是可计算的(即完全可计算)。通过观察使用 �(�,�),我们可以定义另一个修改的对角函数 �(�)=�(�,�)+1,它是部分可计算的(因为 �(�,�) 是可计算的),可以立即得到否定的答案。这反过来意味着对于某个 �,�(�)≃��(�)。但现在请注意,如果�(�,�) 是全函数,则�(�) 将被定义,然后我们将得到
�(�)=��(�)=�(�,�)+1=��(�)+1,
矛盾。将这种情况与第 2.2 节开头描述的情况进行比较,我们可以看到部分可计算函数与原始递归函数的不同之处在于,它允许同一类中存在通用函数,但同时放弃了类中的函数必须是全函数的要求。换句话说,虽然�(�,�)∈PartREC,但第 2.2.2 节中的讨论表明�1(�,�→)∈REC−PR。
由于很容易看出最小化操作如何用于定义部分函数,因此上述观察结果是可以预料的。更令人惊讶的是,存在数学上定义明确的全函数,但它们是不可计算的。基于第 1.7 节中对判定问题的讨论,这种函数最著名的例子来自图灵机模型中所谓的停机问题(参见图灵机条目)。图灵 (1937) 最初将其表述如下:
给定图灵机的索引 �0,�1,…,机器 �� 是否会在输入 � 时停止?
也可以用部分递归函数来表述等效问题:
部分可计算函数 ��(�) 是否针对输入 � 定义?
对应于该问题的肯定答案的自然数对 ⟨�,�⟩ 确定了 �×� 的子集,如下所示:
HP={⟨�,�⟩:��(�)↓}
如果一个集合(或问题)的特征函数不可计算,则该集合(或问题)被称为不可判定的。例如,设 ℎ(�,�)=�HP(�,�),并观察到根据定义,这是一个全函数。停机问题的所谓不可判定性现在可以表述如下:
定理 3.3:ℎ(�,�) 不是可计算函数。
证明:假设存在矛盾,ℎ(�,�) 是可计算的。考虑函数 �(�) 定义为
�(�)={0if ℎ(�,�)↓=0↑otherwise
假设 ℎ(�,�) 是可计算的,则 �(�) 是部分可计算的,因为例如,它可以由一个程序计算,该程序在输入 � 时计算 ℎ(�,�) 并在 ℎ(�,�)=0 的情况下返回 0,否则会进入无限循环。因此,对于某些 �∈�,�(�)≃��(�)。但现在观察到以下两个选择之一必须成立:i) �(�)↓;或 ii) �(�)↑。因此,我们可以通过以下案例进行推理:
假设 �(�)↓。然后根据 �(�) 的定义,ℎ(�,�)=0。由于 ℎ(�,�) 是 HP 的特征函数,这意味着 ��(�)↑。但是由于 ��(�)≃��(�),��(�)↑,因此矛盾。
假设 �(�)↑。则根据 �(�) 的定义,ℎ(�,�)≠0。由于 ℎ(�,�) 是 HP 的特征函数(因此也是总函数),唯一的另一种可能性是 ℎ(�,�)=1,这又意味着 ��(�)↓。但是由于 �(�)≃��(�), �(�)↓,因此存在矛盾。□
因此,ℎ(�,�) 提供了一个数学上定义良好的总函数的初始示例,该函数不可计算。其他不可计算函数可以通过考虑类似于 HP 的决策问题来定义。一些众所周知的例子如下:
(30)�={�:��(�)↓}�={�:��(�)↓=0 对于所有 �∈�}TOT={�:��(�)↓ 对于所有 �∈�}FIN={�:��(�)↓ 对于最多有限多个不同的 �∈�}={�:�� 是有限的}
假设我们让 �(�)、�(�)、tot(�)和 fin(�) 成为这些集合的特征函数。通过对定理 3.3 的证明进行适当的修改,可以直接证明以下内容:
命题 3.1:函数 �(�)、�(�)、tot(�)和 fin(�) 都不是可计算的。
例如,在 �(�) 的情况下,我们可以进行如下论证:
定义一个函数 �(�),如果 �(�)=0,则返回 0,否则返回未定义;
与前面一样,如果 �(�) 被假设为可计算的,则 �(�) 是部分可计算的,因此存在一个指标 �,使得 �(�)≃��(�);
但现在观察到 �(�)=1,当且仅当 �(�)↑ 当且仅当 ��(�)↑ 当且仅当 �(�)=0。
由于这又是一个矛盾的情况,我们可以得出结论 �(�) 不可计算。
请注意,(30) 中定义的每个集合 � 都具有以下属性:如果 �∈� 且 ��(�)≃��(�),则 �∈� 也是如此。具有此属性的集合称为索引集,因为它们将所有具有共同“语义”属性的部分可计算函数的索引收集在一起,即完全由其图确定的索引,例如在�的情况下与常数 0 函数一致,或者在 TOT 的情况下在所有输入上定义。如果�≠∅或�≠�,则索引集�称为非平凡的,即它无法包含或排除所有索引。很容易看出,(30) 中定义的所有集合都是非平凡索引集。因此,这些集合的不可判定性来自以下更一般的结果:
定理 3.4(Rice 1953):如果�是非平凡索引集,则�是不可判定的。
证明:设 � 为非平凡指标集,并假设对于一个矛盾,��(�) 是可计算的。考虑处处未定义的一元函数 �(�),即,对于所有 �∈�,�(�)↑。由于 �(�) 是部分可计算的,故存在一个指标 � 使得 ��(�)≃�(�)。我们可以不失一般性地假设 �∉�。(如果 �∈�≠�,则我们可以在以下论证中将 � 的角色与其补 �― 互换,并得到相同的结果)。由于 �≠∅,我们也可以选择一个指标 �∈�,并定义一个函数如下:
�(�,�)={��(�)如果 �(�)=1 (即,如果 ��(�)↓)↑如果 �(�)=0 (即,如果 ��(�)↑)
请注意 �(�,�) 是部分可计算的,因为它是根据 ��(�) 的值根据 ��(�) 定义的。因此有一个指标 �,使得 �(�,�)≃��(�,�)。通过应用 s-m-n 定理 (3.1),我们得到 ��(�,�)≃��12(�,�)(�)。但请注意,我们现在有以下蕴涵序列:
�(�)=1⇔�(�,�)≃��(�)⇔��12(�,�)(�)≃��(�)⇔�12(�,�)∈�
(根据我们选择 �∈�)
�(�)=0⇔�(�,�)≃��(�)⇔��12(�,�)(�)≃��(�)⇔�12(�,�)∉�
(根据我们假设 � 是 �(�)(处处未定义的函数)的索引,并且 �∉�)。
因此,可以通过应用以下算法来计算 �(�) 的值:
输入 �时,计算 �12(�,�) 的值(其可计算性来自 s-m-n 定理);
计算 ��(�12(�,�)) 的值(这可以实现,因为我们已经假设 ��(�) 是可计算的)。
无论是通过调用 Church 论题还是通过将先前的算法形式化为部分递归定义,都可以得出 �(�) 是可计算的。但这与命题 3.1 相矛盾,命题 3.1 表明 �(�) 不可计算。 □
Rice 定理 (3.4) 提供了一种方法来表明许多具有实际意义的决策问题都是不可判定的——例如,确定程序是否始终返回输出或它是否正确计算给定函数(例如加法或乘法)。其证明还表明,如果 � 是一个非平凡指标集,则判定 �∈� 的问题可以“简化”为判定 �∈� 的问题,具体含义如下:如果我们能够有效地判定后者,那么我们也可以通过首先计算 �12(�,�) 然后检查该值是否在 � 中来有效地判定前者。这种显示不可判定性的方法将通过下面第 3.5 节中描述的多一归约概念形式化。
3.3 可计算和可计算可枚举集
集合 �⊆� 被称为可计算的(或根据第 2 节的旧术语为递归的),只要其特征函数是可计算的。更一般地,我们有以下内容:
定义 3.1:关系 �⊆�� 是可计算的,只要 ��(�→) 是可计算的。
此定义扩展了第 2.1 节中给出的原始递归关系的定义——例如,由于 PRIMES 和 DIV 等集合是原始递归的,因此它们本身就是可计算的。通过 Church 的论点,可计算集的概念也概括了关于有效可判定性的附带启发式方法——即,� 是可计算的,只要存在一种用于判定 �(�→) 是否成立的算法,并且该算法总是在有限(尽管可能无界)的步骤后返回答案。另一方面,从第 3.2 节中记录的观察结果可以看出,HP、K、Z、TOT 或 FIN 都不是可计算集。
一个相关的定义是可计算可枚举(或 c.e.)集合,即,其成员可以通过有效程序枚举的集合。(在第 2 节的旧术语中,这样的集合被称为递归可枚举,传统上缩写为 r.e.)正式定义如下:
定义 3.2:如果 �=∅ 或 � 是可计算函数的范围,则 �⊆� 是可计算可枚举的(或 c.e.),即
�={�:��(�)↓=�,其中 �∈�}
对于完全可计算函数的某个索引 �。
此定义可以扩展到关系,方法是以显而易见的方式将 � 视为有限序列的代码,即 �⊆�� 是 c.e.假设存在一个可计算函数��(�),使得�(�0,…,��)当且仅当 ��(�)=⟨�0,…,��⟩ 其中 �∈�。
如果 � 是可计算枚举的,则其成员可以列为
�={��(0),��(1),��(2),…}
可能带有重复——例如,常量函数 const17(�) 枚举单例集 {17},因此是 c.e. 很容易看出,可计算集 � 是可计算枚举的。因为如果 �=∅,则 � 根据定义是 c.e.。如果 �≠∅,我们可以选择 �∈�,然后定义
(31)�(�)={�if ��(�)=1�otherwise
在这种情况下 �(�) 是可计算的并且其范围为 �。
在证明关于可计算可枚举集的事实时,通常使用几个等效定义之一很方便:
命题 3.2:假设 �⊆�。则以下内容是等效的:
� 是可计算可枚举的。
�=∅ 或 � 是原始递归函数的范围。
对于可计算关系 �,�={�∈�:∃��(�,�)}。
� 是部分可计算函数的定义域。
命题 3.2 的证明主要是解开定义的问题。例如,要看到 iv 蕴含 i,假设 �=dom(��) — 即 �={�∈�:��(�)↓}。如果 �=∅,则它自动为 c.e。否则,有一个元素 �∈�。我们现在可以定义
�(�)={(�)0if �1(�,(�)0,(�)1)�otherwise
�(�) 因此将其输入视为一对 ⟨�,�⟩ 由 ��(�) 的输入 � 和 计算序列 � 组成,如范式定理 (2.3) 的证明中所定义。由于 � 在 � 上变化,因此它会遍历所有可能的输入 (�)0 到 �� 以及所有可能的见证 (�)1 ,即 �� 在 (�)0 上的计算停止。然后,如果 (�)1 是停止计算的见证,则返回 (�)0 ,否则返回 �。因此 �(�) 的范围将对应于 ��(�) 的范围。由于 �1(�,�,�) 是可计算的(实际上是原始递归)关系,因此很容易看出 �(�) 是一个范围为 � 的可计算函数。这表明 � 是 c.e.,正如所期望的那样。
命题 3.2 的第四部分还为可计算可枚举集提供了一个方便的统一符号——即,如果 �=dom(��) ,我们将 � 表示为 ��={�:��(�)↓}。因此,相对于我们之前对一元偏可计算函数的枚举,序列 �0,�1,�2,… 提供了 c.e. 集的统一枚举。这种符号还有助于下列公式的表述:
命题 3.3:
可计算可枚举集在并集、交集和叉积下有效封闭——即,存在可计算函数 un(�,�)、int(�,�) 和 cr(�,�),使得如果 �=�� 且 �=�� 则
�∪�=�un(�,�)、�∩�=�int(�,�)
且
{⟨�,�⟩:�∈� & �∈�}=�cr(�,�)。
可计算集在补集和相对补集下也封闭——即,如果 � 和 � 是递归的,则 �― 和 �−� 也是递归的。
根据 Church 的论题,这些事实的证明也很简单。例如,如果 dom(��)=� 且 dom(��)=�,则 un(�,�) 可视为程序的索引,该程序交替模拟 ��(�) 和 ��(�) 的计算,并在其中一个子计算停止时停止。还要注意,如果 �=�� 是可计算的,则 ��―(�)=1−˙��(�) 也是可计算的,由此可知 �― 是可计算的。[23]
相关观察如下:
命题 3.4(1944 年后):� 是可计算的当且仅当 � 和 �― 都是可计算可枚举的。
从左到右的方向包含在命题 3.3 中。对于从右到左的方向,假设 �=dom(��) 且 �―=dom(��)。然后,为了确定 �∈�,我们可以对计算序列 � 进行无界搜索,使得 �1(�,�,�) 或 �1(�,�,�),在第一种情况下接受,在第二种情况下拒绝。由于 �∪�―=�,搜索必须始终终止,并且由于 �∩�―=∅,条件是互斥的。因此,再次援引丘奇的论点,� 是可计算的。
我们已经看到可计算集包含在可计算可枚举集中。在此阶段出现两个问题如下:
是否存在可计算可枚举但不可计算的集合的例子?
是否存在不可计算可枚举的集合的例子?
下列内容对这两个问题都给出了肯定的答案:
推论 3.1:回想一下集合 �={�:��(�)↓}——即所谓的对角线停机问题。� 是可计算的可枚举的,但不可计算,而 �― 不是可计算的可枚举的。
� 显然是 c.e.,因为它是 ���1(�,�,�) 的定义域。另一方面,我们已经看到 � 的特征函数——即第 3.2 节中定义的函数 ��(�)=�(�)——是不可计算的。因此 � 确实是一个不可计算的可计算可枚举集。要看出 �― 不是 c.e.,请注意,如果是,那么 � 将根据命题 3.4 可计算。这反过来又表明,在某种意义上,决定�中的成员身份比决定任何可计算集合中的成员身份“更难”。第 3.5 节和第 3.6 节中介绍的层次结构将提供一种使此类观察更加精确的方法。
3.4 递归定理
现在最常被称为克莱尼递归定理的结果可用于统一许多类似于定理 3.3 所依据的有效对角线论证,并且在可计算性理论以及数理逻辑和计算机科学的其他领域都有广泛的应用。[24] 虽然它的陈述很简单,但在考虑后续应用时,它的意义和随后的证明都会变得更加清晰。
定理 3.5(克莱尼 1938):假设�(�) 是一个完全可计算函数。然后有一个数 �∈� 使得 ��(�)≃��(�)(�)。
证明:考虑函数 �(�,�) 定义如下:
�(�,�)={���(�)(�)if ��(�)↓↑otherwise
显然 �(�,�) 是部分可计算的,对于某个 �,�(�,�)≃��(�,�)。因此,根据 s-m-n 定理 (3.1),��(�,�)≃��12(�,�)(�)。设 �(�)=�12(�,�),并注意到,只要 ��(�) 有定义,则 ��(�)(�) 与 ���(�)(�) 是相同的函数。请注意,�(�) 是一个完全可计算函数,其定义独立于给定函数 �(�)。
接下来,令 � 为 �(�) 与 �(�) 的组合指标,即 ��(�)≃�(�(�))。我们现在声称 �=�(�) 是定理陈述中要求的数字。首先请注意,由于 �(�) 和 �(�) 都是完全的,��(�) 也是完全的,因此 ��(�) 是有定义的。由此可知 ��(�)(�)≃���(�)(�)。我们现在有以下函数恒等式序列:
��(�)≃��(�)(�)≃���(�)(�)≃��(�(�))(�)≃��(�(�))(�)≃��(�)(�)
□
递归定理有时也称为不动点定理。但请注意,定理 3.5 并不保证给定函数 �(�)(即一个数字 �,使得 �(�)=�)存在外延不动点。(事实上,显然存在不存在这种值的可计算函数,例如 �(�)=�+1。)?但假设我们将 �(�) 视为对部分可计算函数索引的映射,或者更形象地说,将其视为将用于计算部分可计算函数的程序转换为另一个程序的手段。根据这种解释,该定理表示,对于每一个这样的可计算变换,都存在某个程序 �,使得它计算的函数 ��(�) 与在变换下由其图像 �(�) 计算出的函数 ��(�)(�) 相同。