3 ms·

But spectral gaps do occur in nature. Does that mean that even though it is impossible to compute if a spectral gap will occur or not, we could just observe suc

But spectral gaps do occur in nature. Does that mean that even though it is impossible to compute if a spectral gap will occur or not, we could just observe such a system in nature and that way we could build a computer which would compute uncomputable results?

mathgenius 11y ago
I think not, since these systems are "infinite", ie. you would never know how big to build it before you got close enough to the correct result.
sharpneli 11y ago
In nature it does not matter if the spectral gap is really tiny. It's de facto without spectral gap if it's just small enough. Whereas for this particular decision problem the mere existence of spectral gap matters.
- selimthegrim 11y ago
  Who says? Graphene gaps, (it must gap) even though its so small it's impossible to observe in practice. This had very important consequences for topological materials theory...
  - sharpneli 11y ago
    This is exactly what I meant. Even if it has theoretical reasons to have a tiny gap in practice it works as zero gap.
    - tobycubitt 11y ago
      Except that in our result, the spectrum is either continuous, or the spectral gap is guaranteed to be >= 1 (in natural units). It does not become arbitrarily small in the gapped case. The reason you can't use this to compute the uncomputable is that real systems are finite, and the spectral gap is always computable in principle (maybe with a lot of effort) for any finite system. A real (possibly very large but still finite) system will either have a gap or not, and you'll be able to measure it. This definitely doesn't solve an undecidable problem. However, the undecidability in the idealised infinite lattice limit "shows through" to the experimentally accessible finite-size case, in the form of some rather unusual finite-size physics. This is discussed in more detail in the paper itself (the relevant section is quoted verbatim here http://mathoverflow.net/a/225905 http://mathoverflow.net/a/225905) and in the comments on Scott Aaronson's blog.
deleted 11y ago
[deleted]
lmm 11y ago
Sounds like it doesn't it? Could we build a big sheet of this material that encoded e.g. a search for a counterexample to the Riemann Hypothesis, and then just measure whether it had a gap or not? I can't believe that it would be that simple, but I can't immediately see anything wrong with that logic.

mathgenius 11y ago

I think not, since these systems are "infinite", ie. you would never know how big to build it before you got close enough to the correct result.

sharpneli 11y ago

In nature it does not matter if the spectral gap is really tiny. It's de facto without spectral gap if it's just small enough. Whereas for this particular decision problem the mere existence of spectral gap matters.

selimthegrim 11y ago
Who says? Graphene gaps, (it must gap) even though its so small it's impossible to observe in practice. This had very important consequences for topological materials theory...
- sharpneli 11y ago
  This is exactly what I meant. Even if it has theoretical reasons to have a tiny gap in practice it works as zero gap.
  - tobycubitt 11y ago
    Except that in our result, the spectrum is either continuous, or the spectral gap is guaranteed to be >= 1 (in natural units). It does not become arbitrarily small in the gapped case. The reason you can't use this to compute the uncomputable is that real systems are finite, and the spectral gap is always computable in principle (maybe with a lot of effort) for any finite system. A real (possibly very large but still finite) system will either have a gap or not, and you'll be able to measure it. This definitely doesn't solve an undecidable problem. However, the undecidability in the idealised infinite lattice limit "shows through" to the experimentally accessible finite-size case, in the form of some rather unusual finite-size physics. This is discussed in more detail in the paper itself (the relevant section is quoted verbatim here http://mathoverflow.net/a/225905 http://mathoverflow.net/a/225905) and in the comments on Scott Aaronson's blog.

deleted 11y ago

[deleted]

lmm 11y ago

Sounds like it doesn't it? Could we build a big sheet of this material that encoded e.g. a search for a counterexample to the Riemann Hypothesis, and then just measure whether it had a gap or not? I can't believe that it would be that simple, but I can't immediately see anything wrong with that logic.