不可判定问题

决定性问题是一类根据从一个无限集合中选取的输入值，得出是或否的回答的问题。因此，传统上将决定性问题等同地定义为问题返回值为yes的一组输入集。这些输入值可以是自然数，也可以是其他类型的值，例如形式语言中的字符串。使用一些编码方法，例如哥德尔编号，这些字符串可以编码为自然数。因此，用形式语言非正式表达的决策问题也等价于一组自然数。为了保持形式定义的简单性，决定性问题使用自然数的子集来表达。

形式上，决定性问题是自然数的子集。相应的非正式问题是确定给定的数是否在集合中。如果决定性问题A是一个递归集，那么该问题可以称为可决定的或有效可解的。如果A是一个递归可枚举集，那么该问题可以称为部分可判定、半可判定、可解或可证明的。这意味着存在一种算法，当问题的答案为“是”时，该算法最终会停止运行，但如果答案为“否”，则该算法可能会永远运行。部分可判定的问题和任何其他不可判定的问题称为“不可判定的”。

在可计算性理论中，停机问题是一个决定性问题，该问题可以表述如下：

给定任意程序和有限输入的说明，确定程序结束运行还是永远运行。

艾伦·图灵在1936年证明，在图灵机上运行   的能够为所有可能的程序输入对解决停机问题的通用算法一定不存在。因此，停机问题对于图灵机来说是不可判定的。

哥德尔不完备定理提出的概念与停机问题提出的概念非常相似，论据也非常相似。事实上，第一不完备定理的一个较弱形式就是停机问题不可决定性。这种较弱的形式不同于不完备定理的标准陈述方式，该陈述认为对自然数的所有命题进行完整、一致和合理的公理化是不可能实现的。“合理化”是其中最不易实现的部分:这意味着我们只需要所讨论的公理系统来证明关于自然数的真命题。值得注意的是哥德尔第一不完备定理的标准形式的陈述与问题取值真假完全无关，而只涉及该问题是否能被证明。

该定理的弱形式可以用停机问题的不可决定性进行如下证明。假设我们对所有关于自然数的为真的一阶逻辑命题都能进行一致和完全的公理化。然后我们可以构建一个算法来枚举所有这些命题。这意味着存在一个算法，在给定自然数N的情况下，能够计算出关于自然数的为真的一阶逻辑命题，使得对于所有的真命题，至少有一个N，使得N(n)满足该命题。现在假设我们想要确定当输入值为I时，用a表示的算法是否会停止运行。我们知道这个语句可以用一阶逻辑命题来表示，比如说用H(a，I)来表示。因为公理化是完整的，所以要么存在一个n，使得N(n) = H(a，I)，要么存在一个n'，使得N(n') = ¬ H(a, i)。因此，如果我们遍历所有的数值n，直到找到H(a, i)或它的否定形式，我们最终总会停下来。这意味着这给我们提供了能确定停机问题的算法。既然我们知道不可能有这样的算法，那么关于自然数的所有为真一阶逻辑命题都能进行一致和完整的公理化的假设必然是错误的。

不可判定问题会与不同的主题相关联，例如逻辑、抽象机器或拓扑。请注意，因为有无数个不可判定问题，所以任何列表，甚至是无限长的列表，都必然是不完整的。

不可判定一词在当代有两种截然不同的含义。第一种是哥德尔定理所用的含义，即一个命题在特定的演绎系统中既不可证明也不可反驳。第二种含义与可计算性理论相关，该含义并不适用于命题，而适用于决定性问题，决定性问题是指在一个数量为无限大的，可产出任何是或非解答的问题的集合。如果找不到能够正确回答问题集中每一个问题的可计算函数，则认为这样的问题是不可判定的。这两者之间的联系是，如果一个决定性问题是不可判定的(从递归理论意义上来说)，那么就不存在这样一个一致的、有效的形式系统，该形式系统能够为问题集中的每一个问题A提供证明，即要么“A的答案是肯定的”要么“A的答案是否定的”。

