10

只是在阅读关于模拟器和声明的高度投票问题

已经证明，找到给定二进制文件中的所有代码等价于停机问题。

真的对我出手了。

这肯定不是真的吗？它不只是一个大的依赖图吗？

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

4

4 回答 4

5

我不同意拉尔斯曼。

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

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

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

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

于 2011-03-14T15:55:39.120 回答
4

我相信这意味着“查找所有曾经执行过的代码”，即查找覆盖率，可能与动态生成的代码相结合。这确实可以归结为停机问题。

假设你有一个完美的覆盖工具，它可以找到程序中可能执行的每一段代码（所以其余的都是死代码）。给定一个程序P，该工具还能够确定扩展程序(P ; halt)是否曾经执行过halt指令，或者该halt部分是否是死代码。因此，它将解决停机问题，我们知道这是无法确定的。

于 2011-03-14T14:39:56.227 回答
3

有限状态机的停机问题是可以解决的（尽管它可能需要许多生命周期......宇宙），您可能正在模拟的任何机器都是有限状态机。只需运行程序，步数受可能状态数限制；如果在没有停止的情况下超过了这个数字，那么程序将永远不会停止，因为它必须处于循环中。

实际上，除非代码可以使用计算的 goto，否则查找所有代码是一个容易得多的问题。无需运行代码，您只需在每个可能的分支点将所有分支精确地执行一次。

于 2011-03-25T18:09:01.707 回答
0

我同意拉尔斯曼的观点，我相信这个论点可以准确无误。首先，我必须同意“找到给定二进制文件中的所有代码”在这种情况下意味着有一个可计算的函数来确定输入二进制文件中的哪些字节对应于执行的指令。

编辑：如果有人不清楚这里为什么会出现问题，请考虑混淆的机器代码。这种代码的反汇编是一个不平凡的问题。如果您在多字节指令的中间开始反汇编，则会得到错误的反汇编。这不仅会破坏相关指令，而且通常会破坏除此之外的一些指令。等调查一下。（例如，谷歌“混淆和反汇编”）。

使这一点精确的策略草图：

首先，定义一个理论计算机/机器模型，其中程序以多位二进制指令编码，很像“真实”计算机上的机器代码，但要精确（并且它是图灵完备的）。假设二进制编码程序和所有输入。这一切都必须精确，但假设该语言具有（二进制编码的）暂停指令，并且当且仅当它执行“暂停”指令时程序才会暂停。

首先，让我们假设机器不能改变程序代码，但有一个内存可以工作。（在有趣的情况下假设为无限）。

那么任何给定的位要么在程序执行期间运行的指令的开头，要么不在。（例如，它可能在一条指令的中间，或者在数据或“垃圾代码”中——也就是说，永远不会运行的代码。请注意，我没有声称它们是互斥的，例如，跳转指令可以有一个位于特定指令中间的目标，从而创建另一条指令，“在第一次通过时”看起来不像已执行的指令。）。

将 ins(i, j) 定义为返回 1 的函数，如果二进制 i 有一条从位位置 j 开始的指令，该指令在 i 编码的程序的运行中执行。否则将 ins(i,j) 定义为 0。假设 ins(i,j) 是可计算的。

让 halt_candidate(i) 成为以下程序：

for j = 1 to length(i)
  if(i(j..j+len('halt')-1) == 'halt')
    if(ins(i,j) == 1)
      return 1
return 0

由于我们不允许上面的自修改代码，因此程序停止的唯一方法是在某个位置 j 处有一条“停止”指令被执行。按照设计，halt_candidate(i) 计算停止函数。

这提供了证明的一个方向的非常粗略的草图。即，如果我们假设我们可以测试程序 i 是否在位置 j 对所有 j 都有一条指令，那么我们可以编写暂停函数。

对于另一个方向，必须在形式机器内对形式机器的仿真器进行编码。然后，创建一个程序加上输入 i 和 j 来模拟程序 i，当执行位位置 j 处的指令时，它返回 1 并停止。当执行任何其他指令时，它会继续运行，并且如果模拟曾经模拟 i 中的“暂停”功能，则模拟器会跳转到无限循环。那么 ins(i,j) 等价于 halt(emulator(i,j))，因此停机问题意味着查找代码问题。

当然，必须假设一台理论上的计算机相当于著名的无法解决的停机问题。否则，对于“真正的”计算机，停机问题是可以解决但难以解决的。

对于允许自修改代码的系统，参数更复杂，但我希望不会有那么不同。

EDIT: I believe a proof in the self-modifying case would be to implement an emulator of the system-plus-self-modifying-code in the static code plus data system above. Then halting with self-modifying code allowed for program i with data x, is the same as halting in the static code plus data system above with the binary containing the emulator, i, and x as code plus data.

于 2014-05-22T13:08:45.883 回答