Hacker News Reader

Comment by andrewflnr | Hacker News Reader

> In a paper published in Nature in 2015, they proved that the spectral gap problem is equivalent to the halting problem (opens a new tab) — and therefore undecidable. If someone handed you some complete description of the material’s particles, it would either have a gap or not.

Hold up. This is experimentally findable, right? Did they just invent a physical halting oracle? ...Hmm. The paper[0] is paywalled, but the abstract mentions aperiodic tilings. This might be a situation where the undecidability only holds if the material is actually infinite, in which case its significance is little more dubious. Still cool, but not practical-halting-oracle cool.

[0] https://www.nature.com/articles/nature16059

View on HN

Here is a free updated version from 2022. https://arxiv.org/pdf/1502.04573

Edit: Alright, I'm back after skimming the paper. This is a halting oracle.

Here is what I understand, with my limited knowledge of QM. There are two ingredients (Theorem 3: Main Theorem, page 6).

1. For each integer n, the authors construct a spin lattice model H(n).

2. There is a specific Universal Turing Machine, that halts on n iff H(n) is gapped.

Here is how to construct the oracle. For any Turing machine, find out what integer n it corresponds to for the specific Universal Turing Machine of the paper. Then physically construct H(n) and see if it's gapped.

However, this H(n) cannot be physically realized. First, it is an idealized model in which lattice points only interact with their neighbors. Second, it actually a family of lattices, and the result is about the thermodynamic limit as the lattice becomes infinite.

Interestingly, Seth Lloyd appears to have previously proved this result in 1993. https://arxiv.org/pdf/1602.05924

That sounds right, as far as I can understand it. :D What does "thermodynamic limit" mean here, as opposed to the regular limit as it becomes infinite?

It's defined on page 5.

> In this paper we are considering the behaviour of ∆(HΛ(L)) in the thermodynamic limit, that is, when L → ∞

So it's the same as the regular mathematical limit. There must be some thermodynamic implications but my knowledge of physics is not enough to say.

It's not an oracle. 'equivalent to the halting problem' just means 'your system is a turing machine'.

>Even if someone attempted to build one of the machines depicted in these blueprints, however, researchers point out that undecidability is a feature of physical theories and cannot literally exist in real experiments. Only idealized systems that involve infinity — an infinitely long tape, an infinitely extensive grid of particles, an infinitely divisible space for placing pinballs and rubber ducks — can be truly undecidable.

It's a property that can be measured in finite (constant?) time, that's determined by a halting-complete problem. Unless I drastically misunderstood, and except for the whole finite-size thing.

I didn't understand the think completely (I suspect you would have to read the page) but they do mention a Turing machine with an infinite tape several times, then they say they used the quantum states of a finite sized system to emulate that tape.

That makes sense. You can always in principle determine if a finite system halts (although resource constraints mean you may not be able to do so in practice). So their system must be able to contain an infinite amount of information despite being finite in size.

But that does mean they are assuming an infinity lurks within every qubit. I didn't realise we understood quantum so well we can confidently make that assumption.

Halting (problem) is undecidable. Undecidability is not just the halting problem. Whether you go to the park on a given day is undecidable (assuming you have free will, and all such assumptions), but that you can be an oracle for this does not solve the halting problem.

> Whether you go to the park on a given day is undecidable

I feel like that is not really undecidable in the same way the halting problem is. The result does not depend on the input. It'd be like saying checking primality is undecidable if you dont know what number you're supposed to check.

You're right, it's not the same. Undecidable properties are not related in general.

To be more clear, i'm saying it is not undecidable in the sense that mathematicians use the term.

> Did they just invent a physical halting oracle?

I haven't read the article, but it sounds more like they invented a computer.

Like you can tell if an algorithm halts (if it does so) by running an algorithm until it halts. However that isn't an oracle because you may have to run it for infinite steps to get an answer.

> The paper[0] is paywalled

For those in unblocked jurisdictions: https://sci-hub.st/10.1038/nature16059

Reply on news.ycombinator.com