丘奇论题

丘奇论题（Church’s thesis）

“正整数的能行可计算函数的概念，应当等同于正整数的递归函数……”这个论题是由美国数理逻辑学家A.丘奇于1935年提出来的。它把哥德尔的递归性概念与可计算性概念结合起来。一个函数是可算的，当且仅当它是递归的和图灵可计算的。由于这个论题与图灵可计算性概念密切相关，有时也称作“丘奇-图灵论题”。丘奇论题中的能行可计算性的概念是一个直观的而非已证明的概念。因此，丘奇论题就只是一个论题，而非定理。不过，存在一个由丘奇于1936年证明了的“丘奇定理”，它表述为：不存在一个判定程序来确定谓词演算中的任意公式是否为演算的一个定理。这是对判定问题的一个否定解。丘奇论题用作丘奇定理的前提之一。