# What independence between ZFC and P vs NP would imply

Sup­pose we had a model M that we thought de­scribed can­nons and can­non balls. M con­sists of a set of math­e­mat­i­cal as­ser­tions about can­nons, and the hy­poth­e­sis is that these fully de­scribe can­nons in the sense that any ques­tion about can­nons (“what tra­jec­tory do can­non balls fol­low for cer­tain firing an­gles?”, “Which an­gle should we pick to hit a cer­tain tar­get?”) can be an­swered by de­riv­ing state­ments from M. Sup­pose fur­ther that M is speci­fied in a cer­tain math­e­mat­i­cal sys­tem called A, con­sist­ing of ax­ioms A1...An.

Now there is much to be said about good ways to find out whether M is true of can­nons or not, but con­sider just this par­tic­u­lar (strange) out­come: Sup­pose we dis­cover that a cru­cial ques­tion about can­nons—e.g. Q=”Do can­non balls always land on the ground, for all firing an­gles?”—turned out to be not just un-an­swer­able by our model M but for­mally in­de­pen­dent of the math­e­mat­i­cal sys­tem A in the sense that the ad­di­tion of some ax­iom A0 im­plies Q, while the ad­di­tion of its nega­tion, ~A0, im­plies ~Q.

What would this say about our model for can­nons? Let’s sup­pose that we can take Q as a prima fa­cie sub­stan­tive ques­tion with a defini­tive yes or no an­swer re­gard­less of any model or ax­iom­a­ti­za­tion. At the very least it seems that M must be an in­com­plete model of can­nons if the sys­tem in which it is speci­fied is in­suffi­cient to an­swer the var­i­ous ques­tions of in­ter­est. It seems to me that

If a ques­tion about re­al­ity turns out to be log­i­cally in­de­pen­dent of a model M, then M is not a com­plete model of re­al­ity.

Now we have an ax­iom­a­ti­za­tion of math­e­mat­ics—let’s say it’s ZFC for now—and we have a model of com­pu­ta­tion in re­al­ity, which is M=”The un­vierse can con­tain ma­chines that (effi­ciently) com­pute F iff there ex­ists a Tur­ing ma­chine that (effi­ciently) com­putes F” with ap­pro­pri­ate defi­ni­tions of what ex­actly a Tur­ing ma­chine is in terms of ZFC. Sup­pose we want to an­swer a ques­tion like Q=”Can the uni­verse con­tain ma­chines that effi­ciently solve SAT?”

Un­der the premise that M is true, the ques­tion Q be­comes the pure log­i­cal ques­tion R=”Are there Tur­ing ma­chines that effi­ciently solve SAT?”, i.e. the P ver­sus NP prob­lem.

Now sup­pose that R was shown to be for­mally in­de­pen­dent of ZFC in the sense that for some ax­iom A0, ZFC+A0 im­plies P=NP and ZFC+~A im­plies P!=NP. This would re­solve the math­e­mat­i­cal ques­tion of P ver­sus NP but the ques­tion Q seems like a prima fa­cie con­crete ques­tion with a defini­tive yes or no an­swer that does not rely for its sub­stance on M or ZFC or any other epistemic con­struct. It would seem that we must have missed some­thing in our de­scrip­tion of re­al­ity, M.

Per­haps more con­tro­ver­sially, I claim: Un­der the cor­rect model M’ it seems that it’s im­pos­si­ble for a sub­stan­tive ques­tion (such as Q) to be unan­swer­able.

All this adds up to: The P ver­sus NP prob­lem (and ques­tions like it that can be phrased as defini­tive ques­tions about re­al­ity) must have an an­swer un­less our model of re­al­ity is in­com­plete.

• Your post doesn’t seem to have any­thing to do with P vs NP, it’s just a state­ment of in­dig­na­tion at Gödel’s in­com­plete­ness the­o­rems :-)

Here’s a sim­plified ex­am­ple. Imag­ine you have an ax­io­matic “model of re­al­ity” that de­scribes com­put­ers. Then I can write a com­puter pro­gram that suc­ces­sively gen­er­ates all valid proofs in that ax­iom sys­tem. If the pro­gram stum­bles upon a valid proof that 1=0, it halts, oth­er­wise it goes on search­ing. It seems to be a “prima fa­cie sub­stan­tive ques­tion” whether the pro­gram will halt or not, but our ax­iom sys­tem can­not set­tle it be­cause it can­not prove its own con­sis­tency by Gödel’s sec­ond in­com­plete­ness the­o­rem, un­less it is in­con­sis­tent.

The root of the prob­lem, IMO, is our in­abil­ity to de­scribe in­te­gers. By the Löwen­heim–Skolem the­o­rem, you can­not have an ax­iom­a­ti­za­tion of the in­te­gers that rules out non­stan­dard in­te­gers. I wrote sev­eral posts about this.

