艺术中的递归 递归和原始递归函数——读哥德尔之五

哥德尔不完全性定理又一个需要交代的背景，是所谓递归概念，以及由递归引出的原始递归函数。哥德尔1931年的那篇证明不完全性定理的论文，原始递归函数起到极重要的作用。按照莫绍揆先生的说法，也就是在这篇论文之后，“原始递归函数论”便正式出现了（参见莫绍揆著《递归论》第1页）。

何谓递归呢？本篇首节先来点轻松的不那么严格的描述，只求对于递归有个感觉上的认知。虽然感觉很不可靠，但和感觉很相近的直觉这个词，往往是理解那些高玄知识的初阶。可能是错讹的，但也许错的直觉会成为接受真知的台阶。

一、艺术与实在中出现的可能“递归”

我从《集异壁》讨论递归的文本中找到艾舍尔的一幅木刻画“鱼和鳞”，按《集异壁》的说法，它颇有递归味道。一个东西的副本是这个东西自身的副本，这大概点出了“递归”的基本含义。而艾舍尔的“鱼和鳞”正是用一条鱼的鳞来做一条鱼的副本，构成了一幅鱼和鳞的递归意味的画，不断地复制自身的画。

艾舍尔的《鱼和鳞》（1959）

我又从艾舍尔博物馆再创造的画作中，选出一幅层层递进的作品，这个作品似乎也很有点递归味道，也是那些三角空间不断依自身复制组合而成。线条构图都很简单，但颇给人意味深长的直觉。

艾舍尔风格的再创造作品

为了理解递归，查询欧路字典的结果，竟然弄出一幅类似俄罗斯套娃的画，这个画中还有一层一层自身的画面，正是所谓递归的嵌套风格。但也许只是近似于递归，和纯粹数学意味上的递归虽有相似，却可能还相隔甚远的。

一幅嵌套的彩画

除了画作，再拿点文字构思的递归味道吧，不过，这种以为是递归味道的文字，也许离元数学的递归隔得更远更远，姑且写下来，让仁者见仁、智者见智吧。

一首传播甚广的英国民谣

缺了一颗铁钉，

伤了一只马蹄；

伤了一只马蹄，

折了一匹战马，

折了一匹战马，

损了一位国王；

损了一位国王，

输了一场战争；

输了一场战争，

亡了一个帝国

......。

我忽地联想到了历史，历史是不断地复制自身，构成一条只有时间增量的，递归式的历史套娃呢，还是不断超越自身，隽刻着人类智慧痕迹的时间链条呢？这好像很值得探索，就像数理学者探索无尽宇宙时的那些奇思妙想一样。

二、递归和原始递归函数

（一）归纳定义

递归概念自从哥德尔致力于元数学研究以来，一直都是元数学的核心概念。但是对于理解哥德尔定理证明来说，在哥德尔那里几乎就没有更多有关递归的东西提及，但要理解哥德尔定理的证明，理解这个递归及其相关概念却是必需要做的功课。

看《元数学导论》一书，其在讨论原始递归函数时，一开始就指出：你要证明哥德尔定理的结果，需要发展一个来自直觉的理论以处理数论函数及其谓词。使用这个理论，可以证明数论函数中的每个谓词都可以在形式体系内做算术化的表述。

我们在戴德金和皮亚诺的算术理论中已经看到，一个公理化的算术系统，它在定义自然数系列时，应用了一个一元运算，即所谓后继运算“0’”或者用更通俗的运算符号“+0”，从0开始，一个接一个地在自身基础上生成另外的对象，由此而生成整个自然数系列：

0，0’，0’’,0’’’,......

数字0这个初始的客体称作”原始客体“，运用于初始客体0之上的一元运算“’”称为”原始运算“。在原始客体0之上运行原始运算“‘”的结果，一个接着一个的个体对象，就形成了一个自然数客体类。还真有点老子《道德经》所言“天下万物生于有，有生于无”，并且，“道生一，一生二，二生三，三生万物”的味道。不过，这一自然数生成的方式，现代数学家使用直觉和智慧的结果，则生成了一个元数学，其中的一个重要内容，就是我们现在所讨论的递归论。

