<p>(This was meant as a comment, but went long).
Very interesting question.
If you are willing to think about other complexity measures besides Kolmogorov's, then there are some answers in Learning theory that might satisfy you. I leave it for the experts in the area.</p>

<p>For example, if I'm not mistaken, in "A theory of the learnable" Valiant proved that a boolean function can be reconstructed given a polynomial number of "positive points" on the size of its k-CNF formula (for any fixed k, and I mean
with "positive points" those of the form $(x_1,\ldots,x_n,1)$).</p>

<p>In Knuth's TAOCP 7.2.1.6 it is shown in an astonishing way (using the Christmas tree pattern) that to reconstruct a monote boolean function (i.e. non-decreasing in each variable) you need exactly ${n+1 \choose \lfloor n/2\rfloor+1}$ points.</p>

CC BY-SA 3.0
2011-08-09T20:26:37.060Z
2011-08-10T05:11:47.057Z
2011-08-10T05:11:47.057Z
didest
<p>To continue along the lines of Deigo's answer, standard sample complexity bounds from learning theory tell you that if you are satisfied with finding a program which is "approximately correct", you don't need to try very many points at all. Lets say we are encoding programs in binary, so that there are only $2^d$ programs of length d. Lets suppose also that there is some distribution over input examples $D$. Perhaps your goal is to find a program which you are pretty sure is almost right ("Probably Approximately Correct" i.e. as in Valiants PAC learning model). That is, you want to run an algorithm that will take in a small number of samples $x \sim D$ together with $f(x)$, and will with probability at least $(1-\delta)$ output some program $P$ which agrees with $f$ on at least a $(1-\epsilon)$ fraction of inputs drawn from $D$.   </p>

<p>We will simply draw $m$ examples $x \sim D$, and output any program $P$ of length $\leq d$ that agrees with $f$ on all of the examples. (One is guaranteed to exist since we assume $f$ has Kolmogorov complexity at most $d$)...</p>

<p>What is the probability that a particular program $P$ that disagrees with $f$ on more than a n $\epsilon$ fraction of examples is consistent with the $m$ examples we selected? It is at most $(1-\epsilon)^m$. We would like to take this probability to be at most $\delta/2^d$ so that we can take a union bound over all $2^d$ programs and say that with probability at least $1-\delta$, no "bad" program is consistent with our drawn examples. Solving, we see that it is sufficient to take only
$$m \geq \frac{1}{\epsilon}\left(d+\log 1/\delta\right)$$
examples. (i.e. only linearly many in the Kolmogorov complexity of $f$...)</p>

<p>BTW, arguments like this can be used to justify "Occam's Razor": given a fixed number of observations, among all of the theories that explain them, you should choose the one with lowest Kolmogorov complexity, because there is the least chance of overfitting. </p>

<p>Of course, if you only want to check a single fixed program in this way, you only need $O(\log(1/\delta)/\epsilon)$ examples...</p>

CC BY-SA 3.0
2011-08-10T18:38:25.823Z
2011-08-10T18:38:25.823Z
Aaron Roth
<p>Here's a trivial answer: assuming $L \ge \lg |N|$, then you need to know the value of $f$ at all $|N|$ points to uniquely determine $f$.  Therefore, the approach you sketch doesn't help you at all, unless you somehow know that the length $L$ of the program is extremely short: much shorter than $\lg |N|$ bits.</p>

<p>Consider the family of functions $F=\{f_i:i\in N\}$, where $f_i$ is defined to be the function $f_i(x) = 1$ if $i=x$ and $f_i(x)=0$ if $i\ne x$.  Notice that the Kolmogorov complexity of computing $f_i$ is about $\lg |N|$ bits, since you can hardcode the value of $i$ in the source code and then all you need is a simple conditional statement ($O(1)$ extra).</p>