• Good point, ev­i­dently I failed to re­ally in­ter­nal­ize Godel. I had dis­missed Godel sen­tences as not ques­tions about re­al­ity but your ex­am­ple is com­pel­ling.

In­ter­est­ingly, your post on in­te­gers seemed to sug­gest you were also think­ing that since our mod­els of in­te­gers fail to live up to ex­pec­ta­tions we’ve some­how failed to de­scribe them, but that it might yet be pos­si­ble to do so.

• A differ­ent per­spec­tive: Godel doesn’t say that there is any par­tic­u­lar ques­tion about re­al­ity that we can­not an­swer, only that how­ever far into the model-build­ing en­ter­prise we get, there will always be some un­de­cid­able propo­si­tions, which can be trans­lated into ques­tions about re­al­ity with the TM-enu­mer­at­ing-sen­tences ex­per­i­ment. So if we have a model of re­al­ity M and it fails to an­swer a ques­tion about re­al­ity Q then there’s always hope that we could dis­cover fur­ther reg­u­lar­i­ties in re­al­ity to amend M so that it an­swers Q, but there is no hope that we would ever be free of any open ques­tions. Am I cor­rect in think­ing that this rules out the pos­si­bil­ity of a GUT, at least if a GUT is defined as a model that an­swers all ques­tions.

• Godel doesn’t say that there is any par­tic­u­lar ques­tion about re­al­ity that we can­not answer

Of course! It’s a the­o­rem about math. There are no the­o­rems about re­al­ity.

Am I cor­rect in think­ing that this rules out the pos­si­bil­ity of a GUT, at least if a GUT is defined as a model that an­swers all ques­tions.

Yes and no. You can build com­put­ers that enu­mer­ate proofs even in uni­verses with sim­ple and known physics, like the Game of Life. But to math­e­mat­i­cally define some­thing like an in­finite Game of Life grid, you need in­te­gers, and we don’t have a com­plete ax­iom­a­ti­za­tion of those. So you could have a GUT that’s com­pletely defined “rel­a­tive to the in­te­gers”. I guess most physi­cists would ac­cept that as a good enough GUT, even though it’s in­com­plete in the Godelian sense.

• Now sup­pose that R was shown to be for­mally in­de­pen­dent of ZFC in the sense that for some ax­iom A0, ZFC+A0 im­plies P=NP and ZFC+~A im­plies P!=NP. This would re­solve the math­e­mat­i­cal ques­tion of P ver­sus NP

This is only true if A0 is in­de­pen­dent of ZFC. This makes things un­nec­es­sar­ily com­pli­cated and ob­scures how one would usu­ally prove that some­thing is in­de­pen­dent. There are a va­ri­ety of meth­ods of show­ing that some­thing is in­de­pen­dent, but the most com­mon method is to con­struct two mod­els of the the­ory, one with the state­ment and the other with the nega­tion. If both mod­els are con­tained in your origi­nal sys­tem then you know that as long as your origi­nal sys­tem is con­sis­tent, your de­sired state­ment is in­de­pen­dent. A more con­crete ex­am­ple that avoids a lot of the sub­tleties and ab­strac­tions is what hap­pened with the par­allel pos­tu­late in the 19th cen­tury. By mak­ing slightly other ge­ome­tries (such as ge­ome­tries on the sur­face of a sphere), one could do the ex­act same pro­cess as above.

All this adds up to: The P ver­sus NP prob­lem (and ques­tions like it that can be phrased as defini­tive ques­tions about re­al­ity) must have an an­swer un­less our model of re­al­ity is incomplete

I think you may be con­fus­ing re­al­ity with our mod­els here. Con­sider for ex­am­ple the pos­si­bil­ity that our uni­verse is ac­tu­ally dis­crete and finite. If that’s the case, then a de­cent model won’t an­swer whether P != NP or not in the ab­stract sense.

In gen­eral, when a spe­cific ques­tion is be­ing asked it helps to try to put in the less ab­stract ver­sion and see if any­thing changes. In this con­text, what do you think hap­pens if we re­place P ! = NP with some more con­crete ques­tion? Say for ex­am­ple I want to know if 3^^^^^^3 + 1 has an even or odd num­ber of prime fac­tors. This is at least more con­crete in that you can spec­ify a spe­cific com­pu­ta­tion that if you could do it you could then an­swer this ques­tion. I don’t know of any easy way to an­swer this sort of ques­tion but it looks re­ally difficult. It may well be that this ques­tion is sim­ply un­re­solv­able in our uni­verse be­cause the com­pu­ta­tional re­sources to an­swer it don’t ex­ist. But from the per­spec­tive of some­thing like ZFC this ques­tion is triv­ial. This sug­gests to me that there are sub­tle is­sues go­ing on here that you aren’t quite ad­dress­ing. P != NP is a par­tic­u­larly tricky ques­tion be­cause there are so many op­tions for what could hap­pen that are log­i­cally con­sis­tent but seem weird (e.g. there’s an al­gorithm that solves 3-SAT in polyno­mial time but this can’t be proven in ZFC. Or the al­gorithm’s cor­rect­ness can be proven but not a polyno­mial bound on its run time. Or the run time can be proven but not the cor­rect­ness of the al­gorithm. Etc.)

