A note on the description complexity of physical theories

Fol­lowup to: The prior of a hy­poth­e­sis does not de­pend on its complexity

Eliezer wrote:

In physics, you can get ab­solutely clear-cut is­sues. Not in the sense that the is­sues are triv­ial to ex­plain. [...] But when I say “macro­scopic de­co­her­ence is sim­pler than col­lapse” it is ac­tu­ally strict sim­plic­ity; you could write the two hy­pothe­ses out as com­puter pro­grams and count the lines of code.

Every once in a while I come across some be­lief in my mind that clearly origi­nated from some­one smart, like Eliezer, and stayed un­ex­am­ined be­cause af­ter you hear and check 100 cor­rect state­ments from some­one, you’re not about to check the 101st quite as thor­oughly. The above quote is one of those be­liefs. In this post I’ll try to look at it closer and see what it re­ally means.

Imag­ine you have a phys­i­cal the­ory, ex­pressed as a com­puter pro­gram that gen­er­ates pre­dic­tions. A nat­u­ral way to define the Kol­mogorov com­plex­ity of that the­ory is to find the length of the short­est com­puter pro­gram that gen­er­ates your pro­gram, as a string of bits. Un­der this very nat­u­ral defi­ni­tion, the many-wor­lds in­ter­pre­ta­tion of quan­tum me­chan­ics is al­most cer­tainly sim­pler than the Copen­hagen in­ter­pre­ta­tion.

But imag­ine you re­fac­tor your pre­dic­tion-gen­er­at­ing pro­gram and make it shorter; does this mean the phys­i­cal the­ory has be­come sim­pler? Note that af­ter some in­nocu­ous re­fac­tor­ings of a pro­gram ex­press­ing some phys­i­cal the­ory in a rec­og­niz­able form, you may end up with a pro­gram that ex­presses a differ­ent set of phys­i­cal con­cepts. For ex­am­ple, if you take a pro­gram that calcu­lates clas­si­cal me­chan­ics in the La­grangian for­mal­ism, and ap­ply mul­ti­ple be­hav­ior-pre­serv­ing changes, you may end up with a pro­gram whose in­ter­nal struc­tures look dis­tinctly Hamil­to­nian.

Therein lies the rub. Do we re­ally want a defi­ni­tion of “com­plex­ity of phys­i­cal the­o­ries” that tells apart the­o­ries mak­ing the same pre­dic­tions? If our for­mal­ism says Hamil­to­nian me­chan­ics has a higher prior prob­a­bil­ity than La­grangian me­chan­ics, which is demon­stra­bly math­e­mat­i­cally equiv­a­lent to it, some­thing’s gone hor­ribly wrong some­where. And do we even want to define “com­plex­ity” for phys­i­cal the­o­ries that don’t make any pre­dic­tions at all, like “glar­ble flar­gle” or “there’s a cake just out­side the uni­verse”?

At this point, the re­quired fix to our origi­nal defi­ni­tion should be ob­vi­ous: cut out the mid­dle­man! In­stead of find­ing the short­est al­gorithm that writes your al­gorithm for you, find the short­est al­gorithm that out­puts the same pre­dic­tions. This new defi­ni­tion has many de­sir­able prop­er­ties: it’s in­var­i­ant to re­fac­tor­ings, doesn’t dis­crim­i­nate be­tween equiv­a­lent for­mu­la­tions of clas­si­cal me­chan­ics, and re­fuses to spec­ify a prior for some­thing you can never ever test by ob­ser­va­tion. Clearly we’re on the right track here, and the origi­nal defi­ni­tion was just an easy fix­able mis­take.

But this easy fix­able mis­take… was the en­tire rea­son for Eliezer “choos­ing Bayes over Science” and urg­ing us to do same. The many-wor­lds in­ter­pre­ta­tion makes the same testable pre­dic­tions as the Copen­hagen in­ter­pre­ta­tion right now. There­fore by the amended defi­ni­tion of “com­plex­ity”, by the right and proper defi­ni­tion, they are equally com­plex. The truth of the mat­ter is not that they ex­press differ­ent hy­pothe­ses with equal prior prob­a­bil­ity—it’s that they ex­press the same hy­poth­e­sis. I’ll be the first to agree that there are very good rea­sons to pre­fer the MWI for­mu­la­tion, like its ped­a­gog­i­cal sim­plic­ity and beauty, but K-com­plex­ity is not one of them. And there may even be good rea­sons to pledge your alle­giance to Bayes over the sci­en­tific method, but this is not one of them ei­ther.

ETA: now I see that, while the post is kinda tech­ni­cally cor­rect, it’s hor­ribly con­fused on some lev­els. See the com­ments by Daniel_Bur­foot and JGWeiss­man. I’ll write an ex­pla­na­tion in the dis­cus­sion area.

ETA 2: done, look here.