不可知问题

在可计算性理论和计算复杂性理论中，不可知问题是指被证明不可能构造出一种总是导致正确的是或否答案的算法的决策问题。停顿问题就是一个例子：可以证明没有任何算法可以正确确定任意程序在运行时是否最终停顿。

决策问题是无限输入集合上的任何任意是或不是的问题。正因为如此，传统的做法是将决策问题等价地定义为问题返回”是”的输入集合。这些输入可以是自然数，但也可以是其他类型的值，比如形式语言的字符串。使用一些编码，比如哥德尔编号，这些字符串可以被编码为自然数。

因此，一个用形式语言非正式地表述的决策问题也等同于一组自然数。为了保持正式定义的简单性，它是以自然数的子集来表述的。在形式上，一个决策问题是自然数的一个子集。相应的非正式问题是决定一个给定的数字是否在这个集合中。如果一个决策问题A是一个递归集，则称为可解或有效可解，否则称为不可解。

如果A是一个递归可列举的集合，一个问题被称为部分可解、半可解、可解或可证。例子：可计算性理论中的停顿问题在可计算性理论中，停顿问题是一个决策问题，可以表述如下。

给出一个任意程序的描述和一个有限的输入，决定该程序是结束运行还是永远运行。阿兰-图灵在1936年证明，在图灵机上运行的、能解决所有可能的程序-输入对的停止问题的一般算法必然不存在。

因此，对于图灵机来说，停止问题是不可判定的。

哥德尔不完备性定理所提出的概念与停止问题所提出的概念非常相似，而且证明也很相似。事实上，xxx不完备性定理的一个较弱的形式是停顿问题不可逆的一个简单结果。这个较弱的形式与不完全性定理的标准陈述不同，它断言一个既完整又健全的自然数公理化是不可能的。健全的部分是弱化的：它意味着我们要求有关的公理系统只证明关于自然数的真实陈述。由于健全性意味着一致性，这种较弱的形式可以被看作是强势形式的一个推论。

需要注意的是，哥德尔第 一不完备性定理的标准形式的陈述完全不关心一个语句的真值，而只关心是否有可能通过数学证明找到它的问题。该定理的较弱形式可以从停顿问题的不可判定性中得到证明，具体如下。

假设我们有一个健全的（因而也是一致的）、完整的关于自然数的所有真实一阶逻辑语句的公理化。那么我们可以建立一个算法来列举所有这些语句。

这意味着有一种算法N(n)，在给定一个自然数n的情况下，可以计算出一个关于自然数的真实一阶逻辑语句，而且对于所有的真实语句，至少有一个n，使得N(n)可以得到该语句。

现在假设我们想决定具有表示法a的算法是否在输入i上停止，我们知道这个语句可以用一阶逻辑语句来表达，例如H(a,i)。由于公理化是完整的，因此，要么存在一个n，使得N(n)=H(a,i)，要么存在一个n’，使得N(n’)=¬H(a,i)。

因此，如果我们遍历所有的n，直到找到H(a,i)或者它的否定，我们将总是停止，此外，它给我们的答案将是真的（通过健全性）。这意味着，这给了我们一个决定停止问题的算法。

既然我们知道不可能有这样的算法，那么，关于自然数的所有真实的一阶逻辑语句有一个一致和完整的公理化的假设一定是错误的。

不可知问题可以与不同的主题相关，如逻辑、抽象机器或拓扑学。由于存在不可计数的许多不可判定的问题，任何列表，即使是无限长的列表，也必然是不完整的。

不可知这个词在当代有两种不同的含义。第 一种是与哥德尔定理有关的意义，即一个陈述在特定的演绎系统中既不可证明也不可反驳。第二种意义是与可计算性理论有关的，它不适用于语句，而适用于决策问题，这些问题是可计算的。