How is­sues like un­de­cid­abil­ity and our mod­el­ing of re­al­ity in­ter­act are re­ally tough. It isn’t helpful to jump in with them us­ing an ex­am­ple that is it­self re­ally ab­stract.

All of that said, there’s an overview by Scott Aaron­son on whether P != NP is un­de­cid­able that is worth read­ing(pdf). He does also dis­cuss to­wards the end some of the is­sues you are touch­ing on.

• I think you may be con­fus­ing re­al­ity with our mod­els here.

Yeah my claim was a lit­tle am­bigu­ous. I meant to claim that ei­ther (1) our cur­rent model of re­al­ity fails to de­scribe some truths about the uni­verse or (2) P=NP is de­cid­able in our model. [I’m only clar­ify­ing the claim, I’m now du­bi­ous about whether this it is true.] You’re right- I should add (3) P=NP can­not be cast as a ques­tion about re­al­ity.

• 8 Dec 2011 23:01 UTC
5 points

The prob­lem (or, ac­cord­ing to some posters, one of the prob­lems) with your idea is that the con­cept of a polyno­mial-time al­gorithm is it­self a math­e­mat­i­cal ques­tion and not a ques­tion about re­al­ity. If I gave you the run­ning times of an al­gorithm for in­put sizes from 1 to 3^^^3, this would not tell you whether the al­gorithm is polyno­mial. How­ever, it would an­swer the ques­tion as far as re­al­ity is con­cerned, since it’s im­pos­si­ble to perform the al­gorithm on in­puts big­ger than that (or even re­motely close to that size).

For sim­ple al­gorithms like bub­ble sort or what­not, we can look at the al­gorithm and say, “oh, that’s quadratic time” and that lets us make pre­dic­tions about how long it will take to run (if it takes 10 sec­onds to sort a 10^9 el­e­ment ar­ray, then it will prob­a­bly take 1000 sec­onds to sort a 10^10 el­e­ment ar­ray). But this is not a state­ment about re­al­ity di­rectly—this is a math­e­mat­i­cal state­ment which de­scribes re­al­ity, in this case.

Fur­ther­more, it is im­pos­si­ble to make this sort of state­ment in gen­eral. Just as we can’t tell if an ar­bi­trary pro­gram halts or not, we can­not in gen­eral say if an ar­bi­trary al­gorithm runs in polyno­mial time. In fact, I’d bet that one can con­struct an al­gorithm such that the ques­tion whether the al­gorithm runs in polyno­mial time is in­de­pen­dent of ZFC. This is not a ques­tion of ZFC failing to de­scribe re­al­ity, be­cause it’s not a ques­tion about re­al­ity whether the al­gorithm is polyno­mial, to be­gin with.

As for P=NP… there’s ac­tu­ally an in­ter­est­ing ex­er­cise that I’d ex­pect any­one in a good the­o­ret­i­cal CS class to see. Right now, with­out do­ing cut­ting-edge re­search, I can write down an al­gorithm for solv­ing 3SAT with the fol­low­ing prop­erty: if P=NP, then the al­gorithm I write down will run in polyno­mial time (and ob­vi­ously the con­verse also holds). Thus, de­cid­ing whether P=NP is iso­mor­phic to de­ter­min­ing the run­ning time of this al­gorithm (which has a very sim­ple de­scrip­tion!) As I’ve stated ear­lier, it would not be too sur­pris­ing if this ques­tion turned out to be in­de­pen­dent of ZFC.

Edit: it ap­pears that my last para­graph has been pre­empted.

Also: up­voted for an in­ter­est­ing ques­tion.

• Per­haps more con­tro­ver­sially, I claim: Un­der the cor­rect model M’ it seems that it’s im­pos­si­ble for a sub­stan­tive ques­tion (such as Q) to be unan­swer­able.

Have you heard of Gödel’s in­com­plete­ness the­o­rems?

Whether a Tur­ing Ma­chine ever halts is a con­crete ques­tion with a definite yes or no an­swer; but, if we could con­struct an ax­io­matic sys­tem with a re­cur­sively enu­mer­able set of the­o­rems such that for each Tur­ing ma­chine a the­o­rem ex­isted stat­ing whether the ma­chine halted or not, then we could build a de­cider for whether any Tur­ing ma­chine halts.

All this adds up to: The P ver­sus NP prob­lem (and ques­tions like it that can be phrased as defini­tive ques­tions about re­al­ity) must have an an­swer un­less our model of re­al­ity is in­com­plete.

Then all pos­si­ble mod­els of re­al­ity are in­com­plete.

