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.
>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.
I may be misremembering Godel's proof or misunderstanding your last paragraph, but I thought Godel's proof actually presented a specific undecidable statement. The hope then was that somehow undecidable statements could be cordoned off from decidable statements, and Turing's result showed that that wasn't possible. Perhaps that's what you mean by "the nonexistence of a single algorithm that correctly answers every instance in that family"?
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.
No Claude was not involved in any way in me writing it, and honestly it's kind of getting depressing how many comments are constantly questioning peoples use of LLMs.
Just a heads up, "I want to push back on" is an idiom Claude frequently uses.
It is depressing though, writing feels like it's in part becoming a game of outpacing the latest LLM's idiosyncrasies so we can signal authenticity, which perversely, is achieved through using an LLM enough so that you can become familiar with its flavor of communication.
This is what makes me sad about the AI age; many articles now have the same phrasing, the same analogies, the same quips, structure, the same wording; once you start to see it there's no going back.
I actually laughed quite a lot to begin with, GPT models saying things like "...might look like P, but is NP wearing a hat and a lab coat..." and "...is a haunted house disguised as a git repository..."; but alas when you've heard them a million times everywhere it really starts to bite.
- 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".
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?
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.
> 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.
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."
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.
For those that are unfamiliar, Tim Roughgarden is a phenomenal instructor, and has made significant contributions to the field of algorithmic game theory, which has strong connections to a lot of the work he appears to be doing here. I highly recommend his excellent introductory lectures on the subject, especially if you're interested in pursuing his ideas here more rigorously: https://www.youtube.com/watch?v=TM_QFmQU_VA&list=PLEGCF-WLh2...
His website also hosts a bunch more work as well as various lecture notes and exercises: https://timroughgarden.org/
Tim's lectures helped me a lot during my PhD when I was getting up to speed on this subject, and some of the more nuanced ways that computer scientists have worked with these broad algorithmic problems.
What even is computation? State-based inference. But intelligence itself does not rely on computation, only its biological counterweight seems to and only in certain situations. If Computation is a "Universal Concept" then there are at least 4 or 5 more "Universal Concepts" analogous to intuition and spontaneity.
Something has always nagged me about the halting problem, might be my mis-understanding of the problem space but;
- You have a piece of software
- That software does in memory compute only
- The software does not touch any peripherals, networking, or any other external source which introduce unpredictability (x)
I'm convinced that somehow this can be solved/proven whether the execution will halt or not.
(x) The second you touch any external peripherals or networking, you're effectively asking the question of "If I phone my friend, will they pick up the phone?" -> to which the only answer is, "They'll pick it up, only if they pick it up/are there". You can't answer that question without trying it.
Am I missing the point? I'm sure you can introduce other edges even in the limited model above, e.g. where a memory stick stops responding or something; but all in if you have reliable kit and don't touch anything external, why can't this be solved?
Imagine a program that generates the digits of pi, one after the other and stops when it is finished. A general purpose program analysing this program to decide if it stops or not would have to know about pi. And about every other possible algorithm.
Thank you internet stranger, for introducing me to hard-maths drugs; am hooked!! \o/
I love the idea of this. So the BB problems are individual iterations of the halting problem right? To truly solve the problem one would have to come up with a program which would operate on all possible BB numbers?
This truly leads into "computation"; when we're dealing with known quantities, yes, we can "solve" the halting problem. The second you move into "we don't know the answer yet", the can of worms opens. Thank you.
There remain undecidable problems even with finite memory/state space.
Linear bounded automata (LBA) the halting problem is decidable. But many properties of LBA are undecidable:
Emptiness: Does an LBA reject all possible inputs?
Universality: Does an LBA accept all possible inputs over its alphabet?
Equivalent: Do two LBA accept the same language?
Finiteness: Does an LBA accept a finite number of strings.
Computation is the study of infinity. That is how I like to think about it. It doesn't seem that way when you're building a website (well, in some ways because it's not at that point), but every algorithm, data structure, etc is an investigation into a certain part of infinity. Think of the way in which we generally categorize algorithms (Big-O notation)... that's just characterizing infinity.
If the memory is bounded then your software is a simple finite automaton, and can be decided in finite time. The issue is with unbounded memory. The issue with the halting problem is a simple characteristic of infinity. This is actually what people are noticing when they say that computation is a fundamental part of the universe. They are correct! The universe deals with infinitisemals all the time. As humans, we have only discovered ways of dealing with certain classes of infinitesemals (calculus). The others remain beyond our ability to characterize. Indeed, some have been proven to be uncharacterizable.
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.
>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.
I may be misremembering Godel's proof or misunderstanding your last paragraph, but I thought Godel's proof actually presented a specific undecidable statement. The hope then was that somehow undecidable statements could be cordoned off from decidable statements, and Turing's result showed that that wasn't possible. Perhaps that's what you mean by "the nonexistence of a single algorithm that correctly answers every instance in that family"?
I may have been making this claim, I need to think about this for a while and re read what you have written.
This is very helpful though, thank you.
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.
No Claude was not involved in any way in me writing it, and honestly it's kind of getting depressing how many comments are constantly questioning peoples use of LLMs.
Just a heads up, "I want to push back on" is an idiom Claude frequently uses.
It is depressing though, writing feels like it's in part becoming a game of outpacing the latest LLM's idiosyncrasies so we can signal authenticity, which perversely, is achieved through using an LLM enough so that you can become familiar with its flavor of communication.
This is what makes me sad about the AI age; many articles now have the same phrasing, the same analogies, the same quips, structure, the same wording; once you start to see it there's no going back.
I actually laughed quite a lot to begin with, GPT models saying things like "...might look like P, but is NP wearing a hat and a lab coat..." and "...is a haunted house disguised as a git repository..."; but alas when you've heard them a million times everywhere it really starts to bite.
Yeah, that's why I invited the flag. But do not overlook how fucking depressing the endless LLM generated comments actually are too.
My apologies, and I do appreciate your reply.
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".
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?
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.
> 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.
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 .
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.
For those that are unfamiliar, Tim Roughgarden is a phenomenal instructor, and has made significant contributions to the field of algorithmic game theory, which has strong connections to a lot of the work he appears to be doing here. I highly recommend his excellent introductory lectures on the subject, especially if you're interested in pursuing his ideas here more rigorously: https://www.youtube.com/watch?v=TM_QFmQU_VA&list=PLEGCF-WLh2...
His website also hosts a bunch more work as well as various lecture notes and exercises: https://timroughgarden.org/
Tim's lectures helped me a lot during my PhD when I was getting up to speed on this subject, and some of the more nuanced ways that computer scientists have worked with these broad algorithmic problems.
I really do think matter wants to be sentient, being sentient is natural. Why i think that exactly, i'm not sure why, it just seems intuitive.
What even is computation? State-based inference. But intelligence itself does not rely on computation, only its biological counterweight seems to and only in certain situations. If Computation is a "Universal Concept" then there are at least 4 or 5 more "Universal Concepts" analogous to intuition and spontaneity.
Something has always nagged me about the halting problem, might be my mis-understanding of the problem space but;
- You have a piece of software
- That software does in memory compute only
- The software does not touch any peripherals, networking, or any other external source which introduce unpredictability (x)
I'm convinced that somehow this can be solved/proven whether the execution will halt or not.
(x) The second you touch any external peripherals or networking, you're effectively asking the question of "If I phone my friend, will they pick up the phone?" -> to which the only answer is, "They'll pick it up, only if they pick it up/are there". You can't answer that question without trying it.
Am I missing the point? I'm sure you can introduce other edges even in the limited model above, e.g. where a memory stick stops responding or something; but all in if you have reliable kit and don't touch anything external, why can't this be solved?
Imagine a program that generates the digits of pi, one after the other and stops when it is finished. A general purpose program analysing this program to decide if it stops or not would have to know about pi. And about every other possible algorithm.
This is a brilliant explanation thank you.
Related: the Busy Beaver problem https://news.ycombinator.com/item?id=40857041
Thank you internet stranger, for introducing me to hard-maths drugs; am hooked!! \o/
I love the idea of this. So the BB problems are individual iterations of the halting problem right? To truly solve the problem one would have to come up with a program which would operate on all possible BB numbers?
It can be solved if the memory is bounded. But unbounded memory comes with undecidable problems.
This truly leads into "computation"; when we're dealing with known quantities, yes, we can "solve" the halting problem. The second you move into "we don't know the answer yet", the can of worms opens. Thank you.
There remain undecidable problems even with finite memory/state space.
Linear bounded automata (LBA) the halting problem is decidable. But many properties of LBA are undecidable:
Emptiness: Does an LBA reject all possible inputs? Universality: Does an LBA accept all possible inputs over its alphabet? Equivalent: Do two LBA accept the same language? Finiteness: Does an LBA accept a finite number of strings.
Computation is the study of infinity. That is how I like to think about it. It doesn't seem that way when you're building a website (well, in some ways because it's not at that point), but every algorithm, data structure, etc is an investigation into a certain part of infinity. Think of the way in which we generally categorize algorithms (Big-O notation)... that's just characterizing infinity.
If the memory is bounded then your software is a simple finite automaton, and can be decided in finite time. The issue is with unbounded memory. The issue with the halting problem is a simple characteristic of infinity. This is actually what people are noticing when they say that computation is a fundamental part of the universe. They are correct! The universe deals with infinitisemals all the time. As humans, we have only discovered ways of dealing with certain classes of infinitesemals (calculus). The others remain beyond our ability to characterize. Indeed, some have been proven to be uncharacterizable.
Ahhh thank you it's effectively the known-vs-unknown space;
- How long does it take to get from A to B? => Easy if you know where A and B are, and what mode of transport you're taking to get there.
- How long does it take to get from A to _somewhere_ => As long as it takes!!
Related:
Ergo: Long Form Philosophy Lectures
https://news.ycombinator.com/item?id=48840497