$(n + 1)$ points are required to uniquely determine a polynomial of degree $n$; for instance, two points in a plane determine exactly one line.How many points are required to uniquely determine a computable function $f : N \rightarrow N$, given the length of a program that computes $f$ in a fixed language? (i.e. a bound on the Kolmogorov complexity of $f$).The idea is that, at least theoretically, one could prove the correctness of a program by making enough tests.If one has a program $P$ of length $L$ that computes $f$, there is a bound on the number of functions that can be computed with a source length of at most $L$.Therefore one would only need to prove that:$f$ can be computed with a source length $\leq L$$P$ does not compute any other function computable in $L$ bytes or less (by testing)This idea has probably no practical consequences (the bounds are surely bound to be exponential).
Can testing show the absence of bugs?
cc.complexity theory;computability