I wrote a first answer about partial correctness, which has a precise
technical meaning. I thought better to separate this other answer which I initially though to be technically very
different. It turns out not to be quite true, but both answers are long enough, so I thought better not to merge them
Apparently it seem that the OP is more interested in an idea of programs that
are partly incorrect, of finding answers that incorrect in some respect, though, I guess, hopefully not too far of being correct.
There are actually two way you may want to consider closeness to correct for a function:
whether computed answers have correct aand incorrect parts, or
whether they are sometimes correct, and sometimes incorrect.
But these two aspects can be combined. If you manage to define something
like a distance between values in the answer set, you can then
try to extend that into a distance between functions that is,
extremely informally, some kind of integral of the distance
of their result for every point of their domain, or some other function of the incorrectness for every point of the domain.
Then the issue may be to determine if the distance between the
completely correct function and the programmed one does not exceed
some fixed threshold, or whether the error on the result of applying the function does
not exceed for each domain point a threshold that may be related to
this domain point.
These techniques may also be useful to do computation as correct as possible, with data that is in some sense not correct to begin with, such as experimental results. When the degree of incorrectness can be evaluated or hypothesized, this can help keep track of its effect on computation.
This is probably very dependent on the kind of data you are computing
I believe there is already such a theory for numerical computing, and
is often applied for technical work, but I know little of it. Elementary aspects are often taught in physics courses.
Much numerical computation deals with real numbers. It cannot be
exact (correct) because computer use only approximations of real
numbers (there is a concept of computing with exact real arithmetics,
but it is a very different topic, very much related theoretically to
partial correctness). Aproximations in numerical computation cause
small errors (rounding errors) that can propagate, and sometimes grow
out of hand. Hence numericians have developed techniques to analyse
their programs and evaluate how close the answer is to the correct
result. They actually design their algorithms so as to minimize the
computational errors, in addition to the other usual criteria, because
the order of some operations may have a profound influence on the the
size of the error being propagated.
These techniques are also important because they often have to deal
with physical data that is itself only "close to correct", i.e. given
with some approximation. Handling the errors on the input together
with computational errors, and their propagation is, I believe, the
object of significant research in the field of Numerical Analysis. But
I am no expert. Some program will compute both the approximate result
and an error interval around it where the correct answer is to be
found. This compounds both the physical measurement errors and the numerical computation errors.
However, while this was essentially unavoidable in numerical
mathematics dealing with reals (a continuous set of values), there no
similar built-in limitation on symbolic computation, hence no obvious
incentive, a priori, to develop similar techniques. Furthermore, it
may not be obvious to do it.
Still, a close look at error handling techniques in parsing and natural language processing show that they actually use a similar conceptual view, even in a purely symbolic context.
The answer of Shaull seems to indicate that one may be interested in
such approximation ideas in software engineering, but I am not sure it
deals with the same concepts. I have not read his paper and I have read
little of the litterature on this topic, and the answer gives no hint
of the techniques he may be considering.
It may be a very different idea, since software engineering is
much concerned with measuring how buggy the sofware may be, but
inadvertantly buggy. I know that some statistical analyses show that
various parameters that can be measured on a program are statistically
related to the quality of the program, it maintainability and the
likelihood of bugs.
The ides of approximate answers in numerical analysis (for example) is not a matter
of bugs, but of handling the limitations of physical measurements, as well as the limitations of computing (which is
inherently countable) when it is used to deal with reals (which are
uncountable). If it is a bug, that is the fault of our universe, not
Attempting to unify the issues: partial correctness and incorrectness measurement
The following is purely speculative, and an indication of work that
could be done. I would suspect that at least some of it has been done already
(I did not search thoroughly). But I do not recall reading about it
and cannot give proper references. The description is only a sketch, and it
is likely that much of it should be refined or made more precise,
including the choice of definitions. I cannot garantee anything that I
have not fully worked out mathematically (and even then ... :).
There is published litterature on real number computation based on
definitions of real numbers approximations that organizes them in a
Scott domain. Approximating reals with intervals is certainly a way to
do it, and that is one proper way of developping a theory of
computability over the reals. My guess is that it must have already
been done, and it offers a good basis for a semantics theory, and for
analysing real number crunching programs together with an assessment of the
precision of the result as described above. (I did not have the
opportunity to ask a specialist).
Now this may be a hint on what to do with symbolic computation, or
with computation over the integers, to get a notion of approximately
correct computation, espcially in the presence of complex data,
i.e. the use of data structures.
The basic idea is the same as for real, use a concept of approximation
and organize your computation domain (the values you compute with) as
a Scoot domain. However, it will need to be something like a
lattice, where two elements must have a greatest lower bound (glb
or meet) as well as a least upper bound (lub or join). In the
numerical case, the glb corresponds to the smallest interval
containing 2 other intervals, and the lub to interval intersection.
Taking our sorting example from the first answer, sorting an array of 5 numbers $[25, 36, 3,
9, 12]$, we could consider all partial arrays as a lattice, and have:
Now, if you define a notion of distance in the order structure,
then you can define the distance between two possible answers as the
sum of their distances to their glb (or some other symmetrical and
monotonically increasing function of these two distances).
If the domain does not have glb, you can take the distances according
to each of the lower bounds (actually only the maximal elements of the
set of lower bounds), and consider the smallest such distance
(or possibly some other function of the distances of maximum elements,
with adequate properties).
The inportant point is to have a tractable definition of correctness
distance over the data you manipulate.
Then, this notion of distance can then be extended to mesuring
distances between functions, which should be an answer to the question
asked. I am not sure how much extra mathematical aparatus is needed,
since some form of integration (in the calculus sense) may be needed.
A cursory search of the web about these issues yielded the following
paper: "Towards Computing Distances between Programs via Scott
Domains" which is already 15 years old. It should provide a better
mathematical background. But I found it after writing this answer.
This problem can possibly be adressed with other logic, but I suspect it is
much more an issue for the concept of approximation within domains of
values. There are other ways to build them than the one described above for arrays. Defining approximations to data could be part of the definition of an abstract data-type, or of a class in OO programming.
Note: I did not expect this connection with my previous answer. hence the two separate answers.