Right. All physical systems are finite, so they are necessarily
computable. The gap in the limit is undecidable like the halting
problem is undecidable; you have to run the computation to find out and
no matter how big you have made the system you cannot be sure that
making it a little bigger won't change it from gapped to gapless. At
least that's how I understand the result.
Brent
On 9/23/2015 8:38 AM, smitra wrote:
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.
