递归函数(四)
这里前�个参数�0,…,��−1 到 �是参数,�+1个参数�是递归变量,�+2个参数ℎ(�0,…,��−1,�) 给出ℎ的先验值。一个基本集合论论证表明,对于每个�∈�,如果�是k元且�是�+2元,则存在一个唯一的�+1元函数ℎ满足(18)——参见Moschovakis(1994:第5章)。
再次引入一个正式的方案来引用以这种方式定义的函数将很有用:
%00
定义2.2:假设�:��→�和�:��+2→�。那么术语PrimRec�[�,�]表示满足(18)的类型��+1→�的唯一函数。
现在我们可以正式定义原始递归函数类 PR 如下:
定义 2.3:原始递归函数类 PR 是包含初始函数 �PR={0,�,���} 并在泛函
OpPR={Comp��,PrimRec�} 下封闭的最小函数类。
有了 PR 的定义,我们还可以定义关系 �⊆�� 为原始递归的含义:
定义 2.4:�⊆�� 是原始递归关系,只要其特征函数
��(�0,…,��−1)={1 if �(�0,…,��−1)0 if ¬�(�0,…,��−1)
是原始递归函数。
因此,定义 2.4 将原始递归关系 �⊆�� 的特征化为存在与上述算法类似的算法,该算法在输入 �→ 时返回输出 1(如果 � 对 �→ 成立),在输入 �→ 时返回输出 0(如果 � 对 �→ 不成立)。正如下文将清楚说明的那样,日常数学中考虑的大多数自然数集合和关系(例如素数集合 PRIMES 或关系
DIV={⟨�,�⟩:� 除 � 无余数}
)都是原始递归的。
上述定义将 PR 指定为 �PR 在 OpPR 中的函数下的最小闭包。换句话说,PR 可以等效地定义为满足以下属性的 ⋃�∈�(��→�) 的子类:
(19)i.�PR⊆PRii.对于所有�,�∈�和�,�0,…,��−1∈PR,如果�为 j 元且�为 k 元(对于 1≤�≤�),则 Comp��[�,�0,…,��−1]∈PR。iii.对于所有�∈�和�,�∈PR,如果�为 k 元且�为 �+2 元,则 PrimRec�[�,�]∈PR。iv.除非可以通过 i–iii 定义,否则任何函数都不是 PR 的成员。
因此,定义 2.3 的另一个推论是,每个函数 �∈PR 都具有一个规范,该规范显示了如何根据有限数量的组合和原始递归应用从初始函数 �PR 定义它。可以通过进一步考虑上面给出的函数 add(�,�) 和 mult(�,�) 的定义来说明这个过程。
首先请注意,虽然熟悉的加法 (3) 和乘法 (4) 的递归定义符合 (16) 的格式,但它们不符合 (18) 的格式,在这种情况下,原始递归方案的参数 � 是 3 元函数。但是,可以通过取 �(�0)=�01(�0)(即恒等函数)和 �(�0,�1,�2)=Comp31[�,�13](即由后继函数与 3 元投影函数组合到其第二个参数上而得到的函数)来提供正式形式的 add(�,�) 的定义。表达式 PrimRec1[�01,Comp31[�,�13]] 可以理解为编码我们为加法提供的定义的术语。乘法可以通过 (18) 定义,其中 �=0 和
�(�0,�1,�2)=Comp32[���,�03,�23]。
因此
PrimRec1[0,Comp32[���,�03,�23]]
—或以显式形式
PrimRec1[0,Comp32[PrimRec1[�01,Comp31[�,�13]],�03,�23]]
—可视为编码乘法定义的类似术语,我们将其缩写为 mult(�,�)。
这些示例说明,许多非正式递归定义中使用的更简单的递归方案可以与 定义 2.3 同化——例如,(16) 中定义的函数 ℎ(�,�) 可以作为 PrimRec1[�,Comp32[�,�13,�23]] 获得。第 2.1.2 节提供的示例中将重复使用此观察结果和类似观察结果(通常不作评论)。
每个�∈PR 都由 (19) 给出的项定义,这一事实的另一个推论如下:
命题 2.1:函数类 PR 是可数的。
这可以通过证明,通过引入由表达式 0、�、���、Comp�� 和 PrimRec� 形成的项的哥德尔编号,可以将 PR 枚举为�0、�1、�2、…,方式如第 1.3 节所述。由于对于所有�>0,类型为��→� 的函数不可数,因此这一观察结果还提供了一个非构造性的证明,即存在非原始递归的数论函数。
2.1.2 示例
几乎所有在普通数学中遇到的数论函数和关系都可以证明是原始递归的。为了说明此类的范围,我们将在此介绍一个标准的定义序列,其历史可以追溯到 Skolem (1923)。这可用于表明下面定义的序列编码 ⟨…⟩ 和解码 (⋅)� 操作是原始递归的。这反过来又是哥德尔语法算术化(参见第 1.3 节)以及下面将讨论的范式定理 (2.3) 等结果所必需的。
a. 常数函数
对于每个 �∈�,定义为 const�(�)=� 的常数 k 函数是原始递归的。为了说明这一点,我们首先通过原始递归定义常数 0 函数,如下所示:
const0(0)=0const0(�+1)=�12(�,�����0(�))
然后我们可以通过重复组合定义常数 k 函数为
������(�)=�(…(�(�����0(�))…)⏟� 次
b. 指数、超指数、…
我们已经看到,加法函数 add(�,�) 可以通过原始递归定义,即重复应用后继,乘法函数 mult(�,�) 可以通过原始递归定义,即重复应用加法。我们可以通过观察指数函数 �� 可以通过原始递归定义,即重复乘法,继续这一序列如下:
(20)exp(�,0)=1―exp(�+1,�)=mult(�,exp(�,�))
超指数函数
⋰�↑�=��⋰�⏟� 次
可以通过原始递归以重复指数的形式定义如下:
(21)supexp(�,0)=1―supexp(�+1,�)=exp(�,supexp(�,�))
函数序列
�0(�,�)=�+�,�1(�,�)=�×�,�2(�,�)=��,�3(�,�)=�↑�,⋮
其�+1 个成员以�个成员的原始递归形式定义,形成函数层次结构,其值随输入而快速增长。虽然该序列中的每个函数都是原始递归的,但我们也可以考虑定义为��(�,�)的函数�(�,�)——第 1.4 节中定义的所谓 Ackermann-Péter 函数的一个版本——其值不受任何固定函数��的限制。由于可以证明�(�,�) 的值不受任何函数��(�,�) 的限制,这表明�(�,�) 不能通过任何有限次应用 PrimRec1 方案来定义。这提供了一个建设性的证明,即存在类型为�2→�的函数,它们不是原始递归的。
c. 前驱和真减法
真前驱函数由以下公式给出
pred(�)={0 if �=0�−1otherwise
该函数是原始递归函数,因为它可以定义为
(22)pred(0)=0pred(�+1)=�
请注意,(22) 的第二子句不依赖于 pred(�) 的先验值。但是,通过取 �(�0)=0 和 �(�0,�1)=�02,该定义仍可符合方案 (18)。
真减法函数由以下公式给出
�−˙�={�−� if �≤�0otherwise
该函数也是原始递归函数,因为它可以定义为
(23)�−˙0=��−˙(�+1)=pred(�−˙�)
d.绝对差、正负号、最小值和最大值
绝对差函数定义为
|�−�|={�−� if �≤��−�otherwise
|�−�| 可以通过组合定义为 (�−˙�)+(�−˙�) ,因此是原始递归函数,因为 −˙ 是。
正负号函数定义为
sg(�)={1 if �≠00otherwise
此函数可以通过组合定义为 sg(�)=1−˙(1−˙�) ,因此是原始递归函数,就像 sg―(�)=1−˙sg(�) 定义的反正负号函数一样,如果 �=0 则返回 1,否则返回 1。
最小函数和最大函数可以通过从以前被视为原始递归的函数组合来定义,如下所示:
min(�,�)=sg―(�−˙�)×�+sg(�−˙�)×�max(�,�)=sg(�−˙�)×�+sg―(�−˙�)×�
e. 顺序和身份
自然数上的小于关系 (<) 和相等关系 (=) 的特征函数可定义如下:
�<(�,�)=sg(�−˙�)�=(�,�)=1−˙(sg(�−˙�)+sg(�−˙�))
因此,这些关系是原始递归的。
由于小于或等于关系 (≤) 在逻辑上等同于 �<�∨�=�,因此从下一组观察结果可以看出,该关系也是原始递归的。�>�、�≥� 和 �≠� 也同样如此。
f. 命题运算下的闭包
原始递归关系集在布尔运算下是封闭的。换句话说,如果 �(�→) 和 �(�→) 是原始递归的,那么 ¬�(�→)、�(�→)∧�(�→)、�(�→)∨�(�→)、�(�→)→�(�→) 和 �(�→)↔�(�→) 也是如此。
鉴于经典连接词的可相互定义性,以下结论成立:
�¬�(�→)=1−˙��(�→)��∧�(�→)=��(�→)×��(�→)
g. 有界和与有界积
假设 �(�→,�) 是原始递归的。那么有界和 �(�→,�)=Σ�=0��(�→,�) 和有界乘积 ℎ(�→,�)=Π�=0��(�→,�) 都是原始递归的,因为它们可以分别定义如下:
�(�→,0)=�(�→,0)�(�→,�+1)=�(�→,�)+�(�→,�+1)ℎ(�→,0)=�(�→,0)ℎ(�→,�+1)=�(�→,�)×�(�→,�+1)
h.有界量化下的闭包
原始递归关系集在有界量化下也是闭包的——即,如果 �(�→,�) 是原始递归关系,则关系 ∀�≤��(�→,�) 和 ∃�≤��(�→,�) 也是如此。它们可以分别定义如下:
��(�→,�)=df�∀�≤��(�→,�)(�→,�)=Π�=0���(�→,�)��(�→,�)=df�∃�≤��(�→,�)(�→,�)=��(Σ�=0���(�→,�))
由于下文会用到,我们在此扩展了特征函数的符号约定,以便在所定义函数的下标中显示自由变量和约束变量。
i.有界最小化下的闭包
原始递归关系集在有界最小化下也是封闭的。也就是说,如果 �(�→,�) 是原始递归关系,那么函数 ��(�→,�) 也是原始递归关系,它返回小于或等于 �的最小值,使得 �(�→,�) 在存在这样的 �时成立,否则成立 �+1 —即,
(24)��(�→,�)={最小值 �≤�,使得 �(�→,�) 在存在这样的 �时成立�+1 否则
要看到这一点,请观察如果 �(�→,�) 是原始递归,那么 ∀�≤�¬�(�→,�) 也是如此。那么,验证以下事实就不难了:
��(�→,�)=Σ�=0��∀�≤�¬�(�→,�)(�→,�)。
j. 可整除性和素数性
如果存在一个�,使得�×�=�,即�能被�整除而无余数,则称自然数�能被�整除。在这种情况下,我们写为�∣�。请注意,如果�∣�成立,则必须有一个除数�≤�,使得�×�=�,来证明这一点。因此,我们可以按以下方式定义 �∣�,表明它是原始递归的:
�∣�⟺∃�≤�(�×�=�)
我们还可以将不可整除关系 �∤� 定义为 ¬(�∣�),表明它也是原始递归的。
接下来回想一下,自然数 � 是素数,只要它大于 1 并且只能被 1 和它本身整除。因此,我们可以按以下方式定义关系 Prime(�),表明它是原始递归的:
Prime(�)⟺1―<�∧∀�≤�(�∣�→(�=1―∨�=�))
素数形成一个熟悉的无限序列 �0=2, �1=3, �2=5, �3=7, �4=11,…。假设 �(�)=��——即返回第 � 个素数的函数。�(�) 可以通过相对于函数 nextPrime(�) 的原始递归来定义,该函数返回最小的 �>�,使得 � 为素数,如下所示:
�(0)=2―�(�+1)=nextPrime(�(�))
回想一下,欧几里得定理指出,� 和 �!+1 之间总有一个素数,并且 �!=fact(�) 是原始递归的。因此,nextPrime(�) 可以通过有界最小化来定义,如下所示:
nextPrime(�)=��<� ∧ Prime(�)(�,fact(�)+1)
因此,�(�) 是原始递归的。
k. 序列和编码
上述定义序列为原始递归关系和函数类的稳健性提供了一些证据。进一步的证据是,有可能开发出用于编码和解码有限自然数序列以及对序列执行各种组合运算的机制——例如,元素的附加、连接、提取子序列、用一个元素替换另一个元素等。这些操作的原始递归性支撑了第 1.3 节中描述的哥德尔语法算术化。我们在这里仅介绍证明 k 元组和投影函数的原始递归性所需的基本定义,这些定义是可计算性理论结果所必需的,例如下面讨论的范式定理 (2.3)。
给定一个有限自然数序列�0,�1,…,��−1,我们将其代码定义为数字
(25)�0�0+1×�1�1+1×�2�2+1×…×��−1��−1+1
其中��是如上定义的第�个素数。换句话说,�0,�1,…,��−1的代码是将����+1乘以0≤�≤�−1所得的自然数。这将表示为⟨�0,�1,…,��−1⟩—例如,
⟨3,1,4,1,5⟩=24×32×55×72×116=39062920050000。
(请注意,每个指数都加 1,因此,例如,3、1、4、1、5 的代码与 3、1、4、1、5、0 等的代码不同——即,编码操作是单射的。)
将任意长度的序列转换为其代码的操作没有固定的元数,因此不是由单个原始递归函数给出的。但不难看出,如果我们将注意力限制在给定长度的序列上,那么 ⟨�0,�1,…,��−1⟩:��→� 是原始递归的,因为它只是 (25) 给出的有界乘积。接下来考虑函数 element(�,�)=��,其中 �=⟨�0,�1,…,��−1⟩ 且 0≤�≤�−1,并且当 � 不在此范围内或 �=0 或 1(因此不是序列的代码)时返回 0。为了说明 element(�,�) 也是原始递归的,首先观察到可以通过搜索最小 �<� 使得 ��∣� 和 ��+1∤� 来恢复 len(�),即由 � 编码的序列的长度。由于 � 也限制了所有能整除它的素数 ��,因此我们可以定义
���(�)={0 如果 �=0 或 �=11+���∣�∧��+1∤�(�,�) 否则
很容易看出,由具有原始递归条件的案例定义的函数是原始递归的。因此 len(�) 也是原始递归的。同样,很容易看出,作为序列代码的关系 ���(�) 是原始递归的。
最后观察到,element(�,�) 等于最小指数 �,使得 ���+1∣� 但 ���+2∤� 并且这样的指数也受 � 限制。因此,我们可以提供元素(�,�)的原始递归定义,如下所示:
元素(�,�)={0 如果 �≥���(�) 或 ¬���(�)����+1∣�∧���+2∤�(�,�)−˙1 否则
下面将使用此函数的常规缩写(�)�=元素(�,�)。
2.1.3 原始递归函数的附加闭包属性
原始递归函数和关系涵盖了一个广泛的类别,几乎包括逻辑或可计算性理论之外的普通数学中遇到的所有函数。这部分地说明了 PR 包含诸如������(�,�)之类的函数,其增长速度远远快于我们在计算复杂性理论中研究的意义上可以实际计算其值的函数。但是,PR 类的稳健性也由以下事实证明:它的定义对于各种修改都是不变的——例如,对于其定义所基于的初始函数 �PR 和泛函 OpPR 类而言。
作为初步说明,请考虑以下所谓的纯迭代方案:
(26)ℎ(0,�)=�ℎ(�+1,�)=�(ℎ(�,�))
很容易看出,以这种方式从 � 定义的 (26) 函数 ℎ 是 � 的第 � 次迭代——即 ��(�)=df�(�(…�(�))) � 次,约定为 �0(�)=�。我们将用 Iter[�,�] 表示这个函数。因此,方案 (26) 通过将基例的值作为 ℎ 的参数来推广 (14)。但这显然是对 (18) 的限制,因为 ℎ 不能依赖于递归变量或其他参数。
假设我们现在考虑另一个初始函数类 ��IT ,其中包含 �,���、二进制编码函数 ⟨�,�⟩ 以及第 2.1.2 节末尾定义的解码函数 (�)0 和 (�)1。(请注意,它们的操作类似于对有序对代码进行操作的第一和第二个生产函数 �02 和 �12。)现在将 IT 定义为包含 ��IT 并在函数 OpIT={Comp��,Iter} 下封闭的最小函数类。
(本章完)