• Whether a Tur­ing Ma­chine halts af­ter a cer­tain num­ber of steps has a definite an­swer. But whether it halts even­tu­ally does not nec­es­sar­ily; what em­piri­cal data could prove that it halts even­tu­ally, other than see­ing it halt?

• An ob­ser­va­tion of a loop, a por­tion of the tape en­cod­ing a value that’s de­creas­ing each loop, and a check for it fal­ling be­low a thresh­old that would lead to a halt?

• That would only work for some tur­ing ma­chines. In­ci­den­tally, it’s perfectly pos­si­ble to de­cide for par­tic­u­lar finite tur­ing ma­chines whether it halts—ba­si­cally ei­ther set a time-out equiv­a­lent to the Busy Beaver for that TM (and it ei­ther halts be­fore, or blows the time-out in which case it never halts), or, IIRC, you can store ev­ery con­figu­ra­tion of the tape it passes through and if it re­peats any con­figu­ra­tion, then it will not halt. Nei­ther of these is es­pe­cially use­ful.

• That would only work for some tur­ing ma­chines.

Of course. I made no claim at hav­ing solved the halt­ing prob­lem. My re­sponse was speci­fi­cally to,

what em­piri­cal data could prove that it halts even­tu­ally, other than see­ing it halt?

There is noth­ing else that will re­li­ably show this for all ma­chines. There are ab­solutely things that will show this for some ma­chines.

• Those heuris­tics and any oth­ers you come up with will fail to tractably con­firm whether some ma­chines halt.

• Yes, but they can con­firm that some ma­chines will halt, with­out ob­serv­ing that they have halted, which seemed to be what was asked for. Any such ap­proach must of course say “I don’t know” (or it­self fail to halt) in some cases.

• My apolo­gies, I was im­pre­cise in my origi­nal com­ment. I was try­ing to get at the fact that “whether Tur­ing ma­chine M halts” is not ac­tu­ally a con­crete ques­tion, as had been claimed above (I was as­sum­ing that the rea­son it was pre­sumed to be con­crete is be­cause you can just watch the ma­chine and it ei­ther halts or doesn’t, and my point was that you can’t ac­tu­ally just watch a ma­chine to see if it will halt).

• Whether a Tur­ing Ma­chine ever halts is a con­crete ques­tion with a definite yes or no answer

This doesn’t seem right. In differ­ent mod­els, differ­ent TMs halt, and it’s im­pos­si­ble to spec­ify which model you re­ally mean as set­tling the ques­tion. You can even de­cide, of your own free will, whether cer­tain TMs halt or not (if you’re simu­lated by them, say). So, it should rather be the more triv­ial “In any given struc­ture, whether a TM ex­e­cu­tion defined on it halts, is a prop­erty of that struc­ture.”

• Scott Aaron­son (a well-known com­plex­ity the­o­rist) has writ­ten a sur­vey ar­ti­cle about ex­actly this ques­tion.

• Please don’t con­fuse math with “re­al­ity”. Math as about ax­ioms and proofs (well-formed finite strings), and is of­ten a use­ful tool in map­ping the ter­ri­tory, but it is just that, one of the tools.

If a ques­tion about re­al­ity turns out to be log­i­cally in­de­pen­dent of a model M, then M is not a com­plete model of re­al­ity.

Quan­tum Me­chan­ics is a clas­sic coun­terex­am­ple, as far as we know, in a sense that there is no deeper un­der­ly­ing the­ory that would pre­dict an out­come of a mea­sure­ment when QM says it can­not be de­ter­mined.

• Math as about ax­ioms and proofs (well-formed finite strings), and is of­ten a use­ful tool in map­ping the ter­ri­tory, but it is just that, one of the tools.

Your for­mal­ist ide­ol­ogy is noted, but please don’t state its (dis­putable) claims as clear truths.

• Your for­mal­ist ide­ol­ogy is noted, but please don’t state its (dis­putable) claims as clear truths.

Not sure what you mean by “for­mal­ist”, or ” claims as clear truth”, but feel free to provide a differ­ent defi­ni­tion of math­e­mat­ics ac­cept­able to a math­e­mat­i­cian.

• Math­e­mat­ics seem­ingly stud­ies math­e­mat­i­cal struc­tures, guided by rather elu­sive crite­ria for what is worth study­ing, with ax­ioms and proofs not ob­vi­ously con­sti­tut­ing the whole of its fo­cus. In philos­o­phy of math­e­mat­ics, as­sert­ing that only for­mal state­ments and proofs make sense is known as for­mal­ism:

It has been claimed that “For­mal­ists, such as David Hilbert, hold that math­e­mat­ics is no more or less than math­e­mat­i­cal lan­guage. It is sim­ply a se­ries of games...”

• Quan­tum Me­chan­ics is a clas­sic coun­terex­am­ple, as far as we know, in a sense that there is no deeper un­der­ly­ing the­ory that would pre­dict an out­come of a mea­sure­ment when QM says it can­not be de­ter­mined.

