新浪博客

910哥德尔递归汉译和原始递归——哥德尔原著英译拆解汉译之七

2022-03-13 19:11阅读：

http://blog.sina.cn/dpool/blog/u/1793891833

910 哥德尔递归汉译和原始递归——哥德尔原著英译拆解汉译之七

虎年的春节接近尾声，从惠州双月湾返回广州，已经时过一月了。近日又碰上一个震撼世界的俄乌开战，这篇博文也就一拖再拖。此外，还伴有诸多生存琐事缠绕。但书还得读，尤其是你已经开看，并且准备认真看的那些书。
读一本书，宛如和那读书的主人签下合同似的，不继续读下去，颇有点失去信用的感觉。好在是自己与自己定约，不牵涉第二方第三方，所以这爽约的事，也就能够自我谅解。为俄乌战事弄了七篇随笔，三月也眼看过了一半，回到哥德尔这里换换口味吧。
哥德尔的那个原著文本，一直是准备认真对付的，自然还得花功夫读下去。一边是对着文本的读，一边是对着屏幕的敲，于是就有了2.2节哥德尔数之后的又一节文字汉译，也就是以下的汉译文字。哥德尔原著文本英译本的2.3节：原始递归。
哥德尔关于递归的描述在原著英译的2.3节，其篇幅远超2.2节的哥德尔数。原始递归的论述用了整整3个页码，从第6页到第9页，其实也就2000多汉字。
以下标为一的第一部分，即是拆解汉译哥德尔原著英译文本。

一.哥德尔原著英译本拆解汉译2.3节原始递归

2.3 原始递归
此刻，我们将引入一个插述式思考，预先指出的是，这个思考和形式系统P没有任何直接联系，我们先给出以下定义：称一个数论函数Φ(x1，x2...xn)被数论函数Ψ(x1，x2...xn-1)和μ(x1，x2...xn+1)说成是原始递归定义的，如果对于所有的x2，x3...xn，k而言，以下公式成立：


Φ(0，x2，x3...xn) = Ψ(x2，x3...xn)
Φ(k+1，x2，x3...xn) = μ(k，Φ（k，x2，x3...xn) （2）

称数论公式Φ是原始递归的，如果存在一个有限数论公式序列Φ=Φ1，Φ2，...Φn，该序列在Φ中终结，使得序列中的每一个函数Φk：或者，它是被在前的两个公式通过原始递归而定义；或者，它是通过插入在前公式中的任意一个推导而得到的结果；或者，它作为一种基本情形，是一个常元，或者是那个后继函数succ(x)=x+1。属于一个原始递归函数Φ中的Φi，它最短序列的长度，被起名为是该函数Φ的度degree。
一个在自然数之中的关系R(x1，x2...xn)称作原始递归的，如果存在一个原始递归函数Φ(x1，x2...xn)使得对于所有的x1，x2...xn都有：

R(x1，x2...xn) [Φ(x1，x2...xn)=0]

则以下定理成立。
I .通过将原始递归函数（关系）插入到另一个原始递归函数（关系）变元位置，从而获得的每一个函数本身都是原始递归的；通过上述模式（2），从原始递归函数得到的每一个函数也是原始递归的。
II ．如果R和S是原始递归关系，那么，ØR,RÚS,（因此RÙS）也是原始递归关系。
III ．如果函数 ， ，是原始递归的，那么， = 也是原始递归的。[英译者注：我们诉诸于某个向量关系 去指称有限长度的变元组]。
IV ．如果函数 ，和关系R( ，是原始递归的，那么，关系S,T也是原始递归的。这里的S和T如以下公式所示：

S( ， ) ($y£ . R( )

T( ， ) ('y£ . R( )

同样，函数Φ也是原始递归的，这里的Φ，如以下公式所示：

Φ( ， ) (argmin y£ ·R( )

其中，argmin x£f(x)·F(x)代表最小的x，对于这个最小的x而言，x£f(x)ÙF(x)成立，如果不存在这样一个最小数，则该公式代表0。[英译者注：对于这样的读者，即那些对运算描述有更多诉求的读者，他们可能想把这看做是一个循环，一个试图让每一个从1到Φ 的值去决定结果的循环。但这里的关键点是，这个定理并未陈述，一个无边界的循环（或者递归）是原始递归的；但依据可计算性概念，那些人严格地在事实上更有力度]。
定理 I 直接从“原始递归”的定义得出。定理II 和定理III 则基于以下事实：对应于逻辑概念Ø，Ú，=的数论函数，即以下这些函数都是原始递归的

1 对于x=0
a(x)=
0 对于x≠0
0 如果x和y中的一个或者两个=0
b（x,y）
1 如果x和y中两个都≠0
0 如果x=y
g（x,y）
1 如果x≠y

[英译者注：其中n=0表示为真，n≠0表示为假]

这些函数都是原始递归的，人们很容易从心中确信。定理IV 的证明可简要陈述如下：假设有一个原始递归的r(y, )使得：

R(y, ) ( r(y, )=0)

使用递归模式（2），我们现在定义一个函数c(y, )如下：

c(0, )=0
c(n+1, )=(n+1) ·A+c(n, ) ·a(A)

其中，A=a(a(r(0, )))·a((r(n+1,

我的更多文章

下载客户端阅读体验更佳

APP专享