There are no free lunch theorems that show that no computable intelligences can perform well in all environments. As far as they go, these theorems are uninteresting, as we don’t need intelligences that perform well in all environments, just in almost all/most.
They are also, in an important sense, false: the No Free Lunch theorem for statistical learning assumes that any underlying reality is as likely as any other (uniform distribution). Marcus Hutter published a paper years ago showing that when you make a simple Occam’s Razor assumption, using the Solomonoff Measure over reality functions instead of a uniform distribution, you do, in fact, achieve a free lunch.
And of course, the Occam’s Razor assumption is well-justified by the whole line of thought going from entropy in statistical mechanics through to both information-theoretic entropy and Kolmogorov complexity, viz: a simpler macrostate (“reality function” for classification/concept learning) can “be implemented by”, emerge from, many microstates, so Occam’s Razor and the Solomonoff Measure work in reductionist ontologies.
The full Solomonoff measure is uncomputable. So a real-world AI would have a computable approximation of that measure, meaning that there are (rare) worlds that punish it badly.
But you don’t get the Free Lunch from the optimality of Solomonoff’s Measure, but instead from the fact that it lets you avoid giving weight to the adversarial reality functions and distributions normally constructed in the proof of the NFL Theorem.
They are also, in an important sense, false: the No Free Lunch theorem for statistical learning assumes that any underlying reality is as likely as any other (uniform distribution). Marcus Hutter published a paper years ago showing that when you make a simple Occam’s Razor assumption, using the Solomonoff Measure over reality functions instead of a uniform distribution, you do, in fact, achieve a free lunch.
And of course, the Occam’s Razor assumption is well-justified by the whole line of thought going from entropy in statistical mechanics through to both information-theoretic entropy and Kolmogorov complexity, viz: a simpler macrostate (“reality function” for classification/concept learning) can “be implemented by”, emerge from, many microstates, so Occam’s Razor and the Solomonoff Measure work in reductionist ontologies.
The full Solomonoff measure is uncomputable. So a real-world AI would have a computable approximation of that measure, meaning that there are (rare) worlds that punish it badly.
But you don’t get the Free Lunch from the optimality of Solomonoff’s Measure, but instead from the fact that it lets you avoid giving weight to the adversarial reality functions and distributions normally constructed in the proof of the NFL Theorem.