"Strong typing vs. strong testing"
no.email at nospam.invalid
Thu Sep 30 20:11:45 CEST 2010
RG <rNOSPAMon at flownet.com> writes:
> Yes, I know I could have used lint. But that misses the point. For any
> static analyzer, because of the halting problem, I can construct a
> program that either contains an error that the analyzer will not catch,
> or for which the analyzer will produce a false positive.
Can you describe any plausible real-world programs where the effort of
complicated static is justified, and for which the halting problem gets
in the way of analysis? By "real world", I meanI wouldn't consider
searching for counterexamples to the Collatz conjecture to qualify as
sufficiently real-world and sufficiently complex for fancy static
analysis. And even if it did, the static analyzer could deliver a
partial result, like "this function either returns a counterexample to
the Collatz conjecture or else it doesn't return".
D. Turner wrote a famous paper arguing something like the above, saying
basically that Turing completeness of programming languages is
The main example of a sensible program that can't be written in a
non-complete language is an interpreter for a Turing-complete language.
But presumably a high-assurance application should never contain such a
thing, since the interpreted programs themselves then wouldn't have
More information about the Python-list