6 ms·

Computation has turned out to be a far more general concept than I think was imagined, up to the point that many computer scientists now seem to equate computat

by sgt101 3mo ago

Computation has turned out to be a far more general concept than I think was imagined, up to the point that many computer scientists now seem to equate computation with the functioning of the universe. Recently it's been shown that there are real, physical processes which are undecidable (we cannot know if a latice of atoms has a spectral gap or not, we cannot determine if a specific particle in a fluid flow will reach a specific place or not, we cannot determine if a ray of light will reach a specific target in certain configurations of reflection). Our world appeared computable, but it isn't, even if P=NP.

gradys 3mo ago
It can be the case that both: - The physics of the universe can be completely modeled as computation, and - It's possible to pose undecidable problems about the way the universe unfolds This is intrinsic to the idea of undecidability even for Turing machines, e.g. "we equate computation with the functioning of Turing machines, but there are real processes executable in Turing machines that are undecidable".
- sgt101 3mo ago
  Of course, if our universe is undecidable it must be the case that computable processes can be executed within it, and it might be the case that all of the processes that are ever executed within it are computable... but it might be that some of the processes that are executed are not computable... because the machine may.. or may not?
  - jerf 3mo ago
    I think there's an equivocation of "computable" going on here. Mathematicians talk about a lot of things like "uncomputable sequences" but that is usually making a statement about the sequence, not necessarily any individual member. The Busy Beaver sequence is uncomputable. You can, however, quite trivially compute BB(2), even in your head if you're a bit careful. You can set up individual elements of an uncomputable sequence in our universe, and you may be unable to state in advance what the system would do with anything less than simply letting it run and see what happens due to the complexity of the system, but being a member of an uncomputable sequence doesn't mean that you can't in fact set those things up and watch them run. The Universe doesn't throw an "UncomputableCircumstance" exception or anything. It just keeps advancing to the next state. Your inability to make certain statements about that next state or some future state is not its problem.
  - chriswarbo 3mo ago
    There's no way to empirically spot an uncomputable process, since it would require infinitely-many observations. For example, if aliens claim their machine solves the halting problem, we could test it on millions of inputs whose halting/not-halting behaviour we already know; but even if it works for all of them, there's no way to know that it works for all inputs. For all we know, it might be a huge lookup table which happens to cover all of those inputs we tried.
    - peter_m1 3mo ago
      No, you can prove things hold in the abstract mathematically, don't need to resort to physical systems.
      - chriswarbo 3mo ago
        I was responding to this part: > if our universe is undecidable My point is, there would be no way to empirically test this; and therefore, it would make no observable difference, there would be no way to exploit/utilise such effects, etc. In essence: there's no way to tell the difference between a real halting oracle (which would imply an undecidable universe), versus a computable approximation which just-so-happens to be more powerful/sophisticated than the approximations we compare it against. Sure, we can prove that some abstract systems are undecidable and that others aren't. Yet that distinction is inherently unfalsifiable, and hence physically "useless".
  - peter_m1 3mo ago
    Quantum mechanics is intrinsically probabilistic.
    - GoblinSlayer 3mo ago
      Deterministic processes can be modeled probabilistically and are computable, so existence of a probabilistic model doesn't say much about computability.
- woopsn 3mo ago
  A key thing about the undecidability problem wrt physics is preparation of the initial state. In math and computer science it is relatively straightforward to prepare such problems now (though this represented an enormous leap conceptually), but the "undecidability" of all physical problems relies on construction of materials that are clearly unconstructable - systems of infinite negentropy (eg Turing machines), infinite mass (the lattice), bespoke local interactions etc. Problems standing in the way of physics decidability are typically chaos, far from equilibrium mechanics, elementary SNR considerations and so forth, not problems of logic.
  - peter_m1 3mo ago
    In physics we don't talk about decidability, but solvability.