<p>However, you cannot distinguish $f_i$ from the all-zeros function unless you test it at the input $i$.  You cannot distinguish $f_i$ from $f_j$ unless you test at the input $i$ or $j$.  Therefore, you'll need to evaluate $f$ at all $|N|$ inputs, to uniquely determine which $f_i$ we are dealing with.  (OK, technically, you need to evaluate it at $|N|-1$ inputs, but whatever.)</p>

CC BY-SA 3.0
2013-06-15T00:54:21.857Z
2013-06-15T00:54:21.857Z
D.W.
<p>You can make the program arbitrarily long. So given any program, you can decide whether its language is equivalent to that of this program. You can't do that by Rice's theorem.</p>

CC BY-SA 3.0
2011-07-09T13:22:59.873Z
You have a valid point that the idea of checking the program by running it on several instances will not work in general.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-06T10:42:06.600Z
2011-07-06T10:42:06.600Z
Zirui Wang
<p>$(n + 1)$ points are required to uniquely determine a polynomial of degree $n$; for instance, two points in a plane determine exactly one line.</p>

<p>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$).</p>

<p>The idea is that, at least theoretically, one could prove the correctness of a program by making enough tests.</p>

<p>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$.</p>

<p>Therefore one would "only" need to prove that:</p>

<ul>
<li>$f$ <strong>can</strong> be computed with a source length $\leq L$</li>
<li>$P$ does not compute any other function computable in $L$ bytes or less (by testing)</li>
</ul>

<p>This idea has probably no practical consequences (the bounds are surely bound to be exponential).</p>

