4 ms·
>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
by 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.