"查找给定二进制文件中的所有代码等同于停止问题." 真？

Question

刚刚阅读有关模拟器和声明的高度投票的问题

已经证明,找到给定二进制文件中的所有代码等同于停止问题.

真的困在我身边.

当然不可能是真的吗？这不仅仅是一个大的依赖图吗？

非常感谢对此声明的进一步了解.

Answer 1

我相信这意味着“查找曾经执行过的所有代码”，即查找覆盖范围，可能与动态生成的代码结合使用。确实可以将其减少到停顿问题。

假设您有一个完善的覆盖率工具，可以找到程序中可能执行的所有代码（因此其余都是无效代码）。在给定程序的情况下P，该工具还能够确定扩展程序(P ; halt)是否曾经执行halt指令，或者该halt部件是否为无效代码。因此，它将解决暂停问题，我们知道这是无法确定的。

Answer 2

我不同意拉斯曼。

停机问题是说不P存在可以接受任何程序并决定该程序是否执行halt指令的程序。让我引用维基百科：

Alan Turing 于 1936 年证明，对于所有可能的程序-输入对，解决停机问题的通用算法是不存在的。我们说停机问题在图灵机上是不可判定的。

另一方面，我们不是在尝试制作这样的程序/算法，而是试图在这个/这些特定程序中找到所有代码。如果我们对程序进行逆向工程并看到它立即调用exit()（非常乐观的示例情况），我们已经证明它会调用halt，而这是不可能的？！

如果我们正在尝试构建一个可以运行任何程序的模拟器，那么我们将失败，从那时起您可以（轻松）将其简化为停机问题。但是通常您正在为支持有限数量的游戏卡带（程序）的 Game Boy 之类的东西构建模拟器，因此这是可能的。