随后，哥德尔在他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页。