[Maxatar]

>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.

[sgt101]

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.

[joelshep]

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"?

[justinpombrio]

There's no such thing as an undecidable statement. A single statement can't be undecidable. Undecidability is a property of a class of statements.

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.

[scapp]

That's a different meaning of the word "undecidable". You're talking about undecidable problems [1]. The meaning in Gödel's incompleteness theorem is different and is a synonym with independent [2].

[1] https://en.wikipedia.org/wiki/Undecidable_problem

[2] https://en.wikipedia.org/wiki/Independence_(mathematical_log...

[masfuerte]

> 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".

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.

https://en.wikipedia.org/wiki/Collatz_conjecture

[Twey]

And yet there is a correct algorithm — it's either the const yes algorithm or the const no algorithm.

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.

[masfuerte]

Cheers, I had missed the nuance.

[Twey]

In constructive mathematics I think you'd be right: to call a problem decidable would require you to produce the algorithm that decides it, so you couldn't call the Collatz conjecture decidable (nor could you call it undecidable!). But the usual definition of decidability is classical.

This is slightly bizarre now I think about it: the definition of decidability allows the algorithm selection to be undecidable!

[GoblinSlayer]

It's a gap between physics and mathematics. Undecidable statements exist mathematically, but don't exist physically: mathematics and physics have different concepts of existence. Ironically, even mathematical universe hypothesis deliberately limits mathematics-as-physics to specifically resemble physics of a spontaneous material world, and this limitation is just an axiom.

[SideQuark]

> … so there's a physical process that's undecidable.

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.

[wasabi991011]

Agreed, and I'll add: the universe is sufficiently messy and complex that some of the claimed undecidability results may never occur in practice.

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)

[peter_m1]

A quantum Turing machine would be needed to simulate a truly quantum process. Stochasticity exists in classical systems, but that's an entirely different type of randomness.

[Twey]

Quantum computation is not super-Turing: anything you could solve with a quantum Turing machine you could also solve with a classical Turing machine, albeit sometimes a lot slower. We know how to emulate quantum systems in classical systems.

[pocksuppet]

Quantum computers can be simulated on classical computers, but it takes exponential time (completely impractical).

[jesuslop]

I think Gödel undecidable sentence is always relative to a formal system (the title of the paper spoke about systems in the expressive power rank of Russell's Principia, of which he gives one particular example assuming it shows how his methods apply to the whole family of systems), but now Hilbert problem #6 still stands for the lack of a comprehensive axiomatization of Physics, as its modern heir the mass-gap millennium problem, that still also lingers, so we don't have a controllable notion of naked/absolute undecidability for physical phenomena or for arbitrary assertions unbound by explicit logic rules in general.

[peter_m1]

Also, correct me if I'm wrong, the mass gap problem involves quantum physics, not classical, so the underlying math/logic is different.

[jesuslop]

mmh I'd don't say that much, I think the logic and math foundations is common in both classic and quantum theories, only content changing, so you would say "import mathlib" from both classic-phys.lean and quant-phys.lean if writing Lean proof assistant code (I am guessing the "import" command). Concepts from linear algebra as eigendecomposition, to say something, will be used in both applications.

[eth0up]

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.

[Maxatar]

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.

[helterskelter]

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.

[jojogeo]

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.

[dbtc]

The other day, while reading, my AI-dar triggered on some typical claudisms, but then I remembered I was reading from a paper book that was printed in 1997...

[eth0up]

Unsettling. I hereby commit to self doubt on this matter exclusively. I will leave this fight to others.

What was the book in 1997? That's about the time of my first UAP sighting.

[eth0up]

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.

[RandomLensman]

How to build a Turing machine to tell which one of ten atoms of a radioactive element decays next?

[peter_m1]

That would be a quantum Turing Machine as radioactivity is a quantum process.

[RandomLensman]

How would that work as current understanding from quantum theory is that we cannot predict which atom decays next? Is there a quantum algorithm that can do that?

[GoblinSlayer]

The decay process is calculated as

sqrt(1-exp(-t/T))|1> + sqrt(exp(-t/T))|0>

[RandomLensman]

How do you use that to predict which atom decays next?

[GoblinSlayer]

The decayed state exists, it's the second term sqrt(exp(-t/T))|0>