You're conflating computability with computational complexity; that seems to the source of most of your confusion. I don't remember the name of the complexity-

You're conflating computability with computational complexity; that seems to the source of most of your confusion. I don't remember the name of the complexity-theory analog of the Church-Turing thesis; but it's an open problem what types of computers physics can support the existence of, how they relate to classical Turing machines in complexity theory. See for example: quantum complexity theory. About halting: there is provably no way to verify an oracle for the Halting Problem, even if you had one. You can't even ask a hypercomputer to write a proof for you: in general there exist no finite-length proofs.