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.
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.)
Whereas for this particular decision problem the mere existence of spectral gap matters.
Even if it has theoretical reasons to have a tiny gap in practice it works as zero gap.
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) and in the comments on Scott Aaronson's blog.
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?