No-Free-Lunch theorems are often irrelevant

There’s a wide va­ri­ety of “No Free Lunch” the­o­rems prov­ing that, in gen­eral, some prob­lem is un­solv­able. Very of­ten, these the­o­rems are not rele­vant be­cause the real uni­verse is a spe­cial case.

In a very gen­eral and metaphor­i­cal sense, most of these the­o­rems say some equiv­a­lent of, “There’s no uni­ver­sal good strat­egy: For ev­ery uni­verse where an ac­tion causes you to gain $5, there’s a differ­ent uni­verse where that same ac­tion causes you to lose $5. You can’t get a free lunch across ev­ery uni­verse; if you gain $5 in one uni­verse you must lose $5 in an­other uni­verse.” To which the re­ply is very of­ten, “Sure, that’s true across max­i­mum-en­tropy uni­verses in gen­eral, but we hap­pen to live in a low-en­tropy uni­verse where things are far more or­dered and pre­dictable than in a uni­verse where all the atoms have been placed at ran­dom.”

Similarly: In the­ory, the pro­tein fold­ing prob­lem (pre­dict­ing the low­est-en­ergy con­figu­ra­tion for a string of amino acids) is NP-hard (sorta). But since quan­tum me­chan­ics is not known to solve NP-hard prob­lems, this just means that in the real world, some pro­teins fold up in a way that doesn’t reach the ideal low­est en­ergy. Biol­ogy is happy with just pick­ing out pro­teins that re­li­ably fold up a par­tic­u­lar way. “NP-hard” prob­lems in real life with non­ran­dom data of­ten have reg­u­lar­i­ties that make them much more eas­ily solv­able than the worst cases; or they have pretty good ap­prox­i­mate solu­tions; or we can work with just the solv­able cases.

A re­lated but dis­tinct idea: It’s im­pos­si­ble to prove in gen­eral whether a Tur­ing ma­chine halts, or has any other non­triv­ial prop­erty since it might be con­di­tioned on a sub­pro­cess halt­ing. But that of­ten doesn’t stop us from pick­ing par­tic­u­lar ma­chines that do halt, or limit­ing our con­sid­er­a­tion to com­pu­ta­tions that run in less than a quadrillion timesteps, etcetera.

This doesn’t mean all No-Free-Lunch the­o­rems are ir­rele­vant in the real-uni­verse spe­cial case. E.g., the Se­cond Law of Ther­mo­dy­nam­ics can also be seen as a No-Free-Lunch the­o­rem, and does ac­tu­ally pro­hibit per­pet­ual mo­tion in our own real uni­verse (on the stan­dard model of physics).

It should fi­nally be ob­served that hu­man in­tel­li­gence does work in the real world, mean­ing that there’s no No-Free-Lunch the­o­rem which pro­hibits an in­tel­li­gence from work­ing at least that well. Any claim that a No-Free-Lunch the­o­rem pro­hibits ma­chine in­tel­li­gence in gen­eral, must definitely Prove Too Much, be­cause the same rea­son­ing could be ap­plied to a hu­man brain con­sid­ered as a phys­i­cal sys­tem.


  • Methodology of unbounded analysis

    What we do and don’t un­der­stand how to do, us­ing un­limited com­put­ing power, is a crit­i­cal dis­tinc­tion and im­por­tant fron­tier.