两条之中,第二递归定理尤为重要,它是数学中对"自指"(self-reference)现象最简洁、最有力的统一陈述:它只有一步对角线证明 `c = S(e, e)`(S 是"把程序的部分输入写死、生成新程序"的柯里化操作,详见 §2.3),却统一了从罗素悖论(1901)、Gödel 不完备定理(1931)、Turing 停机问题(1936)、von Neumann 自复制自动机(1948)到今天的 quine 程序(1960s)等全部自指现象——它们本质上是同一种对角线/自指结构的不同化身(详 §5.7)。 | 两条之中,第二递归定理尤为重要,它是数学中对"自指"(self-reference)现象最简洁、最有力的统一陈述:它只有一步对角线证明 `c = S(e, e)`(S 是"把程序的部分输入写死、生成新程序"的柯里化操作,详见 §2.3),却统一了从罗素悖论(1901)、Gödel 不完备定理(1931)、Turing 停机问题(1936)、von Neumann 自复制自动机(1948)到今天的 quine 程序(1960s)等全部自指现象——它们本质上是同一种对角线/自指结构的不同化身(详 §5.7)。 |