Zach Furman

A network that has perfectly memorized a lookup table for modular addition computes the same function on a finite domain as a network that has learned the general trigonometric algorithm.

Yet we would want to say, emphatically, that they have learned different programs.

The program is not just the function.

It is the underlying mechanism.

Thus the notion must depend on parameters, and not just functions, presenting a further conceptual barrier.

To formalize the notion of mechanism, a natural first thought might be to partition the continuous parameter space into discrete regions.

In this picture, all the parameter vectors within a region W subscript A would correspond to the same program A, while vectors in a different region W subscript B would correspond to program B. But this simple picture runs into a subtle and fatal problem.

The very smoothness that makes gradient descent possible works to dissolve any sharp boundaries between programs.

Imagine a continuous path in parameter space from a point, complex formula omitted from the narration, which clearly implements program A to a point, complex formula omitted from the narration, which clearly implements program B. Imagine, say, that A has some extra subroutine that B does not.

Because the map from parameters to the function is smooth, the network's behavior must change continuously along this path.

At what exact point on this path did the mechanism switch from A to B?

Where did the new subroutine get added?

There is no canonical place to draw a line.

A sharp boundary would imply a discontinuity that the smoothness of the map from parameters to function seems to forbid.

This is not so simple a problem, and it is worth spending some time thinking about how you might try to resolve it to appreciate that.

What this suggests, then, is that for the program synthesis hypothesis to be a coherent scientific claim, it requires something that does not yet exist.

A formal, geometric notion of a space of programs.

This is a rather large gap to fill, and in some ways, this entire post is my long-winded way of justifying such an ambitious mathematical goal.

I won't pretend that my collaborators and I don't have our own ideas about how to resolve this, but the mathematical sophistication required jumps substantially, and they would probably require their own full-length post to do justice.

For now, I will just gesture at some clues which I think point in the right direction.