With MWI, this is in­cor­rect—we do pre­dict the out­come: all the branches.

• With MWI, this is in­cor­rect—we do pre­dict the out­come: all the branches.

The MWI gives an illu­sion of pre­dictabil­ity (“Every­thing pos­si­ble hap­pens! We just don’t see it be­cause nearly all of it hap­pens some­where else to some other ‘us’!”). Un­for­tu­nately, it can no more an­swer the ques­tion of which out­come an ex­per­i­ment will mea­sure in “this world” than any other in­ter­pre­ta­tion.

Even more un­for­tu­nately, and at a risk of a mas­sive down­vote, I hate to say it, but the MWI has be­come an offi­cial LW re­li­gion:

• pro­claimed to be true true by the founder: check

• pro­vides com­fort to the masses: check

• sets the group apart from oth­ers: check

• im­pos­si­ble to falsify: check

• makes one feel su­pe­rior be­cause of “deeper un­der­stand­ing of the world”: check

• How does MWI provide com­fort to the masses? Michael Vas­sar is hardly the masses, but it makes him ex­tremely un­com­fortable—he called Quan­tum Im­mor­tal­ity the most hor­rify­ing idea he’d ever had to take se­ri­ously, and I agree.

• I would think that most peo­ple would find the idea of liv­ing for­ever in some of the wor­lds at least some­what com­fort­ing. It is even bet­ter than hav­ing an im­mor­tal soul: you get to live for­ever in the flesh, and you do not need to pay a tithe in any of the wor­lds.

That said, I was refer­ring to some­thing else, namely to the ma­jor dis­com­fort of the es­sen­tial un­pre­dictabil­ity of any quan­tum ex­per­i­ment. In the MWI (or at least in some ver­sions of it) the par­allel wor­lds come into ex­is­tence and sail apart as the de­co­her­ence takes hold and the off-di­ag­o­nal con­tri­bu­tion to the joint sys­tem/​de­tec­tor state de­cays away rapidly.

Every­thing seems pre­dictable and some day maybe even com­putable. The only minor caveat is that you never get to ob­serve these other wor­lds and bless your sur­viv­ing copies with your dy­ing breath (or re­ceive the bless­ing of those gone be­fore you).

• Un­for­tu­nately, it can no more an­swer the ques­tion of which out­come an ex­per­i­ment will mea­sure in “this world” than any other in­ter­pre­ta­tion.

It doesn’t fail to give an an­swer to the ques­tion—it makes the ques­tion in­co­her­ent.

“Which out­come an ex­per­i­ment will mea­sure” is sit­ting be­fore the ex­per­i­ment look­ing for­ward. With MWI, there is no world af­ter the ex­per­i­ment look­ing back­wards with a unique claim on be­ing “this world.” The an­swer to “will there be a me ob­serv­ing re­sult X” will of course be yes. The ques­tion of which of those mes is the “real” one is mis­lead­ing. What quan­tum the­ory does tell us, in MWI, is the to­tal amount of sur­prise in the mes look­ing back.

• ...And we are back to square one, the un­falsifi­a­bil­ity of an in­ter­pre­ta­tion, which makes the adepts feel good about their “knowl­edge” with­out run­ning any risk of it be­ing shat­tered.

• If you sup­pose “in­ter­pre­ta­tion” to be a dis­tinc­tion that can’t be set­tled by ob­ser­va­tion, and si­mul­ta­neously that any dis­tinc­tion must be set­tled by ob­ser­va­tion, then it’s not clear what you’re ob­ject­ing to. Th­ese posts seem rele­vant: Belief in the Im­plied In­visi­ble, You’re En­ti­tled to Ar­gu­ments, But Not (That Par­tic­u­lar) Proof.

• For your in­for­ma­tion: Not vot­ing you down be­cause you dis­agree with the MWI, but be­cause you made a silly ar­gu­ment and then im­me­di­ately re­placed it with an en­tirely differ­ent ar­gu­ment with no ac­knowl­edge­ment that your origi­nal ar­gu­ment had been shown to be silly.

• I wasn’t feel­ing su­pe­rior to you be­cause you chose to refer­ence non-MWI QM—I’m not con­fi­dent about MWI my­self, and would pre­fer we keep other in­ter­pre­ta­tions al­ive un­til we can dis­t­in­guish on the ba­sis of ev­i­dence (or at least have a strong ar­gu­ment that space com­plex­ity de­serves no place at all in our pri­ors).

I am feel­ing su­pe­rior to you now be­cause you ig­nored a preva­lent in­ter­pre­ta­tion with­out giv­ing men­tion to what in­ter­pre­ta­tion you were us­ing, and then when I tried to clar­ify you launched into a rant.

• Is it re­ally nec­es­sary to pub­lish one’s su­pe­rior feel­ings?

