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 f

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.