CC BY-SA 3.0
2011-07-03T23:48:24.650Z
Suppose your descriptions of functions are given in binary, then there are at most $2^{L+1}-1$ of description length at most $L$. But now the problem is that unlike polynomials, two distinct computable functions can easily take the same values on an infinite number of inputs. Thus your problem seems impossible to me.
Bruno
CC BY-SA 3.0
2011-07-04T00:01:43.910Z
I understand your idea. But two distinct computable functions of description length <= L should differ at some point (for some n0). Could one find the value of n0 given L?
pbaren
CC BY-SA 3.0
2011-07-04T04:45:07.340Z
you can find such a point if there exists one, just compute the functions on all values using dovetailing, but if there isn't then you will never know, it is undecidable, having a length upperbound on program size doesn't change anything.
Kaveh
CC BY-SA 3.0
2011-07-07T00:49:18.020Z
Actually, @Kaveh, by your own argument, an upper bound on $K(f)$ does tell you *something* about where they differ, just not something computable. If $K(f) \leq L$, and $f \neq g$, then $K(x) \leq 2L + c$ where $c$ is the length of the algorithm you (@Kaveh) described and $x$ is the first string on which $f$ and $g$ differ. In particular, $x$ is bounded by some Busy-beaver-like function of $2L+c$. However, finding all $x$ such that $K(x) \leq 2L + c$ or computing BB is still uncomputable. So @pbaren: there is a bound, but it is much more than just exponential, it is uncomputable.
Joshua Grochow
CC BY-SA 3.0
2011-07-07T03:46:07.757Z
@Joshua, nice point, but they are specific points (those with small Kolmogorov complexity), AFAIU, there is not an upperbound on the number of arbitrary points that equality of two functions of length $L$ over them would imply the two are equal (like the case of two polynomials). (ps: By "anything", I meant anything about finding a point that the two functions differ or answering that they don't differ.)
Kaveh
CC BY-SA 3.0
2011-07-07T03:58:27.420Z
btw, there are other parameters about a program that a bound on them may make the problem of program testing efficient. Harvey Friedman has done some work on this in recent years.
Kaveh
CC BY-SA 3.0
2011-07-07T04:55:34.517Z
Thanks to all of you for clarifying. I understand that the bounds are theoretically uncomputable, but I still have the (probably mistaken) intuition that as the Kolmogorov complexity of the test suite approaches that of the program, there should be "few" programs agreeing with the tests.
pbaren
CC BY-SA 3.0
2011-07-07T16:20:02.470Z
@Kaveh: That's what I meant by a "Busy-beaver-like" function: let $BB'(n)$ be the length of the longest string whose Kolmogorov complexity (fix a universal machine) is at most $n$. There are only finitely many such strings so this is well-defined up to the choice of universal machine. Then $BB'(2L+c)$ is an upper bound: if two (total computable) functions of Kolmogorov complexity at most $L$ agree on all points up to length $BB'(2L+c)$, then they are equal.
Joshua Grochow
CC BY-SA 3.0
2011-07-07T16:20:59.003Z
@pbaren I find the analogy with polynomials and degree quite interesting. I think my last comment is one formalization of your intuition, but it requires the Kolmogorov complexity of the test suite to be uncomputably larger (though still finite!) than the Kolmogorov complexity of the original program. I doubt that this gap can be closed.
Joshua Grochow
<cc.complexity-theory><computability>
Can testing show the absence of bugs?
pbaren
# Can testing show the absence of bugs?

(Asked by: username_0 on 2011-07-03)

$(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).

**Tags:** cc.complexity-theory, computability

> **Comments:**
> **username_1**: Suppose your descriptions of functions are given in binary, then there are at most $2^{L+1}-1$ of description length at most $L$. But now the problem is that unlike polynomials, two distinct computable functions can easily take the same values on an infinite number of inputs. Thus your problem seems impossible to me.  
> **username_0**: I understand your idea. But two distinct computable functions of description length <= L should differ at some point (for some n0). Could one find the value of n0 given L?  
> **username_2**: you can find such a point if there exists one, just compute the functions on all values using dovetailing, but if there isn't then you will never know, it is undecidable, having a length upperbound on program size doesn't change anything.  
> **username_3**: Actually, @username_2, by your own argument, an upper bound on $K(f)$ does tell you *something* about where they differ, just not something computable. If $K(f) \leq L$, and $f \neq g$, then $K(x) \leq 2L + c$ where $c$ is the length of the algorithm you (@username_2) described and $x$ is the first string on which $f$ and $g$ differ. In particular, $x$ is bounded by some Busy-beaver-like function of $2L+c$. However, finding all $x$ such that $K(x) \leq 2L + c$ or computing BB is still uncomputable. So @username_0: there is a bound, but it is much more than just exponential, it is uncomputable.  
> **username_2**: @Joshua, nice point, but they are specific points (those with small Kolmogorov complexity), AFAIU, there is not an upperbound on the number of arbitrary points that equality of two functions of length $L$ over them would imply the two are equal (like the case of two polynomials). (ps: By "anything", I meant anything about finding a point that the two functions differ or answering that they don't differ.)  
> **username_2**: btw, there are other parameters about a program that a bound on them may make the problem of program testing efficient. Harvey Friedman has done some work on this in recent years.  
> **username_0**: Thanks to all of you for clarifying. I understand that the bounds are theoretically uncomputable, but I still have the (probably mistaken) intuition that as the Kolmogorov complexity of the test suite approaches that of the program, there should be "few" programs agreeing with the tests.  
> **username_3**: @username_2: That's what I meant by a "Busy-beaver-like" function: let $BB'(n)$ be the length of the longest string whose Kolmogorov complexity (fix a universal machine) is at most $n$. There are only finitely many such strings so this is well-defined up to the choice of universal machine. Then $BB'(2L+c)$ is an upper bound: if two (total computable) functions of Kolmogorov complexity at most $L$ agree on all points up to length $BB'(2L+c)$, then they are equal.  
> **username_3**: @username_0 I find the analogy with polynomials and degree quite interesting. I think my last comment is one formalization of your intuition, but it requires the Kolmogorov complexity of the test suite to be uncomputably larger (though still finite!) than the Kolmogorov complexity of the original program. I doubt that this gap can be closed.  

---

## 4 answers

### Answer by username_4 on 2011-08-09. Score: 9

(This was meant as a comment, but went long).
Very interesting question.
If you are willing to think about other complexity measures besides Kolmogorov's, then there are some answers in Learning theory that might satisfy you. I leave it for the experts in the area.

For example, if I'm not mistaken, in "A theory of the learnable" Valiant proved that a boolean function can be reconstructed given a polynomial number of "positive points" on the size of its k-CNF formula (for any fixed k, and I mean
with "positive points" those of the form $(x\_1,\ldots,x\_n,1)$).

In Knuth's TAOCP 7.2.1.6 it is shown in an astonishing way (using the Christmas tree pattern) that to reconstruct a monote boolean function (i.e. non-decreasing in each variable) you need exactly ${n+1 \choose \lfloor n/2\rfloor+1}$ points.


---

### Answer by username_5 on 2011-08-10. Score: 7

To continue along the lines of Deigo's answer, standard sample complexity bounds from learning theory tell you that if you are satisfied with finding a program which is "approximately correct", you don't need to try very many points at all. Lets say we are encoding programs in binary, so that there are only $2^d$ programs of length d. Lets suppose also that there is some distribution over input examples $D$. Perhaps your goal is to find a program which you are pretty sure is almost right ("Probably Approximately Correct" i.e. as in Valiants PAC learning model). That is, you want to run an algorithm that will take in a small number of samples $x \sim D$ together with $f(x)$, and will with probability at least $(1-\delta)$ output some program $P$ which agrees with $f$ on at least a $(1-\epsilon)$ fraction of inputs drawn from $D$.

We will simply draw $m$ examples $x \sim D$, and output any program $P$ of length $\leq d$ that agrees with $f$ on all of the examples. (One is guaranteed to exist since we assume $f$ has Kolmogorov complexity at most $d$)...

What is the probability that a particular program $P$ that disagrees with $f$ on more than a n $\epsilon$ fraction of examples is consistent with the $m$ examples we selected? It is at most $(1-\epsilon)^m$. We would like to take this probability to be at most $\delta/2^d$ so that we can take a union bound over all $2^d$ programs and say that with probability at least $1-\delta$, no "bad" program is consistent with our drawn examples. Solving, we see that it is sufficient to take only
$$m \geq \frac{1}{\epsilon}\left(d+\log 1/\delta\right)$$
examples. (i.e. only linearly many in the Kolmogorov complexity of $f$...)

BTW, arguments like this can be used to justify "Occam's Razor": given a fixed number of observations, among all of the theories that explain them, you should choose the one with lowest Kolmogorov complexity, because there is the least chance of overfitting.

Of course, if you only want to check a single fixed program in this way, you only need $O(\log(1/\delta)/\epsilon)$ examples...


---

### Answer by username_6 on 2013-06-15. Score: 3

Here's a trivial answer: assuming $L \ge \lg |N|$, then you need to know the value of $f$ at all $|N|$ points to uniquely determine $f$. Therefore, the approach you sketch doesn't help you at all, unless you somehow know that the length $L$ of the program is extremely short: much shorter than $\lg |N|$ bits.

Consider the family of functions $F=\{f\_i:i\in N\}$, where $f\_i$ is defined to be the function $f\_i(x) = 1$ if $i=x$ and $f\_i(x)=0$ if $i\ne x$. Notice that the Kolmogorov complexity of computing $f\_i$ is about $\lg |N|$ bits, since you can hardcode the value of $i$ in the source code and then all you need is a simple conditional statement ($O(1)$ extra).

However, you cannot distinguish $f\_i$ from the all-zeros function unless you test it at the input $i$. You cannot distinguish $f\_i$ from $f\_j$ unless you test at the input $i$ or $j$. Therefore, you'll need to evaluate $f$ at all $|N|$ inputs, to uniquely determine which $f\_i$ we are dealing with. (OK, technically, you need to evaluate it at $|N|-1$ inputs, but whatever.)


---

### Answer by username_7 on 2011-07-06. Score: 0

You can make the program arbitrarily long. So given any program, you can decide whether its language is equivalent to that of this program. You can't do that by Rice's theorem.

> **Comments:**
> **username_8**: You have a valid point that the idea of checking the program by running it on several instances will not work in general.  

---

