18
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Bruno Jul 3 '11 at 23:48
  • $\begingroup$ 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? $\endgroup$ – pbaren Jul 4 '11 at 0:01
  • 4
    $\begingroup$ 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. $\endgroup$ – Kaveh Jul 4 '11 at 4:45
  • 7
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Jul 7 '11 at 0:49
  • 6
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow Jul 7 '11 at 16:20
9
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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...

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You have a valid point that the idea of checking the program by running it on several instances will not work in general. $\endgroup$ – Tsuyoshi Ito Jul 9 '11 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.