• Gen­er­ally? No, not at all. Here, it was speci­fi­cally a re­sponse to state­ments to the effect of “you’re only bring­ing up MWI as an ex­cuse to feel su­pe­rior.”

• Still, I find it prefer­able if peo­ple keep their po­ten­tially offen­sive feel­ings pri­vate, even if these feel­ings arose as a re­ac­tion to be­ing ac­cused of hav­ing such feel­ings.

• I offered the above more as ex­pla­na­tion than defense. I cer­tainly re­spect your point of view here; I have some fur­ther thoughts, but I’d rather sift through them a bit as I’m not sure they’re ac­tu­ally co­her­ent.

• with­out giv­ing men­tion to what in­ter­pre­ta­tion you were using

The math of QM does not re­quire an in­ter­pre­ta­tion, so I re­frain from us­ing any.

• Then re­frain.

Quan­tum Me­chan­ics is a clas­sic coun­terex­am­ple, as far as we know, in a sense that there is no deeper un­der­ly­ing the­ory that would pre­dict an out­come of a mea­sure­ment when QM says it can­not be de­ter­mined.

This is not re­frain­ing from pick­ing a model—this is choos­ing to reify cer­tain classes of in­ter­pre­ta­tion. If you are say­ing, “The math is just what the math is, and says noth­ing more” then it doesn’t pur­port to be com­plete in the first place, and isn’t a coun­terex­am­ple.

• Seems like we are talk­ing past each other (hap­pens quite of­ten when­ever the MWI is men­tioned), so I will dis­en­gage.

• Quan­tum Me­chan­ics is falsifi­able; MWI vs Copen­hagen is math­e­mat­i­cally equiv­a­lent. I’d call it a prefer­ence rather than a re­li­gion.

 Poster be­low states that they’re not math­e­mat­i­cally equiv­a­lent. I think a bet­ter way of say­ing it is “MWI is re­lated to Copen­hagen so that ob­serv­able ev­i­dence for or against one is always and ex­actly ob­serv­able ev­i­dence for or against the other as well. ”

• I’d call it a prefer­ence rather than a re­li­gion.

Un­for­tu­nately, it is not treated as a prefer­ence. Peo­ple use magic words like Oc­cam’s ra­zor, Solomonoff in­duc­tion and Kol­mogorov com­plex­ity to jus­tify why the MWI is bet­ter, with­out any at­tempt to quan­tify it. Well, I did make an at­tempt to quan­tify the com­plex­ity in one of my com­ments. Pre­dictably, at least in the hind­sight, there was lit­tle in­ter­est in dis­cussing the val­idity or the con­se­quences of this ap­proach.

• At least one well-known physi­cist not only be­lieves that the MWI can be falsified… he sug­gests that it has been falsified:

http://​​www.analogsf.com/​​0409/​​altview2.shtml

• I sus­pect that he mis­in­ter­prets, as it were, what an in­ter­pre­ta­tion is, namely, a way of think­ing that elu­ci­dates the un­der­ly­ing math­e­mat­i­cal frame­work. He seems to think that differ­ent in­ter­pre­ta­tions can make differ­ent pre­dic­tions based on the same math:

We are led by the Copen­hagen In­ter­pre­ta­tion to ex­pect that the po­si­tions of the in­terfer­ence min­ima should have no par­tic­u­lar sig­nifi­cance, and that the wires should in­ter­cept 6% of the light they do for uniform illu­mi­na­tion.

...

Thus, it ap­pears that both the Copen­hagen In­ter­pre­ta­tion and the Many-Wor­lds In­ter­pre­ta­tion have been falsified by ex­per­i­ment.

Does this mean that the the­ory of quan­tum me­chan­ics has also been falsified? No in­deed! The quan­tum for­mal­ism has no prob­lem in pre­dict­ing the Afshar re­sult. A sim­ple quan­tum me­chan­i­cal calcu­la­tion us­ing the stan­dard for­mal­ism shows that the wires should in­ter­cept only a very small frac­tion of the light. The prob­lem en­coun­tered by the Copen­hagen and Many-Wor­lds In­ter­pre­ta­tions is that the Afshar Ex­per­i­ment has iden­ti­fied a situ­a­tion in which these pop­u­lar in­ter­pre­ta­tions of quan­tum me­chan­ics are in­con­sis­tent with the quan­tum for­mal­ism it­self.

I would say that, more likely than not, his men­tal model of what an in­ter­pre­ta­tion is is differ­ent from what physi­cists tend to mean. It does not help that he has an ax to grind, as the au­thor of his pet “trans­ac­tional” in­ter­pre­ta­tion.

• Copen­hagen and Many Wor­lds do not em­ploy the same math. Many Wor­lds posits a sin­gle dy­nam­i­cal evolu­tion law, given by Schrod­inger’s equa­tion. Copen­hagen sup­ple­ments this with an in­ter­mit­tent stochas­tic col­lapse pro­cess (Von Neu­mann’s Pro­cess 2). So Copen­hagen vs. MWI is a ques­tion open to em­piri­cal test.

