- The algorithm must be complete, meaning (in this context) that it never misses a error when one is present (no false negatives).
- The algorithm must be sound, meaning (in this context) that is never reports a error when one is not present (no false positives).
- The algorithm must always return some answer.
Error Reports
How do compilers finding and report errors at compile time? In a word, imperfectly. That statement can be made with confidence because it is provably the case that no algorithm exists for catching semantic errors. This statement relies on a strict definition of algorithm: an algorithm must return a correct answer for every input. In the context of reporting semantic errors, the algorithm must necessarily meet the following three qualifications:
There is a theorem, Rice's theorem, that effectively proves that these three conditions cannot be simulteanously be met. As such, error reporting must give up at least one of the conditions. Since it is unacceptable to fail on condition 3 (i.e. the compiler should guarantee termination), it needs to give up on completeness or soundness. In practice, the compiler may give up on both in order to minimize false positives and false negatives.