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.
- 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?
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?
Our world appeared computable, but it isn't, even if P=NP.
- 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".
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.
This is very helpful though, thank you.
Feel free to flag this comment if I get an answer. I do want to know.
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.
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.
My apologies, and I do appreciate your reply.
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.