There are cer­tain in­ter­pre­ta­tions that are em­piri­cally in­dis­t­in­guish­able from MWI. Bohmian me­chan­ics is an ex­am­ple, al­though even here the math is differ­ent but this differ­ence is pos­tu­lated to be epistem­i­cally in­ac­cessible.

EDIT: I think call­ing Copen­hagen, MWI, Bohm, GRW, etc. differ­ent in­ter­pre­ta­tions of a sin­gle the­ory is pretty mis­lead­ing, sug­gest­ing that they are differ­ent mod­els of the same ax­io­matic sys­tem. They should re­ally be re­garded as differ­ent the­o­ries, with a large amount of over­lap in their math­e­mat­i­cal struc­ture.

• There is no “in­ter­mit­tent stochas­tic col­lapse pro­cess” any­where in the math of QM. The mea­sure­ment is a black box with the Born rule to de­cide the out­come. Bohm is a differ­ent story, and not a happy one.

• The mea­sure­ment pro­cess in the or­tho­dox in­ter­pre­ta­tion isn’t just a means for de­ter­min­ing out­comes. It also has an effect on the sub­se­quent evolu­tion of the wave func­tion. There is a dis­con­ti­nu­ity in the dy­nam­ics be­fore and af­ter a mea­sure­ment. I don’t see how that wouldn’t count as part of the math of the the­ory.

• True, but there is noth­ing stochas­tic about this. Mea­sure­ment is an ex­ter­nal event con­trol­led by an ob­server. The Born rule and the jump into an eigen­state is the math of it, noth­ing more, noth­ing less. The “Von Neu­mann’s Pro­cess 2” is an un­nec­es­sary in­ter­pre­ta­tional mumbo-jumbo.

• Reread this state­ment, which you quoted: “The prob­lem en­coun­tered by the Copen­hagen and Many-Wor­lds In­ter­pre­ta­tions is that the Afshar Ex­per­i­ment has iden­ti­fied a situ­a­tion in which these pop­u­lar in­ter­pre­ta­tions of quan­tum me­chan­ics are in­con­sis­tent with the quan­tum for­mal­ism it­self.”

The im­pli­ca­tion is that Copen­hagen and Many-Wor­lds are not valid in­ter­pre­ta­tions, since (he claims) they are in­con­sis­tent with the for­mal­ism. (I’m not suffi­ciently well-versed in QM to eval­u­ate this claim, un­for­tu­nately.)

• Surely QM can’t be a clas­sic coun­terex­am­ple of any­thing.

• clas­sic != clas­si­cal. English is weird...

• Valid, but I’ve a high con­fi­dence grand­par­ent was just a joke any­way, and clas­sic ~ clas­si­cal enough for that...

• GP

Please do not in­vent new ab­bre­vi­a­tions with­out for­mally in­tro­duc­ing them first.

(Yes, I can figure out what it means, but I shouldn’t have to. One should be able to use sim­ple recog­ni­tion to un­der­stand an ab­bre­vi­a­tion, with­out hav­ing to make any in­fer­ence.)

• Sup­pose we had a model M that we thought de­scribed can­nons and can­non balls. M con­sists of a set of math­e­mat­i­cal as­ser­tions about cannons

In logic, the tech­ni­cal terms ‘the­ory’ and ‘model’ have rather pre­cise mean­ings. If M is a col­lec­tion of math­e­mat­i­cal as­ser­tions then it’s a the­ory rather than a model.

for­mally in­de­pen­dent of the math­e­mat­i­cal sys­tem A in the sense that the ad­di­tion of some ax­iom A0 im­plies Q, while the ad­di­tion of its nega­tion, ~A0, im­plies ~Q.

Here you need to spec­ify that adding A0 or ~A0 doesn’t make the the­ory in­con­sis­tent, which is equiv­a­lent to just say­ing: “Nei­ther Q nor ~Q can be de­duced from A.”

Note: if by M you had ac­tu­ally meant a model, in the sense of model the­ory, then for ev­ery well-formed sen­tence s, ei­ther M satis­fies s or M satis­fies ~s. But then mod­els are ab­stract math­e­mat­i­cal ob­jects (like ‘the in­te­gers’), and there’s usu­ally no way to know which sen­tences a model satis­fies.

• Is there any­thing that sug­gests that this is the case for P vs. NP?

• If ZFC and P vs NP are in­de­pen­dent, this means that it’s im­pos­si­ble to give a proof that P=NP with ZFC. Since an ex­am­ple of a polyno­mial-time al­gorithm that can solve an NP prob­lem would be such a proof, any such al­gorithm must be im­pos­si­ble to state in ZFC. Any al­gorithm we can ac­tu­ally run can be stated in ZFC. As such, this would mean that P!=NP. You’d just have to prove it in ZFC+1, which is ZFC with the ad­di­tional ax­iom that ZFC (the origi­nal, not ZFC+1) is con­sis­tent.