德国数学家戴德金首创，在意大利数学家皮亚诺那里完成的算术系统PA，有5个公理，其中的公理5就是数学归纳法。他们两位在发展自然数理论的时候，就是频繁而又系统地使用这种数学归纳法。 使用这种方法，可以用以下的3个语句来构成自然数的定义。

1.0是自然数；

2.如果n是自然数，则n’是自然数；

3.只有由1及2给出的才是自然数。

自然数的这种定义方法，称作“归纳定义”。这种归纳定义之中，已经有了递归的意味。从一个起点，加上一个一元运算“后继”，不断地回归自身而形成另外的客体个体。而所谓递归定义，还不仅仅是不断地回归自身，而是那种依归纳而定义的东西，这需要把函数引入到这种定义之中。遵照莫绍揆先生的说法，戴德金和皮亚诺系统使用数学归纳法，同时也使用原始递归函数。这个原始递归函数的观念，到了1923年，挪威数学家斯库伦（Thoralf  Albert skelem1887-1963）明确地宣称，所有初等数论中的数论函数都可以通过原始递归式得到定义。这样，原始递归函数便开始在数学界，愈益展示它的重要性。（参见莫绍揆《递归论》第1页）

（二）递归定义和递归函数

那么究竟什么样的定义，是递归式的定义呢？这可概略如下：

1.自然数0，用原始运算”’”生成1，这种一元运算式可以用函数表示为φ（0）。

2.把这个赋值的函数所生成的自然数，扩展到任意自然数，于是，就有了函数φ（y），这个φ（y）还可以表示成谓词式函数P（0）。而由这个φ（y）或者P（y），又生成了φ（y’）或者P（y’)，等等。由此，我们就可以说，任意一个自然数都被定义了。

这样的定义方式，就称作递归定义。其中的函数，称作数论的基本递归函数。

递归（recursiveness）定义方法可以说是，借助“数学归纳法”来获取定义的一种方法，因而可看作为数学归纳法定义方法的扩展。运用这种方法，自然数一个接一个地得到定义。有的以0为自然数的起点（哥德尔），有的以1为自然数的起点（戴德金，皮亚诺等数学家以1为起点）。1被定义为0的直接后继，2被定义为1的直接后继，依此类推，直至无穷。对于自然数的递归定义，现在称为“原始递归定义”。

递归定义对于自然数是这样一种指定，一个数字系列中的每一个数字，它是通过指定第一个数字，并且给定一类规则而形成的。这个规则依据第k个数字和k这个数字自身，来指定那个第（k+1）的数字。这被看作是哥德尔递归地定义算术函数时的一个定义解释。在这个解释中，该算术函数仅有一个数字变元（见哥德尔论文本43页）。如果算术函数是有限函数系列中的最后一项，则它是递归的。而在这个算术函数系列中，它的每一个函数由某种规则来递归地定义。而这类规则，又涉及该系列中位于其前面的两个函数。这两个函数，或者是后继函数，或者是一个常元，或者通过从前一个函数替换而获得。

这大概就表明了递归的基本含义，它生成新的客体，但其生成的过程又要依赖于在前的客体和反复使用的规则。也就是，当我们用k元函数g生成k+1元函数h，在g和h之间生成的关系，就是所谓递归。

用递归定义得到的函数，自然就是递归函数。现在，则该提到原始递归函数了，但原始递归函数的确定，又需要对于递归函数中的基本函数有所知。因为，什么是原始递归函数呢？所谓的原始递归函数,它是依赖基本递归函数来定义的。

（三）原始递归函数

什么是原始递归函数呢？原始递归函数是建立在基本函数基础之上的，这个基本函数也称作本原函数。本原函数在莫先生《递归论》中列出了25种，我仅列出其中四种，这四种称作严格本原函数：

1.函数值与自变元等值的幺函数：Ix = x。

2.函数值与第n个自变元等值的射影函数：Imn（x₁,x₂,,...x_m) = x_n。

3.函数值永为零的零函数：0_x = 0。

