Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Spectral Gap or Gapless Undecidable

  1. Dec 10, 2015 #1
    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.

    Last edited by a moderator: May 7, 2017
  2. jcsd
  3. Dec 10, 2015 #2


    User Avatar
    Science Advisor

    No it doesn't. The undecidability applies to solving the problem on an unbounded grid. You won't be able to perform such an experiment for obvious practical reasons.

    Furthermore, note that quantum mechanics is not required for creating undecidable problems. Classical mechanics also allows for objects with undecidable properties (given unbounded space). We call them computers.
    Last edited: Dec 10, 2015
  4. Dec 10, 2015 #3
    The potential difference between the ones related to computers and the ones that might be related to physical events is that on the computers, they are left unsolved. But if they affected physical events, the universe wouldn't just stop when it gets to one of these problems.

    Actually, the last statement in that phys.org article (http://phys.org/news/2015-12-quantum-physics-problem-unsolvable-godel.html) suggests that no such case has been found:
    You don't sound optimistic about their success in that venture.
    Last edited: Dec 10, 2015
  5. Dec 10, 2015 #4


    User Avatar
    Science Advisor

    In their problem, they're trying to figure out if adding more lattice sites will cause the problem instance to become gapped. Alternatively, it might stay gapless forever. They proved that this question is undecidable.

    For a problem that does eventually have a gap, you will eventually figure out that it in fact has a gap by working your way through larger and larger lattices. But for a problem that stays gapless, you're forever left in limbo. No matter how large of a lattice you check, you don't become sure that an even larger lattice won't work. And because the problem is undecidable, you won't always be able to find a proof that there is no sufficiently large lattice.

    Ok, now the exact same wording but for the halting problem!

    In the halting problem, you're trying to figure out if running a program for more steps will cause it to halt. Alternatively, the program may never halt. Turing proved that this question is undecidable.

    For any program that does halt, you will eventually figure out that it in fact halts by running more and more steps. Even for programs that run for a very VERY long time. But for a program that doesn't halt, you're forever left in limbo. No matter how long you simulate it, you don't become sure that just a few more steps won't make the program halt. And because the problem is undecidable, you won't always be able to find a proof that the program doesn't halt.

    See the similarity now?

    It's not that we wouldn't be able to recognize that there's a gap in a given system, it's that we're never sure if we have to keep trying more and more systems or not. Doing experiments doesn't fix this problem, it just makes it physical instead of symbolic. You still find yourself trying larger and larger instances unsure of when to stop.

    I don't see any problem with using the understanding that programs can be sorta encoded into lattices to find new and interesting substances. The researchers won't be able to solve the halting problem with what they make, but that doesn't mean what they make can't be useful or revolutionary.
  6. Dec 10, 2015 #5
    I saw the similarity from the start. I have been familiar with the computer halting problem for years or decades.

    But what you're adding is that their halting problem only relates to one analytical method of determining whether there is a gap - specifically the method based on a grid. So, from what I now understand, they didn't show that the fundamental gap problem is beyond analysis - only that it is beyond a particular analytic approach.

    Is that right?
  7. Dec 10, 2015 #6


    User Avatar
    Science Advisor

    I'm pretty sure the undecidability applies to any method of analysis and any experimental method. Otherwise we'd have a clear practical counter example to the Church-Turing thesis and it would be GIGANTIC news. Did you have some method in mind?
  8. Dec 10, 2015 #7
    No. I was just trying to interpret what you said.
    So they are not examining a realistic situation?
  9. Dec 11, 2015 #8


    User Avatar
    Science Advisor

    Most physicists are not very much familiar with the concepts such as undecidability, halting problem, and Godel theorems. So let me try to explain the meaning of this result in (my own) simple terms.

    Consider the following SF scenario. In the far far future, Wolfram releases a highly advanced version of Mathematica (say, Mathematica 100.0.0) with the following function:
    When you input parameters for an arbitrary infinite-size Hamiltonian, for any such input (however pathological it might be), Mathematica, after some finite time of processing, gives you the output YES or NO, telling you whether the Hamiltonian has or has not the spectral gap.

    No doubt, it would be very difficult to make such a program in Mathematica. But would it be possible at least in principle? The theorem proved in the paper in Nature shows that such a program is impossible even in principle.

    However, it is not really such a negative result as it might look.

    The theorem does not exclude a possibility to make a program which will work for most cases, and only fail for some pathological cases, for which the program will fall into an infinite loop. All what theorem proves is that such pathological cases exist. It is quite possible that neither of the physically interesting cases is pathological in that sense.

    Moreover, even for such pathological cases, it does not mean that a good mathematician cannot determine whether it has a gap or not. Given a particular pathological case, a creative mathematician can create a special method, working only for this special case, to determine whether it has gap or not.

    Furthermore, it is possible to have two (or more) different algoritms, called A1 and A2, which fail for different cases. So if A1 fails in some case of interest, it may be that A2 works for that case. A2, however, will fail in some other case, for which A1 may work well.

    To summarize, all what the theorem says is that there is no one algorithm by which machine can determine (whether there is a gap or not) for any possible input (Hamiltonian).

    I hope it helps to clarify the mathematical and physical (in)significance of the result.
    Last edited: Dec 11, 2015
  10. Dec 11, 2015 #9
    Thanks Demystifier. You have lived up to your name!!
  11. Dec 11, 2015 #10


    User Avatar
    Science Advisor

    The rest of your answer is good, but this part is a bit misleading. There are two important clarifications to make:

    1. The combination of two algorithms is also an algorithm, and so must fail to solve some cases. You can't put together a team of algorithms that cover all the holes; there's always more holes.

    2. A creative mathematician is also subject to the obstacles of undecidability (... depending on your philosophy). For example, they have to ground their proof of gapped-vs-gapless in an axiomatic system such as ZFC, but "iterate over all proofs and stop when you've shown X or not-X in ZFC" is an algorithm that would find such a proof. Because the problem is undecidable, that algorithm must fail for some cases; there may simply be no proof either way. So the creative mathematician would also fail, unless they're willing and able to introduce more and more new axioms. (Secondarily, given the presumption that physics is computable [i.e. the Church-Turing thesis] and that mathematicians are embedded in physics, mathematicians must fail on some instances of uncomputable problems.)
  12. Dec 11, 2015 #11
    I have little real knowledge of Gödel theory, but if I recall it correctly if was not as harsh as commonly stated. The "proofs" the theorem talks about does not encompass all the ways to prove a given statement in an axiomatic system.
  13. Dec 11, 2015 #12
    I don't understand this part. To me, generating proofs is not enough. They also have to be checked if they work or not. Maybe algorithms can't do it in general (assuming Church-Turing is false).
  14. Dec 11, 2015 #13


    User Avatar
    Science Advisor

    Sorry if that was unclear. I intended for checking that the proof was correct to be implied in "stop when you've shown it". Proofs are defined (or can be defined) in a way that's easy for machines to check, so that's not a problem.

    Generally speaking, the hard creative part of math is considered to be the finding of proofs as opposed to the checking of proofs. And when we're only worried about computability, instead of time complexity, simply iterating through all proofs is viable.
  15. Dec 11, 2015 #14


    User Avatar
    Science Advisor

    No, it includes all possible proofs. To avoid undecidability you either need to stick to very trivial systems that don't allow a Turing machine to be encoded, or you need to keep introducing new ad hoc axioms magically whenever you encounter the next undecidable proposition.
    Last edited: Dec 11, 2015
  16. Dec 12, 2015 #15


    User Avatar
    Science Advisor

    Scott Aaronson, a well-known computational complexity theorist and blogger, has written a post about the paper:

  17. Dec 13, 2015 #16
    It's worth noting that even though the halting problem is provably undecidable, it is still possible in principle to construct pseudo halting oracles which examine computer programs which do not exceed some fixed size. Essentially they examine programs with an upper memory limit, of which there are only a finite amount, and in principle can examine all such programs, keep track of their states as they go and flag any which return to a previous state without looping as non-halting. This leads to the concept of busy-beaver functions and non-computability, which are a great way to spend an afternoon.
  18. Dec 13, 2015 #17

    I mean, yes it denies all possible possible proof working within the theory but that was not the only ways to see if a proposition was true or false, or at least that is what I remember about the issue.
  19. Dec 13, 2015 #18


    User Avatar
    2016 Award

    Staff: Mentor

    But can you be sure that you stop after an afternoon?

    We don't have to assume mathematicians are physical objects and that physical objects are computable: mathematicians produce proofs of finite length, something a conventional algorithm can do as well. So while mathematicians might be able to solve more problems than Mathematica 100, there are always cases where they won't work.
  20. Dec 13, 2015 #19
    Yes this is more or less what I had in mind. There's just something that is off with that argument for me, but I don't have enough knowledge on the topic to see if it's just my blunder or not.
  21. Dec 13, 2015 #20
    I'm trying to follow this thread and read the paper. But what is the fundamental relevance of critical quantum systems? Low temperature superconductors and sonons in crystals aside, are critical quantum systems considered to be possible descriptions of how a LQG spin foam becomes a fundamental particle or how a collection of some of those particles become a nucleus or am I totally misinterpreting that? It seems like the condensed matter angle is reckoning with core problems but I'm not sure I see the connection to the general case.

    Also, if there was no spectral gap... or there weren't always some gaps somewhere wouldn't everything just be one big crystal or wave by now?
    Last edited: Dec 13, 2015
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Spectral Gap or Gapless Undecidable
  1. Spectral Scattering (Replies: 0)

  2. Spectral function (Replies: 3)