So this property looks more like a distinction between P and NL.

]]>I also theorize re the P vs NP problem that you don’t gain anything by building a secondary data structure — I model this idea as the idea that NP = DSPACE(O(n)). The difference between the 2SAT and the 3SAT problems is that 2SAT has natural rewrite rules for its solution, e.g. P\/Q, ~Q\/R, conclude P\/R, whereas 3SAT does not (as far as anyone knows).

]]>(A) The main thing is that it shows a certain problem is Turing-uncomputable. But one particular consequence, is that you can take the Gödel sentence of your favorite formal system and translate it into a statement that says that a certain Hamiltonian is gapless.

(B) No, there are other variations on the Gödel sentence like the Rosser sentence, sentences like Goodstein’s Theorem that are known to be independent of PA (but not of ZF), and sentences like the Axiom of Choice and the Continuum Hypothesis that are known to be independent of ZF (but which are not arithmetical). It remains an open problem to find a “natural” arithmetical sentence, fundamentally different from anything Gödelian, which is provably independent of ZF. In the other direction, if something wasn’t independent of an appropriate formal system, I guess we wouldn’t call it a “Gödel sentence” at all!

(C) Depends what you mean by “useful.” But sure, sometimes the way you show uncomputability is closely related to how you show NP-hardness of a truncated version of a problem, or how you get a universal computer into the system you’re talking about.

]]>I’m very far from being an expert on this subject, so I don’t have a lot of confidence in what I’m about to say, but it seems like situation is more complicated. From the derivation of the Casimir effect I have in front of me, what happens is that you impose a cutoff in your divergent sum, then at the end you take the cutoff to infinity and the famous -1/12 shows up. So far so good. But the infinite cutoff corresponds to the physical situation of perfectly conducting plates. In reality, metals are only good conductors up to a certain frequency, which corresponds to the cutoff you should use in your calculation. And yet the calculation using a cutoff approaching infinity matches (roughly) the experimental results using non-perfect conductors. So it seems like nature is telling us that the -1/12 is showing up in some way even in a truncated sum.

]]>(A) Is it correct to think of Cubitt’s undecidability result as having constructed a particular Godel sentence?

(B) Is every undecidable sentence in a consistent formal theory a Godel sentence? Vice versa too?

(C ) From past experience, have discoveries of particular uncomputability results turned out “useful” to derive other consequences outside of just discovering other uncomputable assertions?

]]>Or is that generalization wrong? Are there practical modelling situations where the literal-infinity to use?

Or alternatively: is there any guidance on when nature prefers the divergent sum to be set to -1/12 instead of the measured metric just blowing up as it would with other divergent sums?

]]>But yes, the trickery that “licenses/encourages” people to replace 1+2+3+… by -1/12, wouldn’t apply to any finite part of that sum.

]]>