On 23 Sep 2015, at 06:51, Brent Meeker wrote:
On 9/22/2015 9:26 PM, 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.
Yes, and it would be quite surprising to find there is no algorithm
to compute whether or not a Hamiltonian system has a mass gap -
since it is presumably a fact of nature whether it does or not.
Not sure that this entails the existence of an algorithm. In the
arithmetical reality, many facts exists with provably no algorithm to
decide them.
This may point to nature doing hyper-Turing computation or there may
be some aspect of nature that has been overlooked. Either way it's
an interesting development.
I am not sure the paper alludes to hyper-Turing computation. Despite
his quite bad vocabulary, the paper is correct on Church thesis, which
it accepts, and concerns just insolubility, I mean unsolvability in
theoretical physics. Like such result exist in topology, group theory,
etc.
What amaze me is the technic and some results by Kitaev.
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.
That doesn't help if nature somehow computes whether or not there is
a mass gap, but you can't.
If one universal system can compute something, all the other universal
system, including you and me, can do the computation, if we are given
the time.
Simply adding an axiom may contradict nature so then you have a
provable proposition, but it's empirically false.
OK. But in this case I was assuming the addition of a true axiom. This
makes many propositions which were true but undecidable in the theory
becoming decidable. "True" means "satisfied by the domain under
scrutiny" (with or without the theory or ourself knowing it).
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.
I meant they would not assume that computability or solvability was
limited to Church-Turing computation.
They do assume Church's thesis (page 10). They have too, if they want
to prove that something is not computable or that a problem is
unsolvable. Like Church thesis needs to be used to prove that
Hilbert's tenth problem about solving mechanically the diophantine
polynomial equation is impossible. There is no algorithm to decide if
a diophantine polynomial equation has a solution or not.
Church's thesis is also used to show that some problem are unsolvable
even by machine using powerful non computable oracle §like the
decidability of quantified G*).
The result in the paper are not so astonishing, as he use "condensed
matter" type of material which is already Turing complete. But the
technic seems cute as far as I understand right now.
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.
