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

G?del and Computability Theory: Could G?del Have Had Church-Turing Thesis?

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

To identify the informal concept of ‘‘effective calculability’’ with a rigorous mathematical notion like ‘‘general recursiveness’’ or ‘‘Turing computability’’,this is called “Church-Turing Thesis” and usually considered one of paradigmatic cases of conceptual clarification via logical methods.This paper,by focusing on G?del’s role in the development,attempts to answer the following two questions from both the historical and philosophical aspects:(1) why is G?del reluctant to launch a similar thesis like CTT while with all the technical points at his disposal?(2) although dissatisfied with Church’s Thesis,why is G?del eventually convinced by Turing’s analysis and CTT?I will propose a solution different from Feferman and Davis in light of G?del’s conceptual realism and explore the superiority of Turing’s Thesis over Church’s Thesis from the perspective of axiomatic method of conceptual analysis,hoping to shed light on both G?delian realism and the epistemological challenges raised by CTT.