halting-problem - 如何证明暂停问题无法确定，该如何工作？

Question

我正在查阅Sipser计算理论导论中的“暂停问题”的证明，而我主要关心的是以下证明:

如果TM M不知道何时循环(它不能接受或拒绝，这就是TM对于所有字符串都可识别图灵的原因)，那么决策者H将如何确定M是否可能在循环中？当TM D进行处理时，也会遇到相同的问题。

Answer 1

这是“矛盾的证明”，是荒谬的还原。 (拉丁词组在理论课上总是很好的……当然，只要它们有意义即可。)

该程序H只是具有两个输入的程序:表示某台机器的程序的字符串和一个输入。为了证明的目的，您仅假设程序H是正确的:如果M以w接受，它将简单地停止并接受。您无需考虑它将如何做到这一点。实际上，我们将证明它不可能，没有这样的程序H可以存在，...

因为

如果存在这样的程序，我们可以立即构造H无法确定的另一个程序H'。但是，根据假设，没有这样的程序:H可以决定一切。因此，我们不得不得出结论，即不可能像我们定义的H那样定义程序。

顺便说一句，考虑到它的使用频率，尤其是在计算机科学中，还原证明方法比您预期的更具争议性。您应该不会感到尴尬而觉得有点奇怪。魔术术语是“非 build 性的”，如果您真的有野心，请向您的一位教授询问有关埃雷特·毕晓普对非 build 性数学的批评。