Hacker News Reader

Comment by schoen | Hacker News Reader

(Not Scott!)

The Halting Problem's unsolvability is proven in a fully abstract mathematical way, and so the truth of this result is as logically necessary as the truth of other mathematical theorems. It doesn't refer to anything about physics. So it seems like this question might be better bifurcated into

Why do we live in a world in which Turing machines are a good model for what computations we can physically perform?

and

Would the laws of mathematics be the same in any universe?

Each of these questions might then be a good one to pose to Scott.

View on HN

Yup. :-)

Or better yet, we could bifurcate into:

(1) Why is our universe apparently unable to solve the halting problem for Turing machines?

The answer, presumably, is a combination of the physical Church-Turing Thesis (specifically, the apparent impossibility of Turing-uncomputable processes in our world), with Church and Turing and Post's theorem on the unsolvability of the halting problem.

Of course one could then push back and ask why the Church-Turing Thesis should be true of our world: i.e., why shouldn't there be physical "hypercomputers"? That's an enormous question, but my old survey "NP-Complete Problems and Physical Reality" contains some thoughts about it: https://arxiv.org/abs/quant-ph/0502072

And then there's:

(2) Why should we live in a universe that's unable to solve "its own" halting problem?

I.e., even if super-Turing computers were physically possible, we could presumably formulate a halting problem for those computers, which would then require a still more powerful computer to solve (a super-duper-Turing computer?), and so on forever. This is because we could simply repeat Turing's diagonalization argument at a higher-level up -- given very minimal properties of computation, such as the ability to feed one program to another program as code, the ability of one program to emulate another one, and the ability to compute the NOT function. Once you have those properties, the inability of any given computational model (even a super-Turing model) to solve its own halting problem is just a matter of logic, as schoen said.

Once you have those properties, the inability of any given computational model (even a super-Turing model) to solve its own halting problem is just a matter of logic, as schoen said.

This seems to assume that logic provides some form of undeniable truth but I am not sure that this is the case. Sure, every system of logic is hopefully consistent and you can use it to derive true statements within it by simply playing a game of symbol manipulation, and in that sense the system is a source of undeniable truth. But when we are using logic to reason about the real world, we need the real world and the logic we use to be compatible. Classical logic works great in the classical world but quantum mechanics seems to push it to its limits. You can certainly still use it if you are careful, but it seems no longer a really good fit once you no longer have your particles either here or there, either spin up or spin down.

So logic seems much more like physics if you want to apply it to the real world instead of just using it for the fun of symbol manipulation. There are systems of logic that are useful to describe the world and there are ones that are less useful or probably even ones yielding wrong conclusions about the real world. Long story short, I am not sure that we can conclude that there will be halting problems for super-Turing machines because we can not be sure what kind of logic would be adequate to describe those machines. Not that I consider this a likely scenario or whatever, I just think we have to be more careful when saying something is just a matter of logic.

Who said anything about physics? I was thinking about axioms/logic systems and finitism.

> Who said anything about physics?

You did. You asked about why the universe we live in has a particular property. That's a question about physics.

Well I obviously don't think so, and all you've done is state the opposite claim.

What do you think the word "physics" means?

Good question. I'm willing to bet you have a different idea to me. How about you tell me what you think. I'm a professional physicist with a relatively mainstream view. But i couldn't give a comprehensive definition in the time I'm willing to take to write this comment. But i promise to write one if you do.

> How about you tell me what you think.

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

> I'm a professional physicist

You're behaving more like a troll than a physicist. What is your field of expertise?

Reply on news.ycombinator.com