Maxatar 3mo ago
>Recently it's been shown that there are real, physical processes which are undecidable I want to push back a bit on this claim along two dimensions. Imagine a physical Turing machine built out of atoms, gears, levers, and an electron parked on the read/write head and ask whether that electron ever crosses some fixed plane in space, which it does only when the machine enters its halt configuration. That's now a purely physical question about a trajectory (does this electron ever reach a certain target), yet answering it for the whole family of such machines is literally the halting problem, so there's a physical process that's undecidable. Your examples about physical processes being undecidable are all basically just this... there examples of using reflections of light, or the flow of liquid, etc... and demonstrating that these physical processes in principle are sufficient to model a universal Turing machine. And while it's fascinating that certain things you may not have expected can be used to model computation, it's misleading, or rather it's too strong of a claim to believe that there exist actual/real physical processes whose outcomes are undecidable. That's a subtle but very common misinterpretation of what undecidability is. Undecidability, whether in physics or computer science, only applies to the infinitely broad class of a problem as a whole, it never applies to a specific instance of a problem. So it can never be the case that there's a certain configuration of reflections for which it's undecidable whether a ray of light reaches a target. Nor can it be the case that for a specific lattice of atoms, it's undecidable whether it has a spectral gap or not. It can only be the case that for the problem as a whole where the parameter space is entirely unbounded, there is no single algorithm that can decide if a ray of light reaches a specific target for all possible arbitrary (and infinitely many) configurations. Once you fix a specific system, then the undecidability goes away. Not claiming that you are necessarily making this misconception, but I often see people misinterpret undecidability to mean that there exists a specific problem, like with specific inputs, where it's somehow impossible to know what the answer will be. Undecidability always requires an infinite family of instances, and it's a statement about the nonexistence of a single algorithm that correctly answers every instance in that family. It says nothing about any particular instance being unknowable/undecidable.
- eth0up 3mo ago
  If I am wrong, please pardon. I suspect I am. But was this comment edited by Claude? I ask specifically because it is well written, substantive, all which is expected here, but the "push back" part, to me, must be a) an artifact of Claude, either by osmotic assimilation (Which is happening to many innocent users) or b) Claude itself. Feel free to flag this comment if I get an answer. I do want to know.
plastic-enjoyer 3mo ago
> up to the point that many computer scientists now seem to equate computation with the functioning of the universe. Do you think that's a kind of tunnel vision? If the only thing you focus on is computation, you'll probably end up seeing computation everywhere - it became a way of seeing the world.
- jerf 3mo ago
  It is a common accusation. There's a somewhat famous quote I've seen a few times: "It's interesting to look back through history on this one. Each age has its pinnacle of technology, and each age uses that technology as a metaphor for nature, for the universe. In ancient Greece, the technological marvels were musical instruments and the ruler and compass. The Greek philosophers tried to build an entire cosmology from number, harmony, proportion, form, and so on — from mathematics, basically. Remember the music of the spheres? The Pythagoreans believed that nature was a manifestation of rational mathematics. Later on the pinnacle of technology was the clockwork. Newton wanted a clockwork universe, the entire universe as a gigantic clockwork mechanism, with all the parts interlocking and ticking over with infinite precision. Then in the 19th century along came steam power, and the universe was then depicted as an enormous heat engine, or thermodynamic machine, running down toward its heat death. Today the computer is the pinnacle of technology, so it's now fashionable to talk about nature as a computational process." Which seems to source from https://www.edge.org/conversation/paul_davies-time-loops https://www.edge.org/conversation/paul_davies-time-loops . While "computer" may give us impressions of something with "a CPU" and "RAM" and "a disk drive", it does at least seem plausible that the universe as computation is a plausible base level, though. Unlike "the music of the spheres", which to the extent that it made predictions of the world, it got them wrong in the most basic way, viewing it through a lens of computation allows us to put some quite subtle and interesting limits on things. "Computation" is a pretty flexible substrate; it is difficult to imagine how the proposition "the universe is a computation and subject to the limitations thereto" could be falsified, and if it could, it is difficult to imagine how we would be able to know it was so falsified. Nevertheless the math of computation allows us to say non-trivial things about the universe as a result; it is not a vacuous generalization, though it is certainly a loose one... being able to say yet more concrete things about the nature of the computation, such as "this is exactly how gravity works", has quite a bit more utility.
