Our world appeared computable, but it isn't, even if P=NP.
Our world appeared computable, but it isn't, even if P=NP.
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.
Feel free to flag this comment if I get an answer. I do want to know.
My apologies, and I do appreciate your reply.
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.
What was the book in 1997? That's about the time of my first UAP sighting.
This is very helpful though, thank you.
For example, you can ask whether a Java program, run with infinite memory, will eventually halt. For any particular Java program, there's obviously an algorithm that says whether it halts or not. The algorithm is a single statement, which says either "yes" or "no". Might be hard to figure out which is the correct algorithm, but the Java program is fixed so the algorithm is definitely one of the two.
However, there is no algorithm which can take an arbitrary Java program as input and determine whether it will halt. It's about the class of all possible programs.
[1] https://en.wikipedia.org/wiki/Undecidable_problem
[2] https://en.wikipedia.org/wiki/Independence_(mathematical_log...
This isn't true.
In general, if a program hasn't halted yet you don't know if it will.
In particular, consider the Collatz conjecture. You can't even tell if your Java implementation of it will halt for a particular input, until it does.
We don't _know_ which algorithm it is, but that's not relevant to the definition of undecidability, which only requires that the algorithm exist.
This is slightly bizarre now I think about it: the definition of decidability allows the algorithm selection to be undecidable!
For your Turing machine example: even if we built such a machine, it would never truly be giving an answer to the halting problem, because any stray cosmic particle could excite the electron and cause it to cross whatever plane.
For a more realistic example: the ground state of an molecule is a physically relevant quantity, and in theory any molecule alone should lose energy and attain it's ground state, even if finding the ground state electronic configuration is undecidable. But in reality, no molecule is ever truly isolated and so would never actually be guaranteed to enter it's ground state (or if it were truly isolated, it would not be observed at all rendering the question moot)
No, since you cannot physically build a Turing Machine. A Turing machine requires infinite tape. Any physically realizable machine doesn’t have that, so has finite states, so is decidable: enumerate the states in finite time - it halts or repeats, so all programs on a finite state machine are decidable.
Your example is not an undecudable physical process.
Godel things also don’t apply: Godel theorems are about proof of this or that from within the same system. In logic one can prove such things from an outside system, then construct towers, avoiding Godel theorems. Godel theorems also require a model of integers including multiplication (without multiplication, such systems were proven complete and decidable). However the universe does not contain a model of integers, as the physical universe is not unbounded: relativity places a finite limit in spacetime on what can interact.
Mixing math as reality fails at these requirements.
sqrt(1-exp(-t/T))|1> + sqrt(exp(-t/T))|0>
If you want to claim that we could predict which specific atom decays next, I'd really like to see a lot more explaintion and exposition as it would upend current understanding.
But at least we agree there is nothing we can predict.
sqrt(1-exp(-t/T))|1> + sqrt(exp(-t/T))|0>
- 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".
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.
> 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".
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.)
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.
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'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.
"If Mathematics is the 'what', Computer Science is the 'how'".
This applies to each and everything.
The imo much more foundational relationship not everybody is aware of is https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...
"Computable" can mean probabilistic, and classical computers can function over probability distributions just fine.
According to the currently known laws of physics. Which we know are incomplete/incorrect in several places.