递归不可判定

确定谓词 predicate 对于给定的 , ..., 值是否为真或假，被称为其 判定问题。谓词 的判定问题被称为递归可判定的，如果存在一个 全 递归函数 使得

(1)

鉴于可计算性和递归性的等价性，这个定义可以被重述，参考 可计算函数 而不是 递归函数。

停机问题 是最早被证明为递归不可判定的问题之一。停机问题 和许多其他递归不可判定问题的递归不可判定性的表述是基于 哥德尔数。例如，判定对于任何给定的 ，哥德尔数为 的 图灵机 是否是全图灵机的问题是递归不可判定的。希尔伯特第十问题 可能是最著名的递归不可判定问题。

大多数递归不可判定性的证明使用归约。它们表明，所研究问题的递归可判定性将暗示另一个已知为递归不可判定问题的递归可判定性。就直接证明而言，它们通常采用 康托尔对角线方法 的思想。