递归性的数学发展以及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页。