'Next-Level' Chaos Traces the True Limit of Predictability(www.quantamagazine.org)
75 pointsby pseudolus2 days ago6 comments
  • jonahbenton2 days 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.
    • nathan_comptona day ago
      Arguably it is Wolfram who has ignored the state of knowledge, which is not to entirely disparage his ideas.
    • drdeca2 days ago
      Does he have any theorems about this?
    • ironSkillet2 days ago
      This is a popular science article, not a scientific paper.
    • UltraSane2 days ago
      Has he published any peer reviewed papers on it?
      • markisusa day 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...

        • brooksta day 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?

          • criddella day 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?
  • cgioa day ago
    > Cubitt put undecidability on a collision course with large quantum systems in 2012.

    Nominative determinism…

  • andrewflnr2 days 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

    • markisusa day 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

      • andrewflnra day 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?
        • markisusa day 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.

    • Legend2440a day 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.

      • andrewflnra day 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.
        • rstuart4133a day 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.

    • qazxcvbnma day 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.
      • bawolffa day 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.

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

    • patcona day ago
      > The paper[0] is paywalled

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

  • a day ago
    undefined
  • 2 days ago
    undefined
  • fuck_google2 days ago
    [dead]