3 ms·

Along the same lines, the "Math is limited by math" really contains a hidden physical assumption, which is this: the (quantum, extended) Church-Turing thesis is

by evanb 3y ago

Along the same lines, the "Math is limited by math" really contains a hidden physical assumption, which is this: the (quantum, extended) Church-Turing thesis is an assumption about physics. The (classical version of the) argument goes like this: Suppose you want to solve the Halting problem for Turing problems that can execute one step per second. If I have a machine that takes 1 second for the zeroeth step step, and 0.5 seconds for the first step, and 0.25 seconds for the second step, and so on, I can just run the "normal" machines' entire infinite history in 2 seconds. If I want to check if the twin prime conjecture is true, I'll just check every integer. If I want to check if an arbitrary normal machine halts, I just run it on my unusual machine. As far as I can tell all of the arguments against the reasonableness of such an unusual machine rely on some physical argument. For example, computational speed requires energy, an increasing speed would require an unbounded amount of energy, which is both impractical and would also presumably collapse into a black hole. So, I guess I should be careful a bit. The Halting problem is a perfectly well defined mathematical question and it has a definite answer. But why is it an interesting question at all? That's a question about the nature of the world.

cvoss 3y ago
Partially agree, partially disagree. Yes. Absolutely, Church-Turing is a claim not just about math and computation but about physics too, because any and all math "runs on" hardware or wetware or some other system that obeys the laws of physics. But I disagree with your assessment of the halting problem. It is not possible to have, even in theory, a machine that solves it. This is from the classic proof of undecidability of the problem, which involves, just as you have, supposing the existence of a machine to oracularly answer the question. You can then construct a logical paradox using a machine that enters an infinite loop if its input is a halting machine, and halts if its input is a non-halting machine, and simply run this machine on itself. It cannot both halt and not halt, so you have to back up and invalidate the assumption that the halting-problem machine could exist. No appeal to physics is required for this proof. Ok, so now the fun part: Let this mathematical impossibility speak into the domain physics by way of Church-Turing. Your accelerating machine is not only mathematically impossible, it _must_ also be physically impossible, else we have to throw out Church-Turing. We deduce that the laws of physics are somehow constrained so as to make it impossible.
- 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

Partially agree, partially disagree. Yes. Absolutely, Church-Turing is a claim not just about math and computation but about physics too, because any and all math "runs on" hardware or wetware or some other system that obeys the laws of physics. But I disagree with your assessment of the halting problem. It is not possible to have, even in theory, a machine that solves it. This is from the classic proof of undecidability of the problem, which involves, just as you have, supposing the existence of a machine to oracularly answer the question. You can then construct a logical paradox using a machine that enters an infinite loop if its input is a halting machine, and halts if its input is a non-halting machine, and simply run this machine on itself. It cannot both halt and not halt, so you have to back up and invalidate the assumption that the halting-problem machine could exist. No appeal to physics is required for this proof. Ok, so now the fun part: Let this mathematical impossibility speak into the domain physics by way of Church-Turing. Your accelerating machine is not only mathematically impossible, it _must_ also be physically impossible, else we have to throw out Church-Turing. We deduce that the laws of physics are somehow constrained so as to make it impossible.

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.