mondrian 3mo ago
Undecidability is a problem of answer-extraction from a process, it doesn’t preclude the process from executing deterministically. The universe could well be the live execution of a deterministic, even basic algorithm, with all kinds of questions about its execution being undecidable.
__rito__ 3mo ago
One sentence I heard somewhere wraps up the totality of computing: "If Mathematics is the 'what', Computer Science is the 'how'". This applies to each and everything.
- athrowaway3z 3mo ago
  If two people agreed on that statement, its entirely unclear if they agree with each other and if they found something profound in the first place. The imo much more foundational relationship not everybody is aware of is https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...
not-a-llm 3mo ago
> Recently it's been shown that there are real, physical processes which are undecidable According to the currently known laws of physics. Which we know are incomplete/incorrect in several places.
woopsn 3mo ago
The infinite lattice doesn't represent a "real" physical processes, it's just mathematical technique for closing a (fundamentally) quantized combinatorial sum over millions of interacting elements. The gap problem exists in the limit. For real systems the spectrum can be measured (in principle) by probing the ground state. The computational paradigm is incredibly general but only within what's apparently a pretty atypical thermodynamic regime (the ordered universe).
- peter_m1 3mo ago
  In this case quantum thermo.
nl 3mo ago
Undecidable isn't uncomputable. "Computable" can mean probabilistic, and classical computers can function over probability distributions just fine.
- rudy6912 3mo ago
  This is incorrect. An undecidable problem is one for which no algorithm can compute the correct result for every given instance. Probabilistic classical computation is irrelevant here.
spragl 3mo ago
Both P and NP are computable. That is, a Turing machine can compute both of them. Those quantum processes are interesting. Take the random numbers generated from radioactive decay. They are (after some cleanup) truly random. That is what we think. But how could we tell the difference from pseudorandom numbers, generated by a sufficiently advanced algorithm? We couldnt. So particles could simply be Turing Machines running sufficiently advanced algorithms that we cant reverse engineer. If so, quantum mechanics is computable even if we cant compute it. (Particles being TMs doesnt mean they are FAs with an infinite tape, but that they are computationally equivalent to TMs.)
- peter_m1 3mo ago
  There is such thing as a quantum Turing machine you know (Deutsch 1985).
  - spragl 3mo ago
    Yes I know. When I wrote Turing Machine, I was thinking about the classical determinstic Turing Machine. Im not super knowledgable about Quantum Turing Machines, but as far as I know, they dont do better than the classical deterministic Turing Machines when we are talking about computability.

by sgt101 3mo ago

gradys 3mo ago

It can be the case that both: - The physics of the universe can be completely modeled as computation, and - It's possible to pose undecidable problems about the way the universe unfolds This is intrinsic to the idea of undecidability even for Turing machines, e.g. "we equate computation with the functioning of Turing machines, but there are real processes executable in Turing machines that are undecidable".

sgt101 3mo ago
Of course, if our universe is undecidable it must be the case that computable processes can be executed within it, and it might be the case that all of the processes that are ever executed within it are computable... but it might be that some of the processes that are executed are not computable... because the machine may.. or may not?
- jerf 3mo ago
  I think there's an equivocation of "computable" going on here. Mathematicians talk about a lot of things like "uncomputable sequences" but that is usually making a statement about the sequence, not necessarily any individual member. The Busy Beaver sequence is uncomputable. You can, however, quite trivially compute BB(2), even in your head if you're a bit careful. You can set up individual elements of an uncomputable sequence in our universe, and you may be unable to state in advance what the system would do with anything less than simply letting it run and see what happens due to the complexity of the system, but being a member of an uncomputable sequence doesn't mean that you can't in fact set those things up and watch them run. The Universe doesn't throw an "UncomputableCircumstance" exception or anything. It just keeps advancing to the next state. Your inability to make certain statements about that next state or some future state is not its problem.
