哥德尔与可计算性理论——哥德尔可以有丘奇-图灵论题吗?

摘要

将非形式的“能行可计算性”概念等同于严格的数学概念“一般递归函数”或是“图灵可计算性”,这被称之为“丘奇-图灵论题”(Church-Turing Thesis,CTT),它被视为用逻辑的方式来澄清概念的一个典范。本文以哥德尔在可计算性理论发展中的角色为参照点,从历史考察以及哲学分析的角度来试图回答这样两个相关的问题:虽然哥德尔已经掌握了足够的技术细节,但是他为什么不愿意提出一个后来被证明是和CTT等价的“哥德尔论题”?其次,尽管对丘奇论题非常不满,但是为什么哥德尔后来还是为图灵的分析信服而最终愿意相信CTT的正确性?本文将从哥德尔的概念实在论视角出发提出一个不同于费佛曼和戴维斯的回答,并且以概念分析的公理化方法考察图灵论题相对于丘奇论题的优越性,以期更好地理解哥德尔的实在论和CTT所带来的认识论挑战。