4 ms·

Wait, Does that imply that it could be possible to construct a system which gives uncomputable results? Does it assume an infinite plane or something? (Assume

by drdeca 11y ago

Wait, Does that imply that it could be possible to construct a system which gives uncomputable results? Does it assume an infinite plane or something? (Assume might be the wrong word) Because, if there's something uncomputable, due to halting problem, how does that fit with the bekenstein bound?

mathgenius 11y ago
> Does that imply that it could be possible to construct a system which gives uncomputable results? They produce a family of systems for which it is not possible to construct an algorithm that can yield a certain property (being gapped) of each system. > Does it assume an infinite plane or something? (Assume might be the wrong word) Yes. The system is infinite. (Or, take a limit as the system size grows to infinity.)
misja111 11y ago
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.
adrianN 11y ago
No, that is incompatible with the definition of undecidable. Any fixed system either has a gap or doesn't, so for fixed systems there always exists a TM that produces the right answer (it's either the one that say yes, or the one that says no). To make something undecidable you necessarily need to have an infinite family of systems. As the (observable) universe can only contain a finite number of things (AFAIK), the universe can't contain an undecidable family of systems. This result "merely" provides some evidence that the TM that decides the has-a-gap problem for all systems in the universe might be pretty large, which is kind of a bummer if you want some concise description from which you can make predictions about the universe.
- noobermin 11y ago
  I've always wondered about this. Whether or not the universe has an infinite number of things or not, human beings and thus science will be constrained to measuring and understanding a countable subset of phenomena in the universe. If that is the case, then it seems like the universe of discourse in science is really countable, up to an extent. Parametrizations of the theories may be continuous, like spacetime is continuous, but can the body of "scientifically tested statements" be continuous? You can only put every scientifically tested theory into a one-to-one correspondence with the number of experiments done to test them, which is a countable set.
  - deleted 11y ago
    [deleted]
  - bweitzman 11y ago
    Wouldn't an infinite number of things imply an infinite amount of energy which would render the conservation of energy laws meaningless?

by drdeca 11y ago

mathgenius 11y ago

> Does that imply that it could be possible to construct a system which gives uncomputable results? They produce a family of systems for which it is not possible to construct an algorithm that can yield a certain property (being gapped) of each system. > Does it assume an infinite plane or something? (Assume might be the wrong word) Yes. The system is infinite. (Or, take a limit as the system size grows to infinity.)

misja111 11y ago

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.

adrianN 11y ago

No, that is incompatible with the definition of undecidable. Any fixed system either has a gap or doesn't, so for fixed systems there always exists a TM that produces the right answer (it's either the one that say yes, or the one that says no). To make something undecidable you necessarily need to have an infinite family of systems. As the (observable) universe can only contain a finite number of things (AFAIK), the universe can't contain an undecidable family of systems. This result "merely" provides some evidence that the TM that decides the has-a-gap problem for all systems in the universe might be pretty large, which is kind of a bummer if you want some concise description from which you can make predictions about the universe.

noobermin 11y ago
I've always wondered about this. Whether or not the universe has an infinite number of things or not, human beings and thus science will be constrained to measuring and understanding a countable subset of phenomena in the universe. If that is the case, then it seems like the universe of discourse in science is really countable, up to an extent. Parametrizations of the theories may be continuous, like spacetime is continuous, but can the body of "scientifically tested statements" be continuous? You can only put every scientifically tested theory into a one-to-one correspondence with the number of experiments done to test them, which is a countable set.
- deleted 11y ago
  [deleted]
- bweitzman 11y ago
  Wouldn't an infinite number of things imply an infinite amount of energy which would render the conservation of energy laws meaningless?