If you're seeing this message, it means we're having trouble loading external resources on our website.

如果你被网页过滤器挡住,请确保域名*.kastatic.org*.kasandbox.org 没有被阻止.

主要内容

不可判定问题

有些问题需要很长时间才能解决,因此我们使用提供近似解决方案的算法。 世界上存在着一些问题,即使使用世界上最强的计算机,即使时间无限,也 无法 解决不可判定问题。
不可判定的问题 指预期应该给出“是”或“否”的答案,但至今还没有任何算法能够在所有的输入参数下,能给出正确答案。

停机问题

阿兰·图灵在1936年通过找到一个例子,即现在著名的“停机问题”,证明了存在不可判定的问题:
根据其代码和输入,特定程序是否能够完成运行?
例如,思考下面这个倒数程序:
num ← 10
REPEAT UNTIL (num = 0) {
  DISPLAY(num)
  num ← num - 1
}
这个程序将停止,因为num最终变为0。
对比这个计数程序:
num ← 1
REPEAT UNTIL (num = 0) {
  DISPLAY(num)
  num ← num + 1
}
它会 永远 数下去,因为num永远不等于0。
算法 确实 存在,可以正确预测第一个程序停止,第二个程序永远不会。这些是简单的程序,不会根据不同的输入而改变。
但是,不存在可以分析 任何 程序代码并确定它是否停止的算法。
为了证明这种算法不可能存在,图灵使用了“反证法”。
我们首先想象一个算法 确实 存在,可以确定程序的暂停性。
然后我们提出了一个名为 HaltChecker 的程序,它接受两个输入,程序的代码和该程序的输入。然后,使用理想暂停算法返回“暂停”或“从不”。
此流程图可视化 HaltCacher
如果我们将那些先前的程序输入 HaltChecker,我们会看到倒计时程序导致“停止”,而计数程序导致“从不”。 请注意,这实际上不是 运行 程序,程序正在查看不同的代码并根据代码结构进行决策。
但现在我们提出了一个名为Reverser 的程序。它需要单一输入,一个程序的代码。 它发送 HaltChecker 程序作为要分析的程序和程序的输入。然后HaltChecker 确定输入程序在作为输入给定时是否停止。如果 HaltChecker返回“停止”,则Reverser运行无限循环。如果HaltChecker返回“never”,则Reverser立即返回。
此流程图可视化 Reverser
如果我们将倒计数程序输入Reverser,它将看到HaltChecker返回“halts”,因此判断为无限循环。
如果我们将计数程序输入Reverser,它会看到HaltChecker返回“never”,因此决定立即返回。
Reverser 确实是一个奇怪的程序。当它发现另外一个程序 停止并可能永远运行下去时,它就停止,当发现一个程序 停止时,它就永远运行下去。很奇怪,但没问题,这个世界是容许奇怪的程序存在的。
但这有一个会让它分崩离析的地方:如果我们将Reverser 自己 输入Reverser 会发生什么?
HaltChecer 分析了Reverser代码,以确定是否停止。如果它判断代码不停止,那么它返回“never”。reverser 看到该结果并立即返回。
但是,等一下!HaltChecker刚刚声称Reverser永远不会停止,然后它继续前进并停止。 HaltChecker 没有 给我们一个正确答案。
如果 HaltCacher 返回 "halts" 则怎么办?当 Reverser 看到结果时,它会无限循环。
HaltChecer 刚刚声称Reverser 停止,但它却永远循环。再次,HaltChecer 没有 给我们正确的答案。事实上,HaltChecer 无法为我们在这种情况下的正确答案。
因此,我们已经证明,完全正确的停止预测算法 永远不存在,而停止问题是不能确定的。
需要花上一段时间才能真正理解停止问题。如果你也遇到一些麻烦,这个动画视频可能有助于你理解。

更多无法确定的问题

计算机科学家和数学家发现了更多不可判定的问题。其中相当一部分,一旦简化,看起来就像停止问题的另一个案例。通常,所有不可判定的问题都围绕着确定程序输入和输出属性的难度。
当我们处理一个不可判定的问题时,要意识到这一点很有帮助。 然后我们可以接受我们的程序无法在所有输入上正确回答是或否,并提出不同的方法。
例如,我们的Khan Academy编程环境试图避免运行带有无限循环的程序,以防止糟糕的浏览器无响应情况。但是我们怎么知道一个程序有无限循环呢? 我们不能,这是不可判定的!相反,我们监视循环需要多长时间,并且当循环花费太长时间时,我们拒绝运行代码。我们无法确定该循环是否会永远存在,但出于我们的目的,安全永远比说抱歉好。
🙋🏽🙋🏻‍♀️🙋🏿‍♂️您对此主题有任何疑问吗? 我们很乐意回答-只需在下面的问题区域中提问即可!

想加入讨论吗?

尚无帖子。
你会英语吗?单击此处查看更多可汗学院英文版的讨论.