An article published in Nature yesterday proves that finding the spectral gap of a material based on a complete quantum level description of the material is undecidable (in the Turing sense).

One of the authors is quoted "From a more philosophical perspective, they also challenge the reductionists' point of view, as the insurmountable difficulty lies precisely in the derivation of macroscopic properties from a microscopic description."

  • Does this result eliminate once and for all the possibility of a theory of everything based on fundamental physics?
  • Does this result refute once and for all the reductionist position?
  • Does this confirm (see previous question) that Turing's undecidability result is indeed an epistemic result and that undecidability places a limit on our knowledge of the world?

Per Nir's comment, I need to clarify that I'm not asking for a discussion of the validity of the paper (that's a Physics SE question), but for the philosophical consequences given the result of the paper

  • 3
    I up-voted the question since I believe that paper may be important, and I understand your desire that we discuss it here, but I think you should edit your post, since it does not make sense to ask this community at this point questions of the form "Does this result <something> once and for all?" — I mean, who in this community can say? the paper is about 140 pages of (probably) advanced physics — is it a breakthrough? does it contain a substantial flaw? who knows? the only reasonable way to answer your question is with "we do not know". – nir Dec 11 '15 at 17:06
  • that said, assuming the paper is veridical, then I would be interested to know if it might be the birth of hyper-computation. – nir Dec 11 '15 at 17:08
  • 1
    "although a theoretical model of a quantum many-body system is always an idealisation of the real physics, the models we construct in the proof of Theorem 1 are highly artificial. Whether the results can be extended to more natural models is yet to be determined. A related point is that we prove undecidabiltiy of the spectral gap (and other low-temperature properties) for Hamiltonians with a very particular form. We do not know how stable the results are to small deviations from this". So no, for now this is interesting mathematics detached from reality. – Conifold Dec 11 '15 at 17:09
  • @nir My intent isn't a discussion of the results of the paper per se - but more along the lines of: given the results of this paper, what are the consequences. For that I assume people who know more about the philosophy of science than I do can offer educated answers off the bat without diving into the physics of the paper itself. Also the paper is only 4 pages (Nature papers are never too long). – Alexander S King Dec 11 '15 at 17:10
  • then, I think it would be better to simply ask those of us who are physicists to try to explain the results in laypeople terms, and warn them to avoid hyperbole, speculation and nonsense. I believe we are talking of this paper Undecidability of the Spectral Gap – nir Dec 11 '15 at 17:19

What the result means, essentially, is that in certain toy models there can be no algorithm deriving some macroscopic characteristics (spectral gap) from microscopic parameters of the models. The main import is that we get a Gödel sentence that unlike the original has some explicit mathematical meaning. Let's be generous and assume that the situation extends to more realistic theories of matter. What are the philosophical consequences for reductionism?

First, existence of undecidable sentences is a property of a theory, not a property of reality it describes, so we are talking not about ontological reductionism but about theory reductionism. Second, the authors mean "undecidable" in two different senses, one result states that there is no algorithm for finding the spectral gap in a class of models, the other result states that in some "artificial" models existence of the gap is neither provable nor disprovable. The former is not exactly surprising, deriving macroscopic properties of models is highly non-trivial even in classical statistical mechanics, although this may be the first explicit proof of it. The latter is more interesting, but undecidability is always relative. The Gödel sentence of arithmetic is provable in the standard set theory (ZFC), the Gödel sentence of ZFC is provable if one additionally assumes that there is an "inaccessible" cardinal, the continuum hypothesis is provable if one assumes that the sets are "constructible", and so on.

And in the end the difference between the two senses is technical, both mean that theoretical analysis of models requires non-trivial insights, whether using existing ways of reasoning non-trivially, or discovering new ones. But this has always been the case historically even in arithmetic, proofs of interesting number-theoretic results, even decidable ones, weren't found by an algorithm. Matiyasevich even proved in 1970s that there can be no algorithm for deciding solvability of Diophantine equations, it doesn't mean that specific Diophantine equations can not be solved or proved unsolvable. Wiles did the latter recently for Fermat equations, and we still don't know if arithmetic alone is sufficient for his proof. Cubitt, one of the authors, says as much: "It's possible for particular cases of a problem to be solvable even when the general problem is undecidable, so someone may yet win the coveted $1m prize".

Mathematicians have a notion of a "wild" classification problem, where classification of certain theoretical objects is intractable in principle. Classification problem for pairs of ordinary matrices is already wild, there is no surveying "Jordan canonical forms" for pairs. Cubitt implies that the source of undecidability in their case is another wild problem:"The reason this problem is impossible to solve in general is because models at this level exhibit extremely bizarre behavior, that essentially defeats any attempt to analyse them". So if theoretical reductionism was supposed to mean that one can get an algorithm for finding high level properties of derived objects from axioms for basic ones then reductionism was doomed for a while now. To summarize, there are no consequences for ontological reductionism, and for theoretical reductionism the paper confirms what we always suspected: reducing high level theory to a low level theory is a non-trivial business.

EDIT: I asked a question on Math Overflow about the technical side of the result. The paper was on arxiv for a year and is well understood by experts. The undecidability in it is typical, the proof is based on the undecidability of the halting problem for Turing machines, and is analogous to Matiyasevich's proof for Diophantine equations. This means that we are no more likely to encounter undecidable Hamiltonians in physics than we are to encounter Gödel sentences in number theory. In particular, the status of the spectral gap millenium problem for the Yang-Mills Hamiltonian is unaffected.

If a model turns out to be undecidable, people will know to avoid models of this kind. It remains to be seen how large is the class of such models (the longer version of the paper in the arxiv is over 150 pages). But it would be premature to announce the death of reductionism just because cases illustrating Goedel's finding have been constructed.

  • So we can actually use underdetermination to our advantage? If your theory is undecidable, fear not, Quine says you can always find another one. Do I get your point correctly? – Alexander S King Dec 11 '15 at 18:19
  • Yes. Adding: simple models breed paradoxes e.g. chicken-and-egg or Schroedinger's cat; the Nature abstract mentions a model with nearest neigbours (the centre of a square interacts only with mid-edge points, not with angle points) this is the most simple 2D case. Huygen's principle does not work in 2D (but in 3D (or 1D)). – sand1 Dec 11 '15 at 18:58

It seems like further evidence that in some ways indeterminism plays a basic part in physics.

If this is so, then the burden of explanation then surely must fall on saying why this is so.

The basic puzzle in QM, after all, is that the act of measurement is indeterministic, and because of Bells Inequalities, not stochastically so (ie dependent on 'hidden variables'); so, in a sense, this result is not adding anything new, but simply confirming this basic result.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.