Wild to me that pieces like this ignore Wolfram and specifically his computational irreducibility. Much more precise rendition of the equivalent but less robust concept undecidability. The key insight he arrives at is that predicting/modeling a system is itself a computational process and the ability of a modeler to make computationally less expensive predictions is dependent both on their own computational capability and the nature of the computation. It is very neat and precise and systematic. "Next level" chaos is just more poor imprecise metaphor.
Here is his 1984 article published in PRL in which he highlights that cellular automata can be realized as physical systems and therefore computational intractabilities will manifest in models of physics.
Honest question: isn’t that the same thing as saying that computers use phyisical processes, so all programs are physical processes, so all concepts of intractability in programming also apply to physics?
You lost me at, "What exactly is a phase change? Why can't we predict all possible states of matter and why do we keep discovering new ones? Can high energy particles form bonds with themselves or each other? Could you build a nucleus of neutrinos surrounded by a photon cloud to construct macro scale matter? Why isn't there a periodic table of high energy particles that we've discovered thus far with clear categories of properties and principles (even if incomplete or contradictory) that we teach in schools to challenge our students?
> 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.
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.
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 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.
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.
Wild to me that pieces like this ignore Wolfram and specifically his computational irreducibility. Much more precise rendition of the equivalent but less robust concept undecidability. The key insight he arrives at is that predicting/modeling a system is itself a computational process and the ability of a modeler to make computationally less expensive predictions is dependent both on their own computational capability and the nature of the computation. It is very neat and precise and systematic. "Next level" chaos is just more poor imprecise metaphor.
Arguably it is Wolfram who has ignored the state of knowledge, which is not to entirely disparage his ideas.
Has he published any peer reviewed papers on it?
Here is his 1984 article published in PRL in which he highlights that cellular automata can be realized as physical systems and therefore computational intractabilities will manifest in models of physics.
https://content.wolfram.com/sw-publications/2020/07/undecida...
Honest question: isn’t that the same thing as saying that computers use phyisical processes, so all programs are physical processes, so all concepts of intractability in programming also apply to physics?
It’s all just electrons, right?
If you're going to be reductive, you might as well go all the way and say it's all just fluctuations and perturbations of quantum fields, right?
You lost me at, "What exactly is a phase change? Why can't we predict all possible states of matter and why do we keep discovering new ones? Can high energy particles form bonds with themselves or each other? Could you build a nucleus of neutrinos surrounded by a photon cloud to construct macro scale matter? Why isn't there a periodic table of high energy particles that we've discovered thus far with clear categories of properties and principles (even if incomplete or contradictory) that we teach in schools to challenge our students?
That isn't his physics project.
Does he have any theorems about this?
This is a popular science article, not a scientific paper.
> Cubitt put undecidability on a collision course with large quantum systems in 2012.
Nominative determinism…
https://www.dr-qubit.org/qubit.html
Toby Cubitt's website
I prefer “aptronym” but yeah.
> 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
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
[dead]