- chriswarbo 3mo ago
  There's no way to empirically spot an uncomputable process, since it would require infinitely-many observations. For example, if aliens claim their machine solves the halting problem, we could test it on millions of inputs whose halting/not-halting behaviour we already know; but even if it works for all of them, there's no way to know that it works for all inputs. For all we know, it might be a huge lookup table which happens to cover all of those inputs we tried.
  - peter_m1 3mo ago
    No, you can prove things hold in the abstract mathematically, don't need to resort to physical systems.
    - chriswarbo 3mo ago
      I was responding to this part: > if our universe is undecidable My point is, there would be no way to empirically test this; and therefore, it would make no observable difference, there would be no way to exploit/utilise such effects, etc. In essence: there's no way to tell the difference between a real halting oracle (which would imply an undecidable universe), versus a computable approximation which just-so-happens to be more powerful/sophisticated than the approximations we compare it against. Sure, we can prove that some abstract systems are undecidable and that others aren't. Yet that distinction is inherently unfalsifiable, and hence physically "useless".
- peter_m1 3mo ago
  Quantum mechanics is intrinsically probabilistic.
  - GoblinSlayer 3mo ago
    Deterministic processes can be modeled probabilistically and are computable, so existence of a probabilistic model doesn't say much about computability.
woopsn 3mo ago
A key thing about the undecidability problem wrt physics is preparation of the initial state. In math and computer science it is relatively straightforward to prepare such problems now (though this represented an enormous leap conceptually), but the "undecidability" of all physical problems relies on construction of materials that are clearly unconstructable - systems of infinite negentropy (eg Turing machines), infinite mass (the lattice), bespoke local interactions etc. Problems standing in the way of physics decidability are typically chaos, far from equilibrium mechanics, elementary SNR considerations and so forth, not problems of logic.
- peter_m1 3mo ago
  In physics we don't talk about decidability, but solvability.

Maxatar 3mo ago

>Recently it's been shown that there are real, physical processes which are undecidable I want to push back a bit on this claim along two dimensions. Imagine a physical Turing machine built out of atoms, gears, levers, and an electron parked on the read/write head and ask whether that electron ever crosses some fixed plane in space, which it does only when the machine enters its halt configuration. That's now a purely physical question about a trajectory (does this electron ever reach a certain target), yet answering it for the whole family of such machines is literally the halting problem, so there's a physical process that's undecidable. Your examples about physical processes being undecidable are all basically just this... there examples of using reflections of light, or the flow of liquid, etc... and demonstrating that these physical processes in principle are sufficient to model a universal Turing machine. And while it's fascinating that certain things you may not have expected can be used to model computation, it's misleading, or rather it's too strong of a claim to believe that there exist actual/real physical processes whose outcomes are undecidable. That's a subtle but very common misinterpretation of what undecidability is. Undecidability, whether in physics or computer science, only applies to the infinitely broad class of a problem as a whole, it never applies to a specific instance of a problem. So it can never be the case that there's a certain configuration of reflections for which it's undecidable whether a ray of light reaches a target. Nor can it be the case that for a specific lattice of atoms, it's undecidable whether it has a spectral gap or not. It can only be the case that for the problem as a whole where the parameter space is entirely unbounded, there is no single algorithm that can decide if a ray of light reaches a specific target for all possible arbitrary (and infinitely many) configurations. Once you fix a specific system, then the undecidability goes away. Not claiming that you are necessarily making this misconception, but I often see people misinterpret undecidability to mean that there exists a specific problem, like with specific inputs, where it's somehow impossible to know what the answer will be. Undecidability always requires an infinite family of instances, and it's a statement about the nonexistence of a single algorithm that correctly answers every instance in that family. It says nothing about any particular instance being unknowable/undecidable.

eth0up 3mo ago
If I am wrong, please pardon. I suspect I am. But was this comment edited by Claude? I ask specifically because it is well written, substantive, all which is expected here, but the "push back" part, to me, must be a) an artifact of Claude, either by osmotic assimilation (Which is happening to many innocent users) or b) Claude itself. Feel free to flag this comment if I get an answer. I do want to know.

plastic-enjoyer 3mo ago

> up to the point that many computer scientists now seem to equate computation with the functioning of the universe. Do you think that's a kind of tunnel vision? If the only thing you focus on is computation, you'll probably end up seeing computation everywhere - it became a way of seeing the world.

