'Next-Level' Chaos Traces the True Limit of Predictability(www.quantamagazine.org)
83 pointsby pseudolus4 months ago6 comments
  • jonahbenton4 months ago
    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.
    • UltraSane4 months ago
      Has he published any peer reviewed papers on it?
      • markisus4 months ago
        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...

        • brookst4 months ago
          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?

          • criddell4 months ago
            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?
            • weard_beard4 months ago
              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?
        • UltraSane4 months ago
          That isn't his physics project.
    • nathan_compton4 months ago
      Arguably it is Wolfram who has ignored the state of knowledge, which is not to entirely disparage his ideas.
    • drdeca4 months ago
      Does he have any theorems about this?
    • ironSkillet4 months ago
      This is a popular science article, not a scientific paper.
  • cgio4 months ago
    > Cubitt put undecidability on a collision course with large quantum systems in 2012.

    Nominative determinism…

  • andrewflnr4 months ago
    > 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

    • markisus4 months ago
      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

      • andrewflnr4 months ago
        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?
        • markisus4 months ago
          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.

    • Legend24404 months ago
      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.

      • andrewflnr4 months ago
        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.
        • rstuart41334 months ago
          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.

    • qazxcvbnm4 months ago
      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.
      • bawolff4 months ago
        > 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.

        • qazxcvbnm4 months ago
          You're right, it's not the same. Undecidable properties are not related in general.
          • bawolff4 months ago
            To be more clear, i'm saying it is not undecidable in the sense that mathematicians use the term.
    • bawolff4 months ago
      > 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.

    • patcon4 months ago
      > The paper[0] is paywalled

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

  • 4 months ago
    undefined
  • 4 months ago
    undefined
  • fuck_google4 months ago
    [dead]