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