4 ms·

I think we have a slight disagreement. My machine is _not_ a Turing machine. Given any program that can only take countably infinite steps my machine halts.

by evanb 3y ago

I think we have a slight disagreement. My machine is _not_ a Turing machine. Given any program that can only take countably infinite steps my machine halts. If you like, you can think of it as an oracle for the Halting Problem. But the fact that it's _not_ a Turing machine is what saves it. What makes it _not_ a Turing machine? It violates one of the assumptions! Essentially, it can reach the transfinite ωth step in a finite amount of time. The assumption that Turing machines can't do that is well-hidden, but essentially it enters every time someone says "and then". "It reads the tape _and then_ updates its state _and then_ moves the head _and then_ etc." You never actually reach the ωth step if each step takes a finite amount of time [edit: an amount of time bounded from below by any fixed positive amount of time]. However, I agree that whatever class this kind of machine belongs to has its own Halting Problem. It's just not the same Halting Problem that our beloved Turing Machines face. Why is the seemingly-relevant question the Normal™ one and not this worse one? That is a question about physics, and not mathematics.

cvoss 3y ago
Ah, interesting, I missed that detail. Yes, you may already be aware that there's a whole hierarchy of undecidable problems, where if you have an oracle for undecidable problem X, you may be able to decide an otherwise undecidable problem Y, but still not Z, etc.
- evanb 3y ago
  Indeed; it's related to the whole tower of large numbers etc. There's no escaping the Halting Problem. It's just a matter of which level of halting "bites us". Anyway, I hope I've convinced you that the appeal to physics is inside "Turing Machines are a reasonable model of how computations work." It's so weird to think about other more powerful machines exactly because they go against deeply-ingrained intuition about what the world is really like. Moreover, physics really seems to prevent you from doing any "sick" by monkeying around either on the quantum or gravitational side. Did the laws of physics have to do that? I have no idea. Perhaps someday we'll wind up elevating the (extended, quantum) Church-Turing thesis to a physical principle and rule out classes of physical law because they'd lead to violations of computational difficulty, in much the same way we rule out classes of physical law because they lead to violations of conservation of energy.

by evanb 3y ago

cvoss 3y ago

Ah, interesting, I missed that detail. Yes, you may already be aware that there's a whole hierarchy of undecidable problems, where if you have an oracle for undecidable problem X, you may be able to decide an otherwise undecidable problem Y, but still not Z, etc.

evanb 3y ago
Indeed; it's related to the whole tower of large numbers etc. There's no escaping the Halting Problem. It's just a matter of which level of halting "bites us". Anyway, I hope I've convinced you that the appeal to physics is inside "Turing Machines are a reasonable model of how computations work." It's so weird to think about other more powerful machines exactly because they go against deeply-ingrained intuition about what the world is really like. Moreover, physics really seems to prevent you from doing any "sick" by monkeying around either on the quantum or gravitational side. Did the laws of physics have to do that? I have no idea. Perhaps someday we'll wind up elevating the (extended, quantum) Church-Turing thesis to a physical principle and rule out classes of physical law because they'd lead to violations of computational difficulty, in much the same way we rule out classes of physical law because they lead to violations of conservation of energy.