Spectral Gap or Gapless Undecidable

[jerromyjon]

I'm kind of confused here, but I am starting to think this is irrelevant to me anyway. In my mind, if the universe and all its possible atomic variables could be defined completely by a set of axioms (a theory of everything in the universe which follows a simple set of rules that apply everywhere) then everything possible would be covered, albeit superdeterministic. Like the Turing machine it's only relevant for example if there are unknowns to possibly contend with, like groups of atoms possessing physics undefinable in the individual basis. I am expecting a TOE would explain everything from blackbody radiation to the Ultraviolet catastrophe to GRBs, so then this undecidable result would become inherently deterministic?

 

[mfb]

A mathematician can be convinced of something that a computer cannot prove: sure. We are all convinced of many things without a formal proof, some of those things are wrong. That is religion, not mathematics.

All other sciences make claims that cannot be strictly proved, and that doesn't make them religion. Mathematicians used to believe (and some still do) that mathematics is different, but after Godel it is becoming more and more accepted that such a belief is not completely justified. Mathematics too must occasionally make some claims which cannot be strictly proved.

All other sciences don't claim that things are certainly right, not even under some given axioms. They make observations and models and statements like "observation A is consistent with model Y but inconsistent with model Z". That is neither mathematics nor religion.

Mathematicians can say "all things we tried so far do not violate the axiom of choice" - and a computer algorithm can make the same statement.

 

[Jimster41]

All other sciences don't claim that things are certainly right, not even under some given axioms. They make observations and models and statements like "observation A is consistent with model Y but inconsistent with model Z". That is neither mathematics nor religion.

Mathematicians can say "all things we tried so far do not violate the axiom of choice" - and a computer algorithm can make the same statement.

Is it consistent with the Undecidability of the Halting Problem to say it takes a mathematician to tell that computer whether or not it is then done - since it can't tell the un-violated axiom of choice from the point of truth?


Or is your point that neither the mathematician nor the computer can know when to halt?

Seriously, I don't quite get the Halting Problem...

I would love it if someone just explained a bit more the way the proof in the paper works. It's like they say - start with something undecidable, add it to something (decideable?) and you will always get... something undecidable. Clearly I'm missing it.

 

[Hornbein]

So there is a new paper.
Presented here: http://arxiv.org/pdf/1502.04135.pdf
Published here: http://www.nature.com/nature/journal/v528/n7581/full/nature16059.html
And broadly described here: http://phys.org/news/2015-12-quantum-physics-problem-unsolvable-godel.html

Here is an excerpt from the abstract:

This suggests that there may be cases where you can experimentally determine whether there is a gap, but that, in theory, there is no way to determine this through analysis.

Is this true, and are there actual examples? For example, is there a specific superconductor that:
- relies on no spectral gap
- where there is enough known about its structure where a computation can be attempted
- but the computation is demonstrably undecidable.

??

Whether or not a gap appears depends on the size of the lattice. It is not possible to test lattices of all sizes, so the general answer will never be known.

But if you are building a particular system, all you care about is that a particular range of system sizes. So gaplessness can be decided by experiment for all practical purposes. If you can build a simulation as large as the actual system will be, then you can rely on that too.

 

[.Scott]

But if you are building a particular system, all you care about is that a particular range of system sizes. So gaplessness can be decided by experiment for all practical purposes. If you can build a simulation as large as the actual system will be, then you can rely on that too.

My interest goes beyond the practicalities of finding superconductors and such. It seems impossible that something in nature could reveal the answer to something that is "undecidable" because "undecidable" is generally taken to be the final word on these math problems. If there is such a case that can be casted as undecidable and then determined through physical experiment, it would be a very interesting mathematical as well as physical revelation.

 

[mfb]

My interest goes beyond the practicalities of finding superconductors and such. It seems impossible that something in nature could reveal the answer to something that is "undecidable" because "undecidable" is generally taken to be the final word on these math problems. If there is such a case that can be casted as undecidable and then determined through physical experiment, it would be a very interesting mathematical as well as physical revelation.

For any given specific and finite problem a solution can be found.

 

[Hornbein]

My interest goes beyond the practicalities of finding superconductors and such. It seems impossible that something in nature could reveal the answer to something that is "undecidable" because "undecidable" is generally taken to be the final word on these math problems. If there is such a case that can be casted as undecidable and then determined through physical experiment, it would be a very interesting mathematical as well as physical revelation.

Quite so. The article also mentioned that some regions were chaotic, but that's nothing new.

Did you know that Diophantine equations are undecidable?

 

[atyy]

Via the Feynman path integral, isn't there a correspondence between quantum mechanics and classical statistical mechanics? So there is a counterpart of this undecidability in the thermodynamic limit of classical statistical mechanics also?

 

