On 9/22/2015 5:17 AM, Bruno Marchal wrote:
On 22 Sep 2015, at 00:29, Brent Meeker wrote:
A fascinating application of computability theory to physics:
Undecidability of the Spectral Gap
Toby Cubitt, David Perez-Garcia, and Michael M. Wolf
The spectral gap—the difference in energy between the ground state
and the first excited state—is one of the most important prop-
erties of a quantum many-body system. Quantum phase transitions occur
when the spectral gap vanishes and the system becomes
critical. Much of physicsis concerned with understanding the phase
diagrams of quantum systems, and some of the most challenging
and long-standing open problems in theoretical physics concern the
spectral gap, 1–3 such as the Haldane conjecture 4 that the Heisen-
berg chain is gapped for integer spin, proving existence of a gapped
topological spin liquid phase, 2,3 or the Yang-Mills gap conjecture 5
(one of the Millennium Prize problems). These problems are all
particular cases of the general spectral gap problem: Given a quan-
tum many-body Hamiltonian, is the system it describes gapped or
gapless? Here we show that this problem is undecidable, in the
same sense as the Halting Problem was proven to be undecidable by
Turing.
I guess he means unsolvable.
"undecidable" is relative to a theory. Unsolvable or uncomputable is
absolute and does not depend on any theory. It means that there is no
alogorithm to do some task, like computing some function or deciding
some set.
6 A consequence of this is that the spectral gap of certain
quantum many-body Hamiltonians is not determined by the axioms of
mathematics,
? (that does not make sense)
much as Gödels incompleteness theorem implies
that certain theorems are mathematically unprovable.
Gödel proved only that all theories are undecidable when it comes to
proving propositions in some domain (like natural numbers).
It makes no sense to say that some mathematical proposition are
unprovable. there always some theories which can prove them: just keep
such proposition as axioms, for example. PA (or ZF, ...) cannot prove
that PA is consistent, but PA + consistent(PA) can prove that PA is
consistent, trivially. More interestingly: PA + epsilon-zero is well
founded can also prove that PA is consistent.
We extend these results to prove undecidability of other low
temperature prop-
erties, such as correlation functions.
Well, I guess again that they talk only about unsolvability, not
undecidability.
The proof hinges on simple quantum many-body models that exhibit
highly unusual physics in
the thermodynamic limit.
I will take a look when I have more time. I might need to revise a bit
the quantum many-body problem for that!
In QM, already the 0-body problem is Turing complete (when you need at
least three bodies to have Turing completeness for classical physics),
so it is hard to be astonished, but I don't judge the paper (above
using a vocabulary which is confusing when you know the difference
between computing and proving). The main difference is that in proof
theory, the result are dependent of the theory (they are not
absolute), where in computability, the results are absolute if we
assume Church-thesis (which is accepted by virtually all experts in
the domain).
But I think their motivation was to show that nature may perform
hyper-Turing computation. So they would not assume Church-Turing.
Brent
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
