遞迴不可判定

確定謂詞 predicate 對於給定的 , ..., 值是否為真或假，被稱為其 判定問題。謂詞 的判定問題被稱為遞迴可判定的，如果存在一個 全 遞迴函式 使得

(1)

鑑於可計算性和遞迴性的等價性，這個定義可以被重述，參考 可計算函式 而不是 遞迴函式。

停機問題 是最早被證明為遞迴不可判定的問題之一。停機問題 和許多其他遞迴不可判定問題的遞迴不可判定性的表述是基於 哥德爾數。例如，判定對於任何給定的 ，哥德爾數為 的 圖靈機 是否是全圖靈機的問題是遞迴不可判定的。希爾伯特第十問題 可能是最著名的遞迴不可判定問題。

大多數遞迴不可判定性的證明使用歸約。它們表明，所研究問題的遞迴可判定性將暗示另一個已知為遞迴不可判定問題的遞迴可判定性。就直接證明而言，它們通常採用 康托爾對角線方法 的思想。