[Demystifier]

but did you realize that means PA + Not(Con(PA)), Peano arithmetic plus an assertion that Peano arithmetic is inconsistent, is also a consistent theory with a model?

That's fascinating. First I couldn't believe it, then, after a careful reading of the paper (which is really great) I concluded that it is true but very very strange, and finally, after more thought, I concluded that it is in fact very simple, almost trivial.

To explain why is it almost trivial let me give a really trivial example with very similar properties:

Instead of PA, consider a much simpler axiomatic system called T (for Trivial), with only one axiom:
The axiom: 1+1=2

This is really a very weak axiomatic system. From this axiom you cannot determine that 1+1+1=3, you cannot determine that 2-1=1, you cannot determine anything, except that 1+1=2. This system looks like a parrot which repeats only one sentence without understanding its meaning.

Is this system consistent? Of course it is, you cannot obtain any inconsistency from it. But can its consistency be proved within the system? Of course it can't. The system is so weak that it can't prove anything (except that 1+1=2).

Good! Now consider the extended axiom system T + Not(Con(T)), i.e. the trivial system plus an assertion that the trivial system is inconsistent. Is it consistent? Of course it is; by using only those two axioms, you cannot derive any inconsistency. But can its consistency be proved within the system? Of course not; the system is still too weak for such a proof.

 

[atyy]

That's fascinating. First I couldn't believe it, then, after a careful reading of the paper (which is really great) I concluded that it is true but very very strange, and finally, after more thought, I concluded that it is in fact very simple, almost trivial.

To explain why is it almost trivial let me give a really trivial example with very similar properties:

Instead of PA, consider a much simpler axiomatic system called T (for Trivial), with only one axiom:
The axiom: 1+1=2

This is really a very weak axiomatic system. From this axiom you cannot determine that 1+1+1=3, you cannot determine that 2-1=1, you cannot determine anything, except that 1+1=2. This system looks like a parrot which repeats only one sentence without understanding its meaning.

Is this system consistent? Of course it is, you cannot obtain any inconsistency from it. But can its consistency be proved within the system? Of course it can't. The system is so weak that it can't prove anything (except that 1+1=2).

Good! Now consider the extended axiom system T + Not(Con(T)), i.e. the trivial system plus an assertion that the trivial system is inconsistent. Is it consistent? Of course it is; by using only those two axioms, you cannot derive any inconsistency. But can its consistency be proved within the system? Of course not; the system is still too weak for such a proof.

Perhaps an easier way to think about it is that the Goedel sentences are formal syntactic constructions, so they do not necessarily mean "consistent" or "not consistent" in general. If we believe PA is consistent, and the definition of Goedelian incompleteness means that the Goedel sentence and its negation can be added to PA to yield another consistent system, then it means that if the Goedel sentence ("Con(T)") is added to PA, the extended system has an interpretation as the "standard model of arithmetic". But if the negation ("Not(Con(T))") is added to PA, then the extended system has an interpretation as a "nonstandard model of arithmetic". http://web.mat.bham.ac.uk/R.W.Kaye/papers/arithhis.pdf

 

[Demystifier]

Perhaps an easier way to think about it is that the Goedel sentences are formal syntactic constructions, so they do not necessarily mean "consistent" or "not consistent" in general.

I see what you mean, but sentences claiming that something is consistent or not consistent are not called Godel sentences. A typical Godel sentence claims that this very sentence is not provable.

the Goedel sentence and its negation can be added to PA to yield another consistent system,

I guess you meant "the Goedel sentence or its negation".

sentence ("Con(T)") is added to PA

I guess you meant "Con(PA)", not "Con(T)".

 

[atyy]

I see what you mean, but sentences claiming that something is consistent or not consistent are not called Godel sentences. A typical Godel sentence claims that this very sentence is not provable.

Yes, but since I'm trying to give the heuristic here, it's ok. Formally they are closely related, see section 3.1 of http://plato.stanford.edu/entries/goedel-incompleteness/.

 

[.Scott]

I am taking the time to reread the article more closely.

I wasn't trying to check it, just read through it enough to broadly track the reasoning. This excerpt states the ultimate predicament that the computer can face in its attempt at computing gap/gapless - hopefully in a finite number of steps. Basically, they are considering what can happen as the computation progresses iteratively in pursuit of the solution:

... We have shown that the difference in energy between the halting and non-halting cases now depends inverse-polynomially on the amount of [Turing computer] tape used, which depends on the input ϕ. Not only does this fail to provide a constant bound on the energy difference, independent of the Hamiltonian parameter ϕ, this energy difference is uncomputable!

