# The limits of discoveries (Carlo Ghezzi)

The results of scientific discoveries are
seldom expressed as absolute truths. Absolute truths may be the result of a purely
theoretical research which proves a statement (that is, a theorem) in a given mathematical
setting. In practice, as we observed in earlier lectures,
research is an iterative process, through which we validate and refine the research
results, until they reach an acceptable degree of support from experiments. At each stage of this iterative process, research results are an approximation of the “real” results. In this lecture we discuss how approximation
can be assessed and controlled in the research process. We can frame this problem in a logical setting,
through the notions of soundness and completeness. When a researcher studies an unknown phenomenon,
he or she comes out with hypotheses, which constitute a theory that tries to explain
the phenomenon. The theory is sound if all the potential predictions
made by the theory are actually observable for the real phenomenon. As the picture shows, a sound theory only
allows truths to be deduced, but not necessarily all truths. A theory is complete if it can predict all
actually observable manifestations. As the picture shows, a complete theory allows
all truths to be deduced, but also possibly non-true things. Ideally, the theory should be both sound and
complete. The deducible truths from a theory that are
not real truths are called false positives. The real truths that are not deducible from
a theory are called false negatives. Of course deducible truths that are real truths
are true positives. For example, let us go back to the simple
culinary theory we defined in an earlier lecture “All Italians like pasta”. The theory is complete, since it can predict
all Italians who like pasta, but it is obviously unsound. For example, it can be applied to a newborn
Italian to deduce that the infant likes pasta. In this example, infants constitute false
positives. A refinement of the theory like “All Italians
more than 18 years old like pasta” is also unsound, since some existing adult Italians
(who are also false positives) may dislike pasta. Let us consider other kinds of research, different
from the examples we discussed so far, which were all trying to explain real-world phenomena. Suppose that the objective of our is to solve
a novel problem, or to find a better solution to an existing problem for which a solution
is already known. Typically, in Informatics the focus may be
on the invention of a new, clever algorithms for a new problem, or on a new algorithm that
improves efficiency of known algorithms in terms of computation time or consumed storage. The concepts of soundness and completeness
equally apply to problem solutions, and algorithms in particular. A sound algorithm never includes a wrong answer,
but it might miss a few right answers. A complete algorithm never misses a right
answer: it provides the complete set of right answers, but it might include a few wrong
answers. A sound algorithm is conservative (pessimistic). Its dogma is to remain on safe grounds to
get assurance on its results. On the opposite, a complete algorithm is liberal
and optimistic. It is open to more results than may turn out
to be invalid in an attempt to include all results. This is described by this figure: A false negative is a right answer that is
not recognized as such by the algorithm. Likewise, a false positive is an answer provided
by an algorithm that turns out to be wrong. An exact solution is both sound and complete. However, in many cases it may be impossible
or impractical di find an exact solution. We need to accept, and we may be perfectly
happy with, approximate solutions. Certain algorithms are neither complete nor
sound, and thus exhibit both false positives and false negative. The number of false positives and false negatives
is an indication of the inaccuracy of an algorithm. Approximate algorithms are very common in
Informatics. A very important reason is that there are
many problems that are undecidable. An undecidable problem is a decision problem
for which it is impossible to construct an algorithm that always leads to a correct (yes/no)
answer. Undecidable problems are ubiquitous. In particular, most problems concerning program
analysis are undecidable. Program analysis refers to analyzing computer
programs to verify certain properties that assure absence of bugs in the program, or
to exclude certain erroneous conditions. A very simple property may be: every statement
in the program is executable, i.e, it is reachable in some computation. A statement that is never executed is useless:
it constitutes dead code. Although well-written program should contain
dead code, per se it does not indicate an error in the algorithm. However, it is very often the symptom that
there is an error in the program. An algorithm that produces the list of all
unreachable statements would be quite useful in program debugging. Unfortunately, this problem is undecidable,
and an exact algorithm does not exist. Program analysis research has analyzed this
problem and produced approximate solutions. A sound solution produces a list of statement
that are guaranteed to be unreachable (although there can be more). A complete solution would produce a list of
statements that includes all unreachable statements, although they might instead be reachable. Notice that an algorithm that always produces
an empty set of statements would be sound, while an algorithm that always produces all
statements would be complete. However, in these two cases the number of
false negatives and false positives, respectively, would be unacceptable! How can we reason about the adequacy of an
approximate research result? Two notions are commonly used for this purpose:
precision and recall. Precision is defined as the ratio between
tp and tp plus fp. In the case of an approximate algorithm, it
is the fraction of correct answers among the computed answers. Ideally, it should be 1. Completeness is instead defined as the ratio
between tp and tp plus fn. In the case of an approximate algorithm, it is the fraction