4.函数值永为a的常值函数：C_a(x） = a。

由本原函数出发，经过叠置与原始递归式所作成的函数，这就叫做原始递归函数。

有了本原函数，我们就看到原始递归函数的身影了。而刚刚列出的本原函数，自然也属于原始递归函数。（参见莫绍揆《递归论》第17页）

自从哥德尔研究递归以来，递归性的概念就已经在元数学中发挥了核心作用，但是在这里，关于递归性的理解只不过是理解哥德尔证明其定理所必需的。递归概念的本质特征是二进位关系R，例如，R是否在m和n之间成立，即R（m，n）是真还是假，可以通过从R（0，0）开始向上所作成的一步一步进程来判定，在判定过程中使用有限数量的递归定义。

一般而言，递归性对于元数学的重要性在于，递归定义让我们看到，递归地定义的无限系列中的每一个数字，它们都是根据规则构造的。因此，关于无限序列的评论，就可以解释为有关构造规则的评论，而不是有关一个给定无限总体的评论。由于这个缘故，有限论和直觉主义的元数学流派的这两类数学思想家，都赞成使用递归这样的数学概念，并且，尽管有哥德尔等人对递归概念的扩展，这些概念都被当今的构造主义者所接受。这些构造主义者，拒绝谈论任何无法递归构造的数学实体。

三、哥德尔论文中的递归概念

对于哥德尔“不可证明性”定理的证明而言，递归的重要性在于以下事实（命题V，第42页）：在给定的数字x₁，x₂，...x_n，之间成立的递归关系，我们给出有关这种关系的每一个陈述，都是用形式系统P中的某个公式f来表达的。而这类公式f，在系统P之内都是可得到证明的。 如果这个公式的陈述为真，则在系统P之内“可证”；如果这个公式的陈述为假，则在系统之内“不可证”。这个为假公式也称作f的否定，记为Neg f，这个“不可证”在系统P之内得到证明，因此也可称作“可证”。哥德尔只概述了一个命题的证明，因为它“没有任何原则上的困难，仅仅稍稍提及”（第51页）。

由于所讨论的关系R是递归的，因此，如果R（x₁，x₂，.... x_n）为真，则可以通过构造有限命题系列，在一个为算术建立的演算系统中使得R（x₁，x₂，.... x_n）得到证明。这个演算系统的有限命题系列，以公理开始，并以R（x₁，x₂，.... x_n）结尾。并且，如果R（x₁，x₂，... x_n）为假，则可以类似地证明这个R（x₁，x₂，... x_n）的否定命题。这个演算或形式系统P由哥德尔设计，用以代表该演绎系统。所以，构成R（x₁，x₂，.... x_n）或其否定命题Not R（x₁，x₂，.... x_n）证明的有限命题系列，将在P中以下述两种情形的公式有限系列来表示：一种情形是公式ƒ，另一种情形是公式Neg f（并非f）。

为了在P中表达那个一步接着一步的定义步骤，正是这样的定义步骤，递归关系的真或者假就被确定，我们将或者构造一个公式f的证明，或者构造一个公式并非f的证明：f或Neg f只会出现在这样的形式系统中，它伴随着某个“证明模式”，而该证明模式中的最后一个公式，就是我们要证明的f或者并非f。因此，如果R（x₁，x₂，... x_n）为真，则有一个f的“证明”，而f就是一个在系统P中的“可证”公式（定义46，第50页）；并且，如果R（x₁，x₂，..... x_n）为假，则Neg f在系统P中，也是一个“可证”公式。

将一个类符号定义为一符号系列，该符号是一个公式，并且正好包含一个自由变元，它可能会出现在公式中的多个位置（第38页）。 在哥德尔的系统P中，类别符号和属性符号之间没有区别，因为“公理模式” V（第42页）可被视为表达了这样的公理：同样类型两个属性，这样的属性总会合在一起，它们是等同的——所谓的外延公理导出了这一点。

如果一个类符号可以解释为表示一个递归算术类，则该类符号是递归的，在这种情况下，用其数字符号变量替换得到的公式将是'可证”或“不可证”，这两者之间的选择，取决于在系统解释中由数字符号表示的数字是否属于此递归类的成员。递归关系符号的定义与此类似（第43页：另请参见第42页）。而需要注意的是，类符号和关系符号都不是基本符号，因为前者包含一个自由变元，而后者包含几个自由变元。

哥德尔定理证明的背景知识，只能浏览这么多了。那篇译者的导论，现在从背景走向了哥德尔的证明过程，这个证明过程，他先不谈可证性，他把我们引向不可证。我们还是跟着导言的思路，下一篇，来看看这个对于形式系统P的不可证，究竟是什么吧。