Spectral Gap or Gapless Undecidable

[mfb]

Or does it mean that you don't know if there IS a threshold at all?

Right.

n that case though, why state it in such an awkward way as "the threshold is uncomputable" instead of just saying "you don't know whether there is a threshold"?

It is a stronger statement: we don't know, and we cannot know in general.

 

[jerromyjon]

It is a stronger statement: we don't know, and we cannot know in general.

I'm still struggling to find a tangible example to relate what it is we can't know.
I think the simple question I have to ask is, does this simply apply to the model as incapable of predicting or is it physics that can't be predicted?

 

[mfb]

No model can predict it for every system.

Do you know the halting problem? It is a related problem, but maybe easier to understand.

 

[jerromyjon]

Do you know the halting problem?

I spent my adolescence fighting it. In what you would consider these days at a crawl.

Thanks I just ran everything I ever did on every computer in a microscopic miniscule sector in microseconds in my head...

 

[ddd123]

No model can predict it for every system.

So you can still find "creative" answers for specific systems?

 

[jerromyjon]

So you can still find "creative" answers for specific systems?

I think that's the point. You can't have a system solve anything. This says you can figure it out but no system can do it itself, I guess.
Quantum physics defies the construction of a "turing complete" computer.

 

[jerromyjon]

is it physics that can't be predicted?

I guess I answered my own question but does my understanding seem to follow the problem?

Quantum physics defies the construction of a "turing complete" computer.

That is the age 16 answer that I think I still agree with.

 

[ddd123]

That's what Penrose says (if you mean: Church-Turing is wrong; Turing-completeness refers to machines that can simulate a Turing machine, not the other way around, so I don't think that's what you meant) but I don't think this particular result points in that direction if mfb gave us the correct interpretation. Here it's just saying: there is an undecidability example in infinite-sized Hamiltonians. But Wang tiles are classical, infinite-sized and undecidable too. Quantum physics can still be simulated classically, only less efficiently in some cases.

As for unpredictable physics, again if mfb gave us the correct answer, the unpredictability lies in unbounded cases, but even classically. Suppose we write up a system in which there's only a box in empty space that tries every possible zero for the Riemann Zeta, and turns on a rocket if it finds one. Is the phase space bounded or not? But classical physics is supposed to be deterministic so you should be able to know. Then again, the box must have finite memory to store the numbers.

 

[jerromyjon]

Logic in computer science
"The Curry-Howard correspondence is a relation between logical systems and software. This theory established a precise correspondence between proofs and programs. In particular it showed that terms in the simply-typed lambda-calculus correspond to proofs of [intuitionistic propositional logic]."

I think that makes the problem of looking for a "specific" needle in a haystack with many similar needles.

 

[ddd123]

They were talking about that earlier in the thread. The problem for me now is: what does the "in general" in "in general the threshold is not computable" mean? That in all cases we can't compute it, or that we can't compute it for all cases (i.e. we can find out creative solutions for specific cases but not a general solution)? By the earlier discussion, it seemed like the former was true; but by reading, for example, Scott Aaronson's explanation, the latter seems to be the correct one (and the one which is more pertinent to the halting problem).

I mean: what if we actually find the threshold for one of those specially constructed cases in the paper, by a mathematical intuition or by brute force? Then we have computed it, contradicting the paper's theorem. There must be something I'm missing still.

 

[mfb]

or that we can't compute it for all cases (i.e. we can find out creative solutions for specific cases but not a general solution)?

This.

I mean: what if we actually find the threshold for one of those specially constructed cases in the paper, by a mathematical intuition or by brute force?

The specially constructed cases correspond to an infinite set of problems, and they prove that no algorithm can solve all of them.

 

[Demystifier]

It seems that Seth Loyd had a very similar result a long time ago:
http://lanl.arxiv.org/abs/1602.05924

 

[Strilanc]

That was commented on in an update to the Scott Aaronson post I linked:

Update (Dec. 20): My colleague Seth Lloyd calls my attention to a PRL paper of his from 1993, which also discusses the construction of physical systems that are gapped if a given Turing machine halts and gapless if it runs forever. So this basic idea has been around for a while. As I explained in the post, the main contribution of the Cubitt et al. paper is just to get undecidability into “the sort of system physicists could plausibly care about” (or for which they could’ve plausibly hoped for an analytic solution): in this case, 2D translationally-invariant nearest-neighbor Hamiltonians with bounded local dimension.

Although I have to say I'm enjoying the 2016 paper you linked. I find Seth Lloyd entertaining to watch and read:

References [2-3] belong to the medieval era of quantum information theory, pre-Shor and pre-arXiv: the contemporary reader may compare them to illuminated manuscripts. I now redescribe their results in contemporary language.