“在给定的二进制文件中查找所有代码等效于停止问题."真的吗? [英] "Finding all the code in a given binary is equivalent to the Halting problem." Really?

问题描述

只需阅读有关仿真器的高度投票的问题和语句

事实证明，找到所有 给定二进制文件中的代码是等效的 停止问题.

It's been proven that finding all the code in a given binary is equivalent to the Halting problem.

真的对我伸出了双手.

Really stuck out at me.

那肯定不是真的吗?不仅仅是一个大的依赖图吗?

Surely that can't be true? Isn't it just a large dependency graph?

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

Would be really grateful for some further insight into this statement.

推荐答案

我相信这是查找曾经执行过的所有代码"，即查找覆盖范围，可能与动态生成的代码结合使用.确实可以将其简化为停顿问题.

I believe what is meant is "finding all code that is ever executed", i.e. finding coverage, possibly in combination with dynamically generated code. That can indeed be reduced to the halting problem.

说您有一个完善的覆盖率工具，可以找到程序中可能执行的每段代码(因此其余都是无效代码).给定程序P，该工具还能够确定扩展程序(P ; halt)是否执行过halt指令，或者halt部分是否为无效代码.因此，它将解决暂停问题，我们知道这是无法确定的.

Say that you have a perfect coverage tool that will find every piece of code in a program that may ever be executed (so the rest is dead code). Given a program P, this tool would also be able to decide whether the extended program (P ; halt) ever executes the halt instruction, or whether the halt part is dead code. So, it would solve the halting problem, which we know is undecidable.

这篇关于“在给定的二进制文件中查找所有代码等效于停止问题."真的吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！