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

摘要：

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

关键词：能行可计算性、哥德尔、概念分析、公理化方法

所属期刊栏目：44

分类号：N0:O1

资助基金：中央高校基本科研业务费专项资金数学直觉,机器学习与创造力项目2019NTSS35

在线出版日期：2022-11-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：17-25