丘奇论题

也叫丘奇－图灵论题。20世纪30年代中期，丘奇、图灵、马尔科夫三人在提出他们各自的理论之后，都曾断言他们所定义的函数类(参看λ可定义函数、图灵可计算函数和马尔科夫算法可计算函数)等同于能行可计算函数的类。由于不久就证明了λ可定义函数、图灵可计算函数、部分递归函数、波斯特系统可计算函数、马尔科夫算法可计算函数等概念都彼此等价。于是丘奇等人的断言很快就得到公认，文献中称为丘奇论题或丘奇－图灵论题。在现代文献中一般是如下陈述的：

丘奇论题 直观意义下的能行可计算函数的类恰好就是部分递归函数的类。

丘奇论题并不是一个严格的数学命题。它涉及两个概念：能行可计算函数和部分递归函数。前者是一个没有严格定义的直观概念，后者是一个严格定义的数学概念。因此并不存在在数学意义下证明丘奇论题的问题。丘奇论题不过是宣布对能行性这一直观概念所作的种种刻画是恰当的、成功的。它的真理性要靠实践来检验。几十年来一直没有发现反例，这个事实也更加坚定了人们对丘奇论题的信任。

现代的递归论文献经常采用丘奇论题作为一种证明手段(称为使用丘奇论题的证明)——要证明某个函数是部分递归的，只要给出一个计算它的直观算法就行了。这种证明方法已得到普遍认可。