I believe the point here is that the more you work at the solution, the more the solution can change.

Here is the take from the authors:

But what does it mean for a physical property to be undecidable? After all, if it is physical, surely we could in principle construct the system in the laboratory, and measure it. A real quantum many-body system might exhibit gapped physics or gapless critical physics, but it must exhibit some kind of physics!
The key to reconciling this with our results is to realize that the thermodynamic limit is an idealisation. A real physical system necessarily has a finite size (albeit very large in the case of a typical many-body system consisting of O(10²⁶) atoms). Nonetheless, signatures of undecidability appear in the very unusual finite-size behaviour of these models.

... and the effect on experimental results:

As the system size increases, the Hamiltonian will initially look exactly like a gapless system, with the low-energy spectrum appearing to converge to a continuum. But at some threshold lattice size, a constant spectral gap will suddenly appear. (Our construction can also be used to produce the opposite behaviour, with the system having a constant spectral gap up to some threshold lattice size, beyond which it abruptly switches to gapless physics. Not only can the lattice size at which the system switches from gapless to gapped be arbitrarily large, the threshold at which this transition occurs is uncomputable.
This implies that we can never know whether the system is truly gapless, or whether increasing the lattice size—even by just one more lattice site—would reveal it to be gapped.

And then the authors provide this feel for the characteristics of these undecidable system:

Signatures of undecidability also appear in the very unusual physics exhibited by these models. Systems with infinitely many phases are known in connection with the quantum Hall effect, where fractal phase diagrams such as the Hoftstadter butterfly can be obtained. The phase diagrams of the models appearing in our result are more complex still. Critical and non-critical phases are so intertwined that arbitrarily close to any non-critical point is a critical point, and vice versa. Indeed, the phase diagrams are so complex they are not just fractal, they are uncomputable. The physics of these models therefore exhibits extreme sensitivity to perturbations. A change in the external parameters of the system, however small, can drive it through infinitely many phase transitions.

The physicists among you can correct me if I am wrong, but my take on the above is this: A system that is as sensitive as that described above, will reliably transition through those gap and gapless states in response to a stimulus magnitude that approaches Planck's constants - and so such systems will be in a superposition of gap and gapless states. So all that is needed is to resolve what properties a material exhibits when it is in such a superposition.

 

[atyy]

Perhaps an easier way to think about it is that the Goedel sentences are formal syntactic constructions, so they do not necessarily mean "consistent" or "not consistent" in general. If we believe PA is consistent, and the definition of Goedelian incompleteness means that the Goedel sentence and its negation can be added to PA to yield another consistent system, then it means that if the Goedel sentence ("Con(T)") is added to PA, the extended system has an interpretation as the "standard model of arithmetic". But if the negation ("Not(Con(T))") is added to PA, then the extended system has an interpretation as a "nonstandard model of arithmetic". http://web.mat.bham.ac.uk/R.W.Kaye/papers/arithhis.pdf

I see what you mean, but sentences claiming that something is consistent or not consistent are not called Godel sentences. A typical Godel sentence claims that this very sentence is not provable.

Yes, but since I'm trying to give the heuristic here, it's ok. Formally they are closely related, see section 3.1 of http://plato.stanford.edu/entries/goedel-incompleteness/.

Actually, there is a serious problem with my original comment, but not with the relationship between the Goedel sentence and Con(T). Con(T) implies that the Goedel sentence can be proved. However, contrary to what I implied, Not(Con(T)) does not imply that the the negation of the Goedel sentence cannot be proved - instead the condition of ω-consistency is required. However, it is correct that neither Con(T) nor Not(Con(T)) can be proved from T (where T is PA), so we believe either can be consistently added to PA, except that in one case we get a standard model of arithemetic, and in another case we get a non-standard model of arithmetic. See the comments on ω-consistency in http://www.columbia.edu/~hg17/godel-incomp4.pdf.

 

[ddd123]

So I've kept thinking about this and I've narrowed down on where I actually lose comprehension on this matter. It's been mentioned around the net but I can't find a real answer.

The article says that the threshold of adding lattice sites at which the gap may appear or disappear is uncomputable. Yet, at fixed lattice size, the model is computable. This doesn't make sense to me, so I must be missing something. Because, even if it's obviously beyond NP, you compute the threshold simply by trying all the lattice sizes until you find it. Or does it mean that you don't know if there IS a threshold at all? In that case though, why state it in such an awkward way as "the threshold is uncomputable" instead of just saying "you don't know whether there is a threshold"? The two things seem different anyway. Or do they mean uncomputable in a context that lies outside of trying all sizes?

 

[mfb]

Or does it mean that you don't know if there IS a threshold at all?

Right.

n that case though, why state it in such an awkward way as "the threshold is uncomputable" instead of just saying "you don't know whether there is a threshold"?

It is a stronger statement: we don't know, and we cannot know in general.

 

[jerromyjon]

It is a stronger statement: we don't know, and we cannot know in general.

I'm still struggling to find a tangible example to relate what it is we can't know.
I think the simple question I have to ask is, does this simply apply to the model as incapable of predicting or is it physics that can't be predicted?

 

[mfb]

No model can predict it for every system.

Do you know the halting problem? It is a related problem, but maybe easier to understand.

 

[jerromyjon]

Do you know the halting problem?

I spent my adolescence fighting it. In what you would consider these days at a crawl.

Thanks I just ran everything I ever did on every computer in a microscopic miniscule sector in microseconds in my head...

 

[ddd123]

No model can predict it for every system.

So you can still find "creative" answers for specific systems?

 

[jerromyjon]

So you can still find "creative" answers for specific systems?

I think that's the point. You can't have a system solve anything. This says you can figure it out but no system can do it itself, I guess.
Quantum physics defies the construction of a "turing complete" computer.

 

[jerromyjon]

is it physics that can't be predicted?

I guess I answered my own question but does my understanding seem to follow the problem?

Quantum physics defies the construction of a "turing complete" computer.

That is the age 16 answer that I think I still agree with.

 

[ddd123]

That's what Penrose says (if you mean: Church-Turing is wrong; Turing-completeness refers to machines that can simulate a Turing machine, not the other way around, so I don't think that's what you meant) but I don't think this particular result points in that direction if mfb gave us the correct interpretation. Here it's just saying: there is an undecidability example in infinite-sized Hamiltonians. But Wang tiles are classical, infinite-sized and undecidable too. Quantum physics can still be simulated classically, only less efficiently in some cases.

As for unpredictable physics, again if mfb gave us the correct answer, the unpredictability lies in unbounded cases, but even classically. Suppose we write up a system in which there's only a box in empty space that tries every possible zero for the Riemann Zeta, and turns on a rocket if it finds one. Is the phase space bounded or not? But classical physics is supposed to be deterministic so you should be able to know. Then again, the box must have finite memory to store the numbers.

 

[jerromyjon]

Logic in computer science
"The Curry-Howard correspondence is a relation between logical systems and software. This theory established a precise correspondence between proofs and programs. In particular it showed that terms in the simply-typed lambda-calculus correspond to proofs of [intuitionistic propositional logic]."

I think that makes the problem of looking for a "specific" needle in a haystack with many similar needles.

 

[ddd123]

They were talking about that earlier in the thread. The problem for me now is: what does the "in general" in "in general the threshold is not computable" mean? That in all cases we can't compute it, or that we can't compute it for all cases (i.e. we can find out creative solutions for specific cases but not a general solution)? By the earlier discussion, it seemed like the former was true; but by reading, for example, Scott Aaronson's explanation, the latter seems to be the correct one (and the one which is more pertinent to the halting problem).

I mean: what if we actually find the threshold for one of those specially constructed cases in the paper, by a mathematical intuition or by brute force? Then we have computed it, contradicting the paper's theorem. There must be something I'm missing still.

 

[mfb]

or that we can't compute it for all cases (i.e. we can find out creative solutions for specific cases but not a general solution)?

This.

I mean: what if we actually find the threshold for one of those specially constructed cases in the paper, by a mathematical intuition or by brute force?

The specially constructed cases correspond to an infinite set of problems, and they prove that no algorithm can solve all of them.

 

[Demystifier]

It seems that Seth Loyd had a very similar result a long time ago:
http://lanl.arxiv.org/abs/1602.05924

 

[Strilanc]

That was commented on in an update to the Scott Aaronson post I linked:

Update (Dec. 20): My colleague Seth Lloyd calls my attention to a PRL paper of his from 1993, which also discusses the construction of physical systems that are gapped if a given Turing machine halts and gapless if it runs forever. So this basic idea has been around for a while. As I explained in the post, the main contribution of the Cubitt et al. paper is just to get undecidability into “the sort of system physicists could plausibly care about” (or for which they could’ve plausibly hoped for an analytic solution): in this case, 2D translationally-invariant nearest-neighbor Hamiltonians with bounded local dimension.

Although I have to say I'm enjoying the 2016 paper you linked. I find Seth Lloyd entertaining to watch and read:

References [2-3] belong to the medieval era of quantum information theory, pre-Shor and pre-arXiv: the contemporary reader may compare them to illuminated manuscripts. I now redescribe their results in contemporary language.