They are considering the limit if an infinite system size and then
asking if you get a continuous spectrum or if the ground state is
separated by a gap from the excited states in that limit. That this is
not decidable is perhaps surprising, but this has nothing to do with
Nature not being computable. Turing gave an example of a physical system
that exhibits the same phenomena in an appropriate limit a long time
ago.
Saibal
On 23-09-2015 06:26, Bruno Marchal wrote:
On 22 Sep 2015, at 19:27, Brent Meeker wrote:
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.
? I am not sure.
So they would not assume Church-Turing.
? You need Church thesis to define "hyper-Turing" computation. In fact
you need a stronger version of Church's thesis, a sort of
hyper-Turing Church thesis (the hyper-arithmetical Church's thesis).
Without Church's thesis, computation is not definable, still less
hyper-computation.
Bruno
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.
http://iridia.ulb.ac.be/~marchal/
--
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.