• I can write down a polyno­mial time al­gorithm which solves SAT (for all but finitely many in­stances at least), pro­vided that in fact P = NP. The difficulty is prov­ing that this par­tic­u­lar al­gorithm works, which could eas­ily be true but in­de­pen­dent of ZFC.

• I’ll write down an al­gorithm that solves SAT in time N^k if any al­gorithm does.

On SAT in­stances of size T, enu­mer­ate all al­gorithms of size up to log(T); for each one, con­sider all SAT in­stances of size up to log(T); run each al­gorithm for time log(T)^k, out­put­ing 0 if they don’t halt, and com­pare its out­put to the re­sult of a brute force search.

Take the short­est al­gorithm which worked in each of these tests, and use it to an­swer your origi­nal SAT query of size T (abort­ing and out­put­ing 0 if it takes more than T^k time).

This en­tire pro­cess takes time poly(T). More­over, sup­pose there is an N^k time al­gorithm which solves SAT cor­rectly and let A be the short­est such al­gorithm. Then there is a finite con­stant T0 such that all shorter al­gorithms than A fail on some SAT in­stance of size at most T0. Then the al­gorithm I de­scribed works cor­rectly for all SAT in­stances of size at least 2^(T0 + |A|).

(Edit: this ar­gu­ment is silly; you can just run all pro­grams of size log(T) and out­put a solu­tion if any of them find one)

Edit: Note in par­tic­u­lar that the al­gorithm which takes k = BB(10^10) and does a brute force search in­stead for T < BB(10^10) is guaran­teed to solve SAT in poly time, pro­vided that any al­gorithm does. Real­is­ti­cally, I think tak­ing k = 10 and do­ing a brute for search for T < 10^10^10 is vir­tu­ally guaran­teed to solve SAT in poly time, if any al­gorithm does (and I can ac­tu­ally write down this lat­ter al­gorithm).

• Per­haps a slightly sim­pler way would be to ‘run all al­gorithms si­mul­ta­neously’ such that each one is slowed down by a con­stant fac­tor. (E.g. at time t = (2x + 1) * 2^n, we do step x of al­gorithm n.) When al­gorithms ter­mi­nate, we check (still within the same “pro­cess” and hence slowed down by a fac­tor of 2^n) whether a solu­tion to the prob­lem has been gen­er­ated. If so, we re­turn it and halt.

ETA: Ah, but the busi­ness of ‘switch­ing pro­cesses’ is go­ing to need more than con­stant time. So I guess it’s not im­me­di­ately clear that this works.

• Very in­ter­est­ing.

• Ex­actly. For a more fa­mil­iar ex­am­ple, the in­de­pen­dence of the con­tinuum hy­poth­e­sis from ZFC means that we’ll never stum­ble across a set of in­ter­me­di­ate car­di­nal­ity while do­ing an anal­y­sis prob­lem (oth­er­wise, we’d have a dis­proof), and so the CH is valid in a prac­ti­cal sense even though for­mally un­de­cid­able.

Gen­er­ally speak­ing, if a state­ment is un­de­cid­able and claims the ex­is­tence of some­thing which could be effec­tively ver­ified if it were found, then for prac­ti­cal pur­poses you can as­sume it’s false.

EDIT: Oops- see paulfchris­ti­ano’s com­ment on why P vs. NP isn’t a case of this prin­ci­ple. I think the gen­eral prin­ci­ple is still OK, I just for­got about the whole “abil­ity to effec­tively ver­ify” bit in this case.

• See paulfchris­ti­ano’s com­ments. The mis­take in DanielLC’s com­ment is that, even though any polyno­mial al­gorithm can be “stated in ZFC”, the proof that it runs in polyno­mial time doesn’t nec­es­sar­ily lie within ZFC, or ZFC+Con(ZFC), or any other sys­tem you can name in ad­vance.

• Ah, thanks.

• It is not clear that our uni­verse has in­finite com­put­ing power. If it is finite, then there is a finite com­plete de­scrip­tion of it. Maybe that finite de­scrip­tion even fits in the uni­verse. But we can’t, in the uni­verse, com­pute all the con­se­quences of the de­scrip­tion. If the uni­verse is in­finite and able to simu­late in­finite Tur­ing ma­chines, such as Con­way’s game of Life, then Gödel’s the­o­rem ap­plies, as oth­ers ex­plain. There are also in­ter­me­di­ate pos­si­bil­ities, such as the uni­verse is in­finite, but we are not able to ex­ploit it for com­pu­ta­tion, but a pos­i­tivist might clas­sify that as finite. I think that the state of the art is that this is the case, due to the cos­molog­i­cal con­stant.