丘奇論題

丘奇論題（Church’s thesis）即“正整數的能行可計算函式的概念，應當等同於正整數的遞歸函式……”。這個論題是由美國數理邏輯學家A. 丘奇於1935年提出來的。它把哥德爾的遞歸性概念與可計算性概念結合起來。

丘奇論題（Church’s thesis）
“正整數的能行可計算函式的概念，應當等同於正整數的遞歸函式……”這個論題是由美國數理邏輯學家A.丘奇於1935年提出來的。它把哥德爾的遞歸性概念與可計算性概念結合起來。一個函式是可算的，若且唯若它是遞歸的和圖靈可計算的。由於這個論題與圖靈可計算性概念密切相關，有時也稱作“丘奇-圖靈論題”。丘奇論題中的能行可計算性的概念是一個直觀的而非已證明的概念。因此，丘奇論題就只是一個論題，而非定理。不過，存在一個由丘奇於1936年證明了的“丘奇定理”，它表述為：不存在一個判定程式來確定謂詞演算中的任意公式是否為演算的一個定理。這是對判定問題的一個否定解。丘奇論題用作丘奇定理的前提之一。