jerf 3mo ago
It is a common accusation. There's a somewhat famous quote I've seen a few times: "It's interesting to look back through history on this one. Each age has its pinnacle of technology, and each age uses that technology as a metaphor for nature, for the universe. In ancient Greece, the technological marvels were musical instruments and the ruler and compass. The Greek philosophers tried to build an entire cosmology from number, harmony, proportion, form, and so on — from mathematics, basically. Remember the music of the spheres? The Pythagoreans believed that nature was a manifestation of rational mathematics. Later on the pinnacle of technology was the clockwork. Newton wanted a clockwork universe, the entire universe as a gigantic clockwork mechanism, with all the parts interlocking and ticking over with infinite precision. Then in the 19th century along came steam power, and the universe was then depicted as an enormous heat engine, or thermodynamic machine, running down toward its heat death. Today the computer is the pinnacle of technology, so it's now fashionable to talk about nature as a computational process." Which seems to source from https://www.edge.org/conversation/paul_davies-time-loops https://www.edge.org/conversation/paul_davies-time-loops . While "computer" may give us impressions of something with "a CPU" and "RAM" and "a disk drive", it does at least seem plausible that the universe as computation is a plausible base level, though. Unlike "the music of the spheres", which to the extent that it made predictions of the world, it got them wrong in the most basic way, viewing it through a lens of computation allows us to put some quite subtle and interesting limits on things. "Computation" is a pretty flexible substrate; it is difficult to imagine how the proposition "the universe is a computation and subject to the limitations thereto" could be falsified, and if it could, it is difficult to imagine how we would be able to know it was so falsified. Nevertheless the math of computation allows us to say non-trivial things about the universe as a result; it is not a vacuous generalization, though it is certainly a loose one... being able to say yet more concrete things about the nature of the computation, such as "this is exactly how gravity works", has quite a bit more utility.

mondrian 3mo ago

Undecidability is a problem of answer-extraction from a process, it doesn’t preclude the process from executing deterministically. The universe could well be the live execution of a deterministic, even basic algorithm, with all kinds of questions about its execution being undecidable.

__rito__ 3mo ago

One sentence I heard somewhere wraps up the totality of computing: "If Mathematics is the 'what', Computer Science is the 'how'". This applies to each and everything.

athrowaway3z 3mo ago
If two people agreed on that statement, its entirely unclear if they agree with each other and if they found something profound in the first place. The imo much more foundational relationship not everybody is aware of is https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...

not-a-llm 3mo ago

> Recently it's been shown that there are real, physical processes which are undecidable According to the currently known laws of physics. Which we know are incomplete/incorrect in several places.

woopsn 3mo ago

The infinite lattice doesn't represent a "real" physical processes, it's just mathematical technique for closing a (fundamentally) quantized combinatorial sum over millions of interacting elements. The gap problem exists in the limit. For real systems the spectrum can be measured (in principle) by probing the ground state. The computational paradigm is incredibly general but only within what's apparently a pretty atypical thermodynamic regime (the ordered universe).

peter_m1 3mo ago
In this case quantum thermo.

nl 3mo ago

Undecidable isn't uncomputable. "Computable" can mean probabilistic, and classical computers can function over probability distributions just fine.

rudy6912 3mo ago
This is incorrect. An undecidable problem is one for which no algorithm can compute the correct result for every given instance. Probabilistic classical computation is irrelevant here.

spragl 3mo ago

Both P and NP are computable. That is, a Turing machine can compute both of them. Those quantum processes are interesting. Take the random numbers generated from radioactive decay. They are (after some cleanup) truly random. That is what we think. But how could we tell the difference from pseudorandom numbers, generated by a sufficiently advanced algorithm? We couldnt. So particles could simply be Turing Machines running sufficiently advanced algorithms that we cant reverse engineer. If so, quantum mechanics is computable even if we cant compute it. (Particles being TMs doesnt mean they are FAs with an infinite tape, but that they are computationally equivalent to TMs.)

peter_m1 3mo ago
There is such thing as a quantum Turing machine you know (Deutsch 1985).
- spragl 3mo ago
  Yes I know. When I wrote Turing Machine, I was thinking about the classical determinstic Turing Machine. Im not super knowledgable about Quantum Turing Machines, but as far as I know, they dont do better than the classical deterministic Turing Machines when we are talking about computability.