The No Free Lunch Theorem is irrelevant to the real world [0][1]. It assumes all functions, even those with infinite algorithmic complexity, are equally likely.

You should look into algorithmic probability for a better foundation.

[0] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.540....

[1] https://arxiv.org/abs/1111.3846.pdf

On the one hand, yes, the No Free Lunch Theorem seems to intuitively rely on the set-theoretic definition of functions, rather than building on a constructive foundation to hypothesize that functions which are "physically harder", in some sense, are less likely.

On the other hand, algorithmic probability requires first defining a Turing machine, rendering the Solomonoff Measure defined only up to a specific programming language, which can bias it some arbitrary amount. That's on top of the Solomonoff Measure itself being incomputable, and so utterly useless as a foundation for real-world machine learning and computational cognitive science.

I agree that positing a Bayesian prior on functions/programs/causal structures gets you around the No Free Lunch Theorem. The question just then ends up being: what sort of hypothesis space, and what sort of prior, sufficiently resemble the real world (the data-generating process) to allow for learning from a given data set? That's a matter of science.

I'm not sure I follow you.

I didn't mean intelligence in any abstract problem-space. I meant intelligence in the world and type of problems we humans deal with (in fact, I'm unsure what process should we call intelligence in non-human context).

In the context I'm talking about, we at least have one algorithm that has build models from the scratch: evolution by natural selection.