Was just reading the highly voted question regarding Emulators and the statement
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.
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.