Optimal Programming

Posted on by Chris Warburton

I'm a programmer, and as such I'm always looking for ways to automate and abstract away repetitive and time-consuming tasks. The most repetitive and time-consuming thing I do is program, so why not try to automate it?

There have been many approaches to automating programming over the years. Most, like inductive programming and [page=":cedi:type=misc:id=40"]Genetic Algorithms[/page], try to increase the power of toy systems. A few, like [page=":cedi:type=misc:id=46"]Levin Search[/page], try to increase the efficiency of theoretical systems.

I prefer the top-down theoretical approach, since 'heuristics come and go, but theorems are forever', but these algorithms tend to perform terribly on small problems, despite being optimal for large problems. The trouble is, all of the problems we care about are 'small' according to these algorithms.

As I've written previously, Levin Search is the optimal way to automate programming when the only information we have is whether each guess is right or wrong. Levin Search is only linearly slower than any other method, such as Genetic Algorithms, but the factor is huge.

The reason is that the limited-information scenario where Levin Search shines is actually a worst-case scenario; we usually have much more information available to exploit than just yes/no replies. For example, for a Genetic Algorithm to work well it needs enough bits in its fitness function to make the expected variance of the population high enough to learn from.

Is there a theoretically-best way to handle information? Yes, Solomonoff Induction, although that is incomputable. So on one hand we can make no use of information and sample from a universal prior, ie. we have Levin Search. On the other hand we can make maximum usage of information, which is Solomonoff Induction. What we would really like is a smooth curve between the two, and I think this can be parameterised by the ratio of evaluation cost / computational cost:

It's interesting to wonder what the curve between these would look like. I might play around with some equations to see if I can make a pretty picture :)