[JohnStrange]

Interesting blog entry but I was a bit disappointed not to hear about Solomonoff induction, as it is often taken to determine quite rigidly what is in principle learnable by induction. What's the connection of the approach mentioned in the blog post to Solomonoff induction?

[yters]

Isn't Solomonoff induction optimal if the target is learnable?

The connection to Kolmogorov complexity is interesting. It implies a perfect learner must have infinite KC or increase KC, neither of which an algorithm can do.