On 23 Sep 2015, at 23:42, Brent Meeker wrote:
On 9/23/2015 12:19 PM, Bruno Marchal wrote:
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.
But many scientists implicitly assume that reality is computable,
But this is ambiguous. From outside the universe compute the empty
function, so it is computable by the algorithm "do-nothing".
Computable applies to "function from N to N ore recursively
equivalent)" (which might be characteristic function of a set, so we
can extend the notion of computability to set belongness, and if the
set is a set of theorem, semi-decidable will correspond to *partial*
computability).
An expression like "reality is computable" does not make sense a
priori, as "reality" is a term impossible to define from inside a
theory or system.
that there is an algorithm for deciding how the state of the
universe evolves.
OK, in that sense, it is better to use the term emulable or simulable,
which can be applied to processes (and be well defined using the
intensional Church thesis). This is directly refuted by
computationalism if we define reality by what we can observe (which is
1p and typically non computable), but would be computable, and look
computable (in that "emulable sense) if current physics is exact.
Of course with comp, the notion of "physical universe" is quite
different than from what we usually understand by such terms. The
physical universe is a first person sharable history. There is no
physical universe per se; only numbers coherent dreams.
All known *processes" in Nature are Turing-emulable. But that does not
yet entails that derivative of known processes are computable. Specker
showed that there are computable function with a derivative which is
not computable (from R to R, a notion which does not really have a
Church thesis, but there is a more or less standard definition given
by Turing). Now, such weird function have not been encountered in
nature, but computationalism leads to the idea that some observation
are not predictible, but then it might just be the outcome of a self-
superposition or self-duplication.
And so they reject the idea that reality is isomorphic to arithmetic.
Which reality? With computationalism, we can take as "fundamental
reality" the tiny sigma_1 part of arithmetic. This gives a set which
is already not computable, but it is partial computable, and we can
recursively enumerate the *true* sigma_1 sentences (but already not
the false one, or we could decide the halting problem). Now the full
(first order) arithmetic is far bigger than this, and most
arithmetical proposition are undecidable in al all first order theories.
Then, having that simple (but only partially computable ontology), the
physical reality is necessarily not computable and much more complex,
although than we can bound the complexity by the level of
unsolvability of qG*: it PI_1 complete in the oracle for arithmetical
truth. If God is arithmetical truth, then God is already overwhelmed
by the complexity of machines like PA, and this, by the FPI plays some
role in the mergence of the physical reality. The problem of comp is
that the observable, or knowable, or "feelable" realities are a priori
NOT computable.
the real miracle here, is that at the proposition level, those
modalities are decidable. (G* is decidable, and can be emulated by G).
If the mass gap is not computable that's very surprising.
I have to dig on this.
But I'm afraid it depends on systems being potentially infinite,
which is dubious.
Why? I mean that you would have said "actually infinite", I could
understand why it is dubious, but potential infinity is already
present with self-dividing amoeba, universal machine, natural numbers,
any algorithm in fact.
Only ultra-finitism in general would be a problem for a
computationalist. Ultra-finitism in physics would lead to digital
physics, and that would indeed contradict computationalism (and
provide magical attribute to some "primitive matter").
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.
