博文
2022-03-13
|
哥德尔递归汉译和原始递归——哥德尔原著英译拆解汉译之七
虎年的春节接近尾声，从惠州双月湾返回广州，已经时过一月了。近日又碰上一个震撼世界的俄乌开战，这篇博文也就一拖再拖。此外，还伴有诸多生存琐事缠绕。但书还得读，尤其是你已经开看，并且准备认真看的那些书。
读一本书，宛如和那读书的主人签下合同似的，不继续读下去，颇有点失去信用的感觉。好在是自己与自己定约，不牵涉第二方第三方，所以这爽约的事，也就能够自我谅解。为俄乌战事弄了七篇随笔，三月也眼看过了一半，回到哥德尔这里换换口味吧。
哥德尔的那个原著文本，一直是准备认真对付的，自然还得花功夫读下去。一边是对着文本的读，一边是对着屏幕的敲，于是就有了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如以下公式所示：
T(，) ("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
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)
c(n+1, )=(n+1) ·A+c(n, ) ·a(A)
其中，A=a(a(r(0, )))·a((r(n+1, )·a(c(n, ))。
[英译者注：上述符号A，即运用上述定义a，同时运用一个条件句：如果其因子中有一个因子是0，则其乘积为0，这样一个事实而构成的A，公式A可以用以下伪代码(psendo-code)方式得到描述：
A=if(r(0, )=0)
then 0
else if(r(n+1, )≠0)
then 0
then 0
else 1
对于算术如何能够被用来仿效逻辑，这是很好的一个实例]。
因此，c(n+1, )或者是等于=n+1,(如果A=1)；或者是等于=c(n, )（如果A=0）。显然，前一种情形将出现，当且仅当A的所有因子是1，也就是，如果我们有公式
这就蕴涵了，函数(c(n, )（看作为n的函数）保留了0以上n的最小值，对于这个n，公式R(n, )成立，并且，正由此而等于这个最小值（（如果R(0, )，那么，(c(n, )就是相应的常元并且=0))。因此，我们又有以下公式
Y，)= ,()
把关系T用否定归约为类似于S的那种情形，这是很容易的。这就完成了对于定理IV的证明。
哥德尔的英译2.3.原始递归小节，到此译毕。
文字真是一个奇妙的东西，德语看不明白，翻成英文就使得理解成为某种可能。再从英文翻成中文，间或参照英文，对哥德尔的理解似乎就可以再上层楼了。中国哲学和数学界总有些狂妄之人，风格颇似唐吉坷德的骑士精神，敢于用长矛向长臂风车挑战。国内逻辑界中，似乎还未看到这样的异类。这批骑士，常存反骨，名之曰不崇洋媚外，有批判精神。我不敢妄评这种批判异类，因为对哥德尔的理解底气不足。但对这样的异类批判文字，始终不敢苟同，权当看客间有感叹而已。
闲言少述，书归正传，开始消化这个哥德尔的原始递归观念吧。
二、从哥德尔的定义看原始递归函数
（一）哥德尔原始递归定义
“哥德尔数”那个2.2节，就已经有点难度了，这个2.3节似乎难度更高。
直切主题，从哥德尔的原始递归定义开始。
哥德尔不完全性定理，一个需要交代的背景，是所谓递归概念，以及由递归引出的原始递归函数。哥德尔1931年的那篇证明不完全性定理的论文，原始递归函数起到极重要的作用。按照莫绍揆先生的说法，也就是在这篇论文之后，“原始递归函数论”便正式作为一种数学理论出现了（参见莫绍揆著《递归论》第1页）。
在此，再给出一次哥德尔的汉译原始递归定义，哥德尔的原著文本使用的递归函数概念，Hirzel英译本在递归之前加进了原始，译为原始递归或者原始递归函数：
称一个数论函数Φ(x1，x2...xn)被数论函数Ψ(x1，x2...xn-1)和μ(x1，x2...xn+1)说成是原始递归定义的，如果对于所有的x2，x3...xn，k而言，以下公式成立：
Φ(k+1，x2，x3...xn)= μ(k，Φ（k，x2，x3...xn) （2）
称数论公式Φ是原始递归的，如果存在一个有限数论公式序列Φ=Φ1，Φ2，...Φn，该序列在Φ中终结，使得序列中的每一个函数Φk：或者是，被在前的两个公式通过原始递归定义的；或者是，它通过插入在前公式中的任意一个推导而得到的结果；或者是，作为一种基本情形，它是一个常元，或者是那个后继函数succ(x)=x+1。
何谓原始递归呢？
我忽地联想到了历史，历史是不断地复制自身，构成一条只有时间增量的，递归式的历史套娃呢，还是不断超越自身，隽刻着人类智慧痕迹的时间链条呢？这好像很值得探索，就像数理学者探索无尽宇宙时的那些奇思妙想一样。但这样的比喻代替不了学界对其所作的定义，描述我们人类的智慧，自然语言提供了语言的基本平台，但仅仅自然语言还不够，还得有专业的学科语言即所谓形式语言来提升智慧的强度。这正如开创现代逻辑的弗雷格所言：光有肉眼那是不够的，还需要超越肉眼功能的显微镜。我们还是回到文本，来分析哥德尔对于原始递归函数的定义。
（二）有头有尾的递归函数
先简要说明一下函数和数论函数。
函数可以简单地看作是从一个客体到另一个客体的运算。
如果给函数分类，大概可以按照克林的分法，将其分为四类。第一类就是数论函数，从数字｛0，1，2，3…｝到数字｛0，1，2，3，…｝的函数，这种函数也可以直接简称为函数。其它三类，一类是数论谓词，从数字｛0，1，2，3，..｝到真值｛1，0｝的函数。另一类是真值函数，从｛1，0｝到｛1，0｝的函数。还有一类与数论谓词反向的函数，从｛1，0｝到｛0，1，2，3，…｝,这被称为特征函数，莫先生翻译为“代表函数”。（克林《元数学导论》第246页）
哥德尔所说的数论函数，也就是克林的第一类函数。这样的函数，其定义域是数字，值域也是数字。应该没有疑问，哥德尔的原始递归函数，是在克林数论函数视野之下的函数。被定义的那个Φ(x1，x2...xn)是数论函数，所依据的两个公式Ψ(x1，x2...xn-1)和μ(x1，x2...xn+1)也是数论函数。
哥德尔原始递归定义中的公式（2），需要特别地关注，这两个公式的成立，是原始递归特性赖以成立的前提。
Φ(0，x2，x3...xn)=Ψ(x2，x3...xn) （2-1）
在函数Φ的变元中，一个常元0替代了原先的x1。函数Y的变元中，则少了一个变元x1。Y的变元中还有一个变化，变元的编码从x2开始，末位变元编码从xn-1变成了xn。这样的符号编码变化，告诉读者一些什么信息呢？
我们行将给以原始递归性质的函数是Φ(x1，x2...xn)，编码从1到n。
它所依据的一个函数是Ψ(x1，x2...xn-1)，变元编码顺序从1到n-1。
但公式（2）中第一个公式（2-1）中的函数Φ公式，编码顺序却是从0作为第一个编码开始到n。
且公式（2）中第一个公式（2-1）中的函数Y公式，变元编码顺序却是从2开始到n。
这意味着什么呢？这意味着，函数Φ(x1，x2...xn)有原始递归性质的第一个条件，这被称为基始条件。一个递归结构一定有一个起点，这个起点就是公式（2-1）所标示的，从0开始，这也称之为开始函数。可以表述为是这样两个函数之间的相等关系成立，即（2-1）成立。也就是说，这个（2-1）告诉我们，一个递归结构是有起点的。
再看（2）中的第二个公式（2-2）。
Φ(k+1，x2，x3...xn)= μ(k，Φ（k，x2，x3...xn) （2-2）
可以用同样的方式来解读这个公式（2-2），这大概也是递归的基本性质，反复地，用计算机的语言，迭代式地调用同样的函数来对客体对象进行推移运算。
在公式（2-2）中，函数Φ的首变元也有了变化，用变元k+1替代了原先的x1。函数Y则换掉，用另一个函数μ来表示。在Φ的变元中，少了一个变元x1。μ的变元中也有一个变化，变元的编码顺序从k开始，末位编码变元变成了一个Φ函数，该函数的定义域是一串从k到xn的变元。这样的变元和符号编码变化，告诉读者一些什么信息呢？
我们行将给以原始递归性质的函数是Φ(x1，x2...xn)，编码从1到n。
它所依据的一个函数是Ψ(x1，x2...xn-1)，变元编码从1到n-1。
但公式（2）中第二个公式（2-2）中的Φ函数公式，变元顺序却是从k+1作为第一个变元开始，一直到第n个变元xn为止。
且公式（2）中第二个公式（2-2）中的μ函数公式，变元仅仅两个。一个是k，另一个是从变元k到第n个变元的xn，它们构成了函数μ。
这意味着什么呢？这意味着，函数Φ(x1，x2...xn)有递归性质的第二个条件，这被称为终止条件。一个递归结构一定有一个终点，这个终点就是公式（2-2）所标示的，以xn结束，这也称之为终止函数。它可以表述为是这样两个函数之间的相等关系成立，即（2-2）成立。也就是说，这个（2-2）告诉我们，一个递归结构是有终点的，它不是一个无穷尽的客体。
递归图示
（三）从本原函数出发做成的函数是原始递归函数
递归定义对于自然数是这样一种指定，一个数字系列中的每一个数字，它是通过指定第一个数字，并且给定一类规则而形成的。这个规则依据第k个数字和k这个数字自身，来指定那个第（k+1）的数字。这被看作是哥德尔递归地定义算术函数时的一个定义解释。在这个解释中，该算术函数仅有一个数字变元（见哥德尔论文本43页）。如果算术函数是有限函数系列中的最后一项，则它是递归的。而在这个算术函数系列中，它的每一个函数由某种规则来递归地定义。而这类规则，又涉及该系列中位于其前面的两个函数。这两个函数，或者是后继函数，或者是一个常元，或者通过从前一个函数替换而获得。
这大概就表明了递归的基本含义，它生成新的客体，但其生成的过程又要依赖于在前的客体和反复使用的规则。也就是，当我们用k元函数g生成k+1元函数h，在g和h之间生成的关系，就是所谓递归。
用递归定义得到的函数，自然就是递归函数。现在，则该提到原始递归函数了，但原始递归函数的确定，又需要对于递归函数中的基本函数有所知。因为，什么是原始递归函数呢？所谓的原始递归函数,它是依赖基本递归函数来定义的。
什么是原始递归函数呢？原始递归函数是建立在基本函数基础之上的，这个基本函数也称作本原函数。本原函数在莫先生《递归论》中列出了25种，这里列出其中四种，这四种称作严格本原函数：
1.函数值与自变元等值的幺函数：Ix = x。
2.函数值与第n个自变元等值的射影函数：Imn（x1,x2,,...xm) = xn。
3.函数值永为零的零函数：0x = 0。
4.函数值永为a的常值函数：Ca(x） = a。
由本原函数出发，经过叠置与原始递归式所作成的函数，这就叫做原始递归函数。
有了本原函数，我们就看到原始递归函数的身影了。而刚刚列出的本原函数，自然也属于原始递归函数。（参见莫绍揆《递归论》第17页）
自从哥德尔研究递归以来，递归性的概念就已经在元数学中发挥了核心作用，但是在这里，关于递归性的理解只不过是理解哥德尔证明其定理所必需的。递归概念的本质特征是二进位关系R，如同以上译文中，证明定理I、定理II和定理III所表示的。
“定理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表示为假]”
也就是说，当一个函数可以用真值函数来表示的时候，这些函数的取值总是或者0，或者1，这样的函数也是原始递归的。于是，递归概念的本质特征就是二进位关系R。
例如，R是否在m和n之间成立，即R（m，n）是真还是假，可以通过从R（0，0）开始向上所作成的一步一步进程来判定，但一定是在判定过程中使用有限数量的递归定义。
一般而言，递归性对于元数学的重要性在于，递归定义让我们看到，递归地定义的无限系列中的每一个数字，它们都是根据规则构造的。因此，关于无限序列的评论，就可以解释为有关构造规则的评论，而不是有关一个给定无限总体的评论。由于这个缘故，有限论和直觉主义的元数学流派的这两类数学思想家，都赞成使用递归这样的数学概念，并且，尽管有哥德尔等人对递归概念的扩展，这些概念都被当今的构造主义者所接受。这些构造主义者，拒绝谈论任何无法递归构造的数学实体。
这篇拖延甚久的读书笔记，先草写到这里。哥德尔原著英译本的汉译接下来是2.4：元数学概念的表达式，哥德尔给出了46个有关原始递归函数的定义，且留待下篇。
https://blog.sciencenet.cn/blog-3478957-1329252.html
上一篇：谓词再议和哥德尔数配置——哥德尔原著英译拆解汉译之六
