3 ms·
Running the program to see if it ever stops is an easy way to solve the halting problem. The trick, of course, is that you need infinite time to be sure of a "n
by mikeash 10y ago
Running the program to see if it ever stops is an easy way to solve the halting problem. The trick, of course, is that you need infinite time to be sure of a "never halts" answer.
Turing's proof essentially says that there is no way to be sure of knowing what an arbitrary program will do except for running it and seeing what it does.
It's an imperfect technique for real-world programs, but so is everything. Think of it as being like static code analysis versus runtime "sanitizer" tools. Both are useful, and both can detect problems the other can't.
- zAy0LfpBZLC8mAC 10y ago> It's an imperfect technique for real-world programs, but so is everything. No, it's mostly a bullshit technique. The thing is that the malware author can see "how much" of the halting problem AV software "solves", and then deliberately hide their bad/suspicious actions just out of reach of that limit. Simple everyday heuristics are good for a lot of things, but the one thing that they are mostly ineffective against is intentional deception.