--- schema_version: "library-reader-v1" source_type: "original_book" title: "递归与偶然" author: null edition: null publisher: null year: null isbn: "9787576004694" library_document_id: "ea3b7167-0435-4a94-84b9-80a5359326a4" source_sha256: "c6c4c29967cb574649afa134d7480c6fa0dbba332ef3fae7003613904ae1c907" pdf_physical_page_count: 401 pdf_physical_page_index_base: 0 range_start: 150 range_count: 10 html_url: "https://workshop.closeclaw.top/api/ai/read/ea3b7167-0435-4a94-84b9-80a5359326a4?start=150&limit=10" markdown_url: "https://workshop.closeclaw.top/api/ai/read/ea3b7167-0435-4a94-84b9-80a5359326a4.md?start=150&limit=10" previous_url: "https://workshop.closeclaw.top/api/ai/read/ea3b7167-0435-4a94-84b9-80a5359326a4.md?start=140&limit=10" next_url: "https://workshop.closeclaw.top/api/ai/read/ea3b7167-0435-4a94-84b9-80a5359326a4.md?start=160&limit=10" --- # 递归与偶然 > 页码规则：PDF_PHYSICAL_PAGE_INDEX 是从 0 开始的权威文件物理页索引；PRINTED_PAGE 是页面中识别出的印刷页码，可能为空，二者不得混用。 ## PDF_PHYSICAL_PAGE_INDEX=150 | PRINTED_PAGE=138 递归性的数学发展以及20世纪30年代它在通用图灵机中的实现，见证了我们所说的算法的诞生。包括计算机科学家和社会科学家在内的许多人，在解释什么是算法时，经常以菜谱为例。这不完全错误，因为算法确实规定了必须遵循的一系列程序和规则，但这个类比也绝对称不上正确，因为菜谱根本无法解释我们这个时代的算法是什么。因此我想指出，应当通过递归和反思的概念理解算法思维。递归函数所指的，不过是一个不断调用自己直至达到停机状态的函数。侯世达(Douglas Hofstadter)在他的《哥德尔、埃舍尔、巴赫：永恒的金辫子》(Gödel，Escher，Bach：An Eternal GoldenBraid)中用一个笑话解释了这个概念:想象一个德国教授必须用一个全是从句的长句子讲课，最后他只要说出动词，就能结束这次讲授。 首先，理查德·戴德金(Richard Dedekind)在他1888年的文章《数字是什么以及它们应当是什么？》中，正式用递归函数定义了运算和自然数。数学家托拉尔夫·斯科尔姆(Tho-ralf Skolem)在1922年再次拾起这个主题，以重构怀德海和罗素《数学原理》中的逻辑体系。斯科尔姆的激进处在于，他去掉了罗素的存在量词(existential quantifiers)，代之以函数。如今这被称为斯科尔姆化(Skolemnization)。从表面上我们可以[111]把它理解为，存在的问题不再是问题了，因为最终它是个数学函数。① 138 递归与偶然 ① 哥德尔于1969年12月10日致布鲁提亚(Brutian)的信，见哥德尔《全集》，第4卷，第 330页；皮埃尔·卡索·诺盖斯(Pierre CassouNoguès)的《哥德尔的魔鬼，逻辑与愚蠢》(Les démons de Gödel. Logiqueet Folie)也引用了该书，巴黎：Seuil,2007年，第115页。 ## PDF_PHYSICAL_PAGE_INDEX=151 | PRINTED_PAGE=139 随后，哥德尔在他1931年题为“论数学原理中的形式不可判定命题及相关系统 I”(On Formally Undecidable Proposi-tions of Principia Mathematica and Related Systems I) 的文章中，定义了递归函数，又在随后1934年的论文《论形式数学的不可判定命题》（On Undecidable Propositions of FormalMathematics)中定义了一般递归函数。与符号逻辑的形式化相反，哥德尔1931年的论文用数字把形式系统算术化了(如今被称为哥德尔配数[Gödel numbering])，这样不同公理的关系就可以用数字表示；正如我们在表2.1中见到的：每个符号，包括括号，都被赋予了一个自然数。 这样，哥德尔就可以把证明从逻辑推理变成由递归函数组成的运算。在他1931年的论文中，哥德尔这样定义递归函数： 第二章 逻辑与偶然 139 ① 罗德·亚当斯(Rod Adams)，《递归函数和可计算性的早期历史》(An Early History of Recursive Functions and Computability),波上顿：Docent,2011年，第19—32页。 ## PDF_PHYSICAL_PAGE_INDEX=152 | PRINTED_PAGE=140 当存在一个以φ结尾的有限数论函数序列 $\varnothing _ { 1 }$ $\varnothing _ { 2 }$ ,$\scriptstyle \varnothing _ { \mathfrak { n } }$ ，且每个函数 $\rho _ { \mathrm { k } }$ 都递归地由前面两个函数定义，或可通过替换从前面的任意函数中得出，或是一个常数，或是后继函数x+1，则称这个数论函数φ是递归的。① 我们或许可以把这种说法简化为F(x)=kF(x—1)的形式，这个函数返回到它自身和前一个函数的结果上。正因此，我们可以把它与哥德尔对冈瑟提出的反思逻辑的兴趣联系起来。1934年哥德尔在他的论文《论形式数学的不可判定命题》中提出了一般递归函数。他(通过与法国逻辑学家雅克·埃尔布朗[Jacques Herbrand]的通信)注意到，他[112]早先的递归函数不能包括所有有效的可运算函数。在第9节“一般递归函数”中，哥德尔对递归函数做了类似定义： 我们或许可以把这个概念定义如下：如果φ表示某一未知函数，而ψ，…ψ是已知的函数，若ψ和φ能以最一般的方式相互替代，且替换后的某些表达式不变，且如果结果函数方程组对于φ有唯一解，则ψ是递归函数。② 这第二个定义更抽象，因为它涉及两个函数，复杂性程度更高，但它也突出了递归理论的三个主要观点：1.可以用递归函数表示的东西是递归可枚举的，即可计算的；2.它从一个简单函数开始，以达到一个复杂函数，这通常可以用涌现现象说明；3.为了得出已知函数，它首先假定了未知函数，也就是说虽然黑箱不能明确地被知晓，却可以被其他已知函数替代，后者的递归运算能得出与未知函数相同的结果。①哥德尔给出的这个例子可能有助于我们的理解： 140 递归与偶然 ① 哥德尔，《全集》，第1卷，所罗门·费弗曼等人编，牛津：Claren-don,2001年，第159页。 ② 同上，第268页。 ## PDF_PHYSICAL_PAGE_INDEX=153 | PRINTED_PAGE=141 [113]在哥德尔之后，图灵1936年的论文和斯蒂芬·克莱尼(Stephen Kleene，阿隆佐·邱奇[Alonzo Church]的学生)进一步定义了一般递归性——比如不动点定理(FixedPoint Theorem)②和正规形理论(Normal Form Theory)③;随后，邱奇在1937年对图灵1936年的论文《论可计算数及其在判定问题上的应用》(On Computable Numbers，with an Ap-plication to the Entscheidungsproblem)的评论中表示，埃尔布朗—哥德尔一克莱尼的一般递归函数等价于图灵的通用机，以及邱奇的 λ可定义函数(Lambda definable function)。①我们或许可以说，对图灵而言，可计算或可判定的东西总是递归可枚举的，即使有些计算机科学家(如罗伯特·索阿雷)建议用可判定性和可计算性的说法代替递归性，②因为递归一词在日常使用中有多种含义。然而，这种做法会忽略递归形式—它在数学和哲学理解中发挥核心作用—的重要性。一个递归函数可能无法实现其目标，因此不能停机。在这种情况下它会在无限循环中迷失，直至耗尽计算资源，比如耗尽内存，甚至达到机器的物理疲劳上限。而通用图灵机试图规定的正是这种不可判定性，以避免这种无限循环。 第二章逻辑与偶然 141 ① 皮埃尔·利维，《递归的概念，从控制论到联结主义》(Lanotion de récursivité, de la première cybernétique au connexionnisme), 见 Intellectica39,2004年2月，第126页。 ② 这个理论可以简单表述为：对于每一个图灵可计算的总函数f(x),都有一个不动点 n,使 φf(n)=φn(后面我们将看到不动点的说法再次出现，如终止状态[terminal state])。 ③在此我们可以借用索阿雷的总结：存在一个原始递归谓词T(e,x,y)和一个原始递归函数∪(y),对于任何一般递归函数φ(x),都有一个索引 e,使 φ(x)=U(μy T(e, x, y))。见罗伯特·索阿雷(Robert I.Soare)，《可计算性和递归》(Computability and Recursion)，见《符号逻辑简报》(Bulletin o f Symbolic Logic),2,第 3期，1996年，第 301页。 ## PDF_PHYSICAL_PAGE_INDEX=154 | PRINTED_PAGE=142 让我们以斐波那契数列(1,1,2,3,5,8,13,21…)的计算为例，数列中后一个数是两个数之和。给定一个数字N，我们想知道从1到N的序列中的所有数字，递归函数调用自身，进入循环运行，直至达到停机状态，即当数字N的值变为0；N=0或N=1是最终目的的判定标志。 long fibonacci(long N) { if((N==0)|(N==1)) return number; else //recursion step 142 递归与偶然 ①同上，第 297 页；另见威尔弗里德·西格(Wilfried Sieg)，《数学程序与数学经验》(Mechanical Procedures and Mathematical Experience)，见《数学与心灵》(Mathematics and Mind)，牛津：牛津大学出版社，1994年。 ②索阿雷认为，“术语递归’不应再具有‘可计算性’或‘可判定性’的附加含义”。 ## PDF_PHYSICAL_PAGE_INDEX=155 | PRINTED_PAGE=143 [114]值得一提的是，斐波那契数列也是图灵后来的论文《形态发生的化学基础》(The Chemical Basis of Morphogene-sis)的灵感来源，图灵在文中指出，或许可以把形态发生理解为模式生成的递归过程。在达西·汤普森生物形式分析的启发下，图灵提出了一种“化学胚胎学”，以“就它与Wr-cones的关联，解释契波那契数列的出现”。①图灵算法(反应一扩散)成功表明，构成生命的模式和形式是能够生成出来的，②这就像把形式因和目的因单独挑出来，作为计算生物学的因果模型。人们可能会认为图灵是个计算主义者，想把生物学还原为计算，但这种说法会使人们忽略另一点，即他开启了一种新认识论。关键问题在于该如何推进这种新认识模式，以及这种模式如何有助于理解生命。我们只有到后面的章节才能处理这个问题。 如果要用简单的说法重新表达数字递归(digital recur-sion)的概念，那么可以说它是一个在每次迭代中调用自己，直至达到停机状态的函数，停机状态可以是一个预先规定的、可执行的目标，或是对不可计算的证实。必须进一步把这种递归概念从数学命题扩展到更广的应用中。它可以是个数学命题、软件或是像谷歌这样的系统，甚至也可以是个不断与其生活环境互动的生物。这种一般递归思维的实现，便是我所说的算法思维（algorithmic thinking）的产生。与被看作[115]重复的自动化相反，递归是一种被看作算法自我设定和自我实现能力的起源的另一种自动化。哥德尔不是黑格尔主义者，因为他(以误解的方式)拒绝了绝对，他说“不存在绝对知识，一切只凭概率发生”。①然而，他把反思看作一种向高阶逻辑发展的方式。递归的概念及其在图灵机机制中的实现，似乎是技术史中的一个决定性时刻，它吸纳了有机的概念，它的不断改良和突破，也构成了在黑格尔和谢林两个世纪后的哲学化新条件。不过我们现在还不急于总结。接下来，还需要进一步研究有机概念是如何在20世纪早期控制论的背景中被进一步采纳的。 第二章 逻辑与偶然 143 ①图灵给麦克·伍杰(Michael Woodger)的信，未注明日期，1951年 2月12 日收,http://www. alanturing. net/turing\_woodger\_feb51;杰克·科普兰(Jack Copeland)在《图灵概要》(The Essential Turing)的《人工生命》(ArtificialLife)一文中也引用了这句话，杰克·科普兰编，牛津：牛津大学出版社，2004年，第508页。 ②康拉德·瓦丁顿在给图灵的一封信中评论说，图灵的模型可以在“各种斑点、条纹和色斑的产生中找到最重要的应用，这些斑点出现在各种表面上均一的区域，比如蝴蝶的翅膀、软体动物的壳、老虎和豹子的皮等”。引自科普兰，《人工生命》，第510页。 ## PDF_PHYSICAL_PAGE_INDEX=156 | PRINTED_PAGE=144 §21 维纳的莱布尼茨主义 不同于冈瑟的是，维纳没有用黑格尔的语言，而是把莱布尼茨当作控制论的守护人。当然，莱布尼茨不是黑格尔，但他们都对存在的有机性及其在反思中的运作有所反思；正因此，冈瑟把维纳的反馈与黑格尔的反思等同了起来。这不是说莱布尼茨是第一个思考数学和逻辑的人。在他之前，笛卡尔已经建构了一套自动机理论。但在莱布尼茨那里，人们能找到对反思模型的数学和物理解释，这种反思模型把无限折叠在有限的存在中，就像最好可能世界的假说和单子论那样。维纳写道： 144 递归与偶然 ①王浩，《逻辑之旅》，第291页。 ## PDF_PHYSICAL_PAGE_INDEX=157 | PRINTED_PAGE=145 如果我要从科学史上选择一个人做控制论的守护人，我一定会选莱布尼茨。莱布尼茨哲学以两个密切相关的概念为核心——普遍符号主义（universal symbol-ism)和推理演算。如今的数学符号与符号逻辑正由此而来。正如算术演算本身带来了从算盘和台式计算机到[116]今天的超高速计算机的机械化进程，莱布尼茨的推理演算(calculus ratiocinator)则携带着推理机器(machi-na ratiocinatrix)的基因。① 维纳称莱布尼茨是普遍符号主义和推理演算方面的第一位思想家，但这种说法还很模糊和笼统。莱布尼茨对控制论的贡献究竟是什么？探讨这个问题，将使我们为控制论的哲学研究打下基础，并把它与我们在上文讨论的德国理念论联系起来。 正如我们在导论中讲到的，李约瑟认为莱布尼茨是西方哲学史上第一位有机哲学思想家。在莱布尼茨这里，“推理机器”思想家和“有机”哲学家走到了一起，这并非巧合；这种结合是莱布尼茨得以成为控制论守护人的真正原因。莱布尼茨的作品远不只我们在这里试图考察的哲学，但我们想概述一下莱布尼茨经过维纳阐发的一些重要思想。我们要说，维纳认真阅读了莱布尼茨。我们想指出莱布尼茨控制论中有两个重要元素：1. 组合的理论(theory of the combinatorial);2. 无限寓于有限之中的数学模型。这二者是他《单子论》的核心，因为世界由单子组成，单子从某一点出发看世界，从而产生各种组合；单子有着能反映世界本身的镜子，这产生了远超出规则限制的丰富性。莱布尼茨1666年的博士论文《论组合术》(De Arte Combinatoria)提议将人类思维，如观念，理解为符号的不同组合。人脑是一系列基于符号组合的操作，推理则是这些操作的组织。值得注意的是对莱布尼茨来说，思维就是计算，它类似于符号运算，在很大程度上也依赖于符号运算。由此他提出了对笛卡尔主义的批判：他们使用符号思考的程度比他们想象的更高，因此在他们那里符号是未被思考的(impensé)。①组合不是随机的，它们表现为这样或那样是有原因的，这便是充足理由律的原则:Nihil est sine ratione，没有什么是无根据或[117]无原因的。由符号构成的思维旨在“排除争议”，尤其是“杜绝在依据推理的事情方面的争议，因为推理和计算应当是一样的”。② 第二章 逻辑与偶然 145 ①诺伯特·维纳，《控制论：或论动物与机器中的控制和交流》，马萨诸塞州剑桥：麻省理工学院出版社，1985年，第12页。 ## PDF_PHYSICAL_PAGE_INDEX=158 | PRINTED_PAGE=146 至于无限和有限的关系，这是莱布尼茨类比符号操作和思维的基础，它意味着无限刻写在有限之中。对笛卡尔主义者而言，推理要想是完美的，应当包含有限的步骤，这样心灵才能依序前进；莱布尼茨的贡献则是将无限刻写在有限中，这样心灵就能通过有限的符号理解无限。比如，莱布尼茨可以把著名的无理数π呈现为一个由有限的符号组成的公式：$1 - 1 / 3 + 1 / 5 - 1 / 7 + 1 / 9 - \cdots = \pi / 4$ 146 递归与偶然 ① 克莱尔·施瓦茨(Claire Schwarz)，《莱布尼茨——存在的合理性》，巴黎：Belin，2017年，第140页。 ② 莱布尼茨，《莱布尼茨短文及未出版的片段集》(Opuscules et fragments inédits de Leibniz)，路易·库蒂拉(Louis Couturat)编，巴黎： Alcan, 1903 年，第 28 页：“surtout pour exterminer les controverses dans les matières qui dépendent du raisonnement, car alors raisonner et calculer sera la même chose. ## PDF_PHYSICAL_PAGE_INDEX=159 | PRINTED_PAGE=147 如果我们回忆一下德勒兹对莱布尼茨的讨论——无限表现在有限中的方式是褶子(thefold)。这是莱布尼茨在《形而上学论》(Discours de la métaphysique)中提出的“个体物”(in-dividual substance)概念，以及后来《单子论》中的“单子”(简单实体)的核心。他拒绝了笛卡尔把物质实体视为空间中的广延的定义，往实体中添加了一种动力。个体物并不包含全部实体的谓词，因为只有神能做到这一点，它在自身中包含的是能表现按其视角呈现的世界的谓词。我们知道单子没有窗户；相反，它有一个奇怪的装置：镜子。在《单子论》中，镜子是理解这种观点的关键，也是内化的机制。我们或许可以把镜子的机制与递归概念联系起来。单子在世界中，而“在世界中”意味着它之外有别的东西。如果单子能看到自己，就像“我”(I)看着“我”(me)，那么它就在自身之外，这是一个矛盾。相反，如果一切关系都已经包含在个体物的概念之中，且这个概念是由统一性和绝对洞察力而非其形而上学的存在条件定义的，就像路易·库蒂拉所说的那样，①那么我们就无法理解莱布尼茨[118]思想的精妙之处。莱布尼茨通过把否定性的形而上学条件反映进单子中，整合了这些条件，从而“在世界中”不再是一种条件，而是和单子对世界的表现相关。 第二章 逻辑与偶然 147 ①施瓦茨(Claire Schwarz)，《莱布尼茨存在的合理性》，第159 页：施瓦茨引用海德格尔等人的话，做出这句著名的声明：“莱布尼茨的 形而上学是完全基于其逻辑的。”(la métaphysique de Leibniz repose tout entière sur sa logique. ) 下一段：[继续读取](https://workshop.closeclaw.top/api/ai/read/ea3b7167-0435-4a94-84b9-80a5359326a4.md?start=160&limit=10)