由于“不可判定”一词有两种含义，所以有时使用“自变”一词来代替“既不可证明也不可反驳”意义上的不可判定。然而，“自变”的用法也不明确。它可能仅仅表示“不可证明”，而不管该命题是否可反驳。

在特定演绎系统中，命题的不可决定性本身并不能解决命题的真值是否定义明确这一问题，也不能解决它是否可以通过其他方式确定这一问题。不可决定性仅仅意味着被考虑的特定演绎系统不能证明命题的真或假。是否存在所谓的“绝对不可判定”的命题，即该命题是否取值为真永远无法知晓或真值是否定义不明确，是各家哲学流派争论的焦点。

按照不可判定的第二条含义，最先被怀疑是不可判定问题之一的是群论中的字问题。该问题最早由马克斯·德恩在1911年提出，该问题提出是否存在一个有限呈现群，对于这个群来说，没有算法能够确定两个字是否等价。后来，该问题于1952年被证明是不可判定问题。

哥德尔和保罗·寇恩二人的著作结合在一起给出了两个关于不可判定命题的具体实例(在术语的第一个意义上): 即在ZFC(集合论的标准公理化)中，连续统假设既不能被证明也不能被反驳。同时，在ZF中（ZF是除选择公理之外的所有ZFC公理），选择公理既不能被证明也不能被反驳。这些结论不依赖于完备性定理。哥德尔在1940年证明了这两个实例都不能在ZF或ZFC集合论中被推翻。在20世纪60年代，寇恩证明了两者都不能从ZF得到证明，同时连续统假说也不能从ZFC得到证明。

1970年，俄罗斯数学家尤里·马季亚谢维奇(Yuri Matiyasevich)提出，希尔伯特的第十个问题，该问题不可解，作为1900年提出的对下一个世纪数学家的挑战。希尔伯特的挑战寻找一种算法用以找到丢番图方程的所有解。丢番图方程是一个费马大定理的更一般的例子；我们在任意数量的具有整数系数的变量中寻找多项式的整数根。因为我们只有一个方程，但有n个变量，所以在复平面中存在无穷多个解(并且很容易找到)；然而，如果解仅限于整数值，问题就变得不可能了。马季亚谢维奇通过将丢番图方程映射到递归可枚举集并引用哥德尔不完备性定理证明了这个问题是不可解的。^[1]

1936年，艾伦·图灵证明了停机问题—即图灵机是否会在给定程序上停止运行的问题—在术语的第二种意义上是不可判定的。后来，莱斯定理将这一结论进行了概括。

1973年，萨哈拉·谢拉赫证明了在术语的第一个意义上，群论中的怀特海问题在标准集合论中是不可判定的。

1977年，帕里斯和哈灵顿证明了帕里斯-哈灵顿定理-拉姆齐定理的一个版本-在皮亚诺公理构造的算术公理系统中是不可判定的，但在更大的二阶算术中可以证明为真。

应用于计算机计算机科学中的克鲁斯卡尔树定理，它在皮亚诺公理中也是不可判定的，但在集合论中是可证的。事实上，克鲁斯卡尔的树定理(或其有限形式)在一个更强的系统中是不可判定的，该系统在一种基于称为预测主义的数学哲学的基础上来编纂可接受的原则。

古德斯坦定理是一个关于拉姆齐自然数理论的命题，而科比和帕里斯则证明了该定理在皮亚诺公理中是不可判定的。

格雷戈里·蔡汀在算法信息论中提出了一些不可判定的命题，并这种设定下证明了另一个不完全定理的存在。蔡汀提出的定理指出，对于任何能够包含足够多算术的理论来说，都存在一个上限c，在该理论中不能证明存在任何特定的数具有比c更大的柯氏复杂性，尽管哥德尔定理与说谎者悖论相关，而蔡汀的结论却与贝里悖论相关。

2007年，在约翰·何顿·康威20世纪70年代早期工作的基础上，研究人员库尔茨和西蒙证明了对于考拉兹猜想的本质上概括是不可判定的。^[2]