3 ms·
"It is a mathematical impossibility for the behaviour of Turing-complete code to be analyzed by machine." This is categorically false. There ar
by aidenn0 15y ago
"It is a mathematical impossibility for the behaviour of Turing-complete code to be analyzed by machine."
This is categorically false. There are plenty of static analysis tools that can determine if programs written in turing-complete languages will halt. They can't do it for every program, but they can do it for large numbers of useful programs.
Simple counterexample: python is turing complete, yet it is possible to mechanically analyze and determine a whole lot about this program:
print "Hello, World!"
Yes, that's a stupid example, but it demonstrates that the premise of this article is false.
As further example that the author misunderstands the issue is the quote: "That, or viewing your website means I have to pore over every line." If good static analysis tools can't figure it out, it is less likely that a person will.
Static analysis tools running on Turing complete languages are a useful tool. Sometimes they answer "I don't know" at which point you will have to decide if you trust the author or not, but the vast majority of code out there is fairly tractable.
[edit] It is true that it is a mathematical impossibility for all possible programs in a turing-complete language to be analyzed, but that doesn't mean that there don't exist programs that are analyzable and has little bearing on whether or not real-world programs are analyzable.
- zeteo 15y ago>There are plenty of static analysis tools that can determine if programs written in turing-complete languages will halt. But they're heuristic, which means if their use ever becomes widespread it will be very easy for malicious software writers to defeat them on a case-by-case basis.
- aidenn0 15y agoThey need not be heuristic. It is possible to formally prove things about programs in Turing-complete languages.
- zeteo 15y ago>It is possible to formally prove things about programs in Turing-complete languages. But not about arbitrary programs you download from the Internet. For such programs you need to require either that they include a custom proof, or that they're written in a non-Turing complete language so that you can check safety yourself.
- gbhn 15y ago... or you could adopt a personal policy of just not running such programs. That's the top-level poster's point -- the boundary between statically-analyzable and not is extremely complex, and not coincident with Turing-completeness.
- ScottBurson 15y agoYes, this is the operative point. Analyzing intentionally obfuscated code is a whole different deal than analyzing ordinary code. Throw in an interpreter for a bizarre language of your own design, along with some code in that language, and you will frustrate any extant static analyzer.