5 ms·

"This to me is a strong "intuitive" argument for why the halting problem is undecidable: a halt detector can be trivially repurposed as a program optimizer / th

by ummonk 1y ago

"This to me is a strong "intuitive" argument for why the halting problem is undecidable: a halt detector can be trivially repurposed as a program optimizer / theorem-prover / bcrypt cracker / chess engine. It's too powerful, so we should expect it to be impossible." I don't buy this. Bcrypt cracking and solving chess is easy already if you don't care about runtime complexity (both have rather trivial finite -- albeit exponential -- runtime algorithms), and it wouldn't be any easier to transform them into halting problems.

jonahx 1y ago
What do you not buy? He's saying it could be used to do anything for free. He gave four examples. The first two don't have general solutions, and never will. You don't like the last 2 examples because we have algorithms for them, ok. It doesn't undermine the argument. And in any case both things were developed with effort and ingenuity... they weren't spit out of a halting problem calculator.
- cvoss 1y ago
  Having a decision algorithm does not make a computation free. It may take exponential time in the input size, doubly exponential time, some time involving Graham's number, ... etc. It may also take up an unreasonable amount of space. Indeed, some problems have such complex algorithms that you should expect the universe to end before the answer is determined and/or the computing device is doomed to collapse into a black hole, making the answer irretrievable. So the blog post's claims that a hypothetical halting algorithm would solve anything "overnight" are exaggerated and naive.
  - jonahx 1y ago
    "Free" in the sense of thought, cleverness, insight. You have an "everything" calculator. That is the sense in which it might be intuitive that it couldn't exist. > So the blog post's claims that a hypothetical halting algorithm would solve anything "overnight" are exaggerated and naive. I agree "overnight" is misleading in this context. However, I am fairly sure the author is aware of the point you are making.
    - Dylan16807 1y ago
      > "Free" in the sense of thought, cleverness, insight. You have an "everything" calculator. That is the sense in which it might be intuitive that it couldn't exist. Right. But brute force solvers for bcrypt and chess are already "free" in the sense of thought, cleverness, insight. We already have the "everything" algorithm: iterate through all possible solutions in O(2^n) time and pick the best one. A halting solver gains us nothing in these scenarios. (The code for scoring a solution is the same code that would need to go into the halting solver. For bcrypt it's checking if the input matches, for chess it's the number of turns until checkmate.)
      - jonahx 1y ago
        Yeah, I thought I already addressed that above. Can we do the same for a theorem prover? For proofs of some fixed finite length, I think the answer is yes, but without that constraint the answer is no. Whereas with a halting detector we could. It still seems to me your complaint (and the other poster's) are just about these specific examples rather than general argument Hillel is making. Please clarify if that's not the case, and why.
        ummonk 1y ago
        The complaint is that Hillel is providing an intuitive explanation but that intuition is clearly faulty, as demonstrated by two of the examples he gave. P.S., you can run that proof finding algorithm (iterate through every candidate proof one by one and check for validity) for proofs of finite length in general, not just some fixed finite length. Where the halting oracle comes in is that you can use it to check whether the proof finding algorithm will ever halt, and thereby find out whether the theorem is provable or not.
        jonahx 1y ago
        > for proofs of finite length in general, not just some fixed finite length. For a brute force proof finder, for your program to be guaranteed to finish in theory, you have to pick a length. So it is fixed. Ofc you can choose whatever length you want. But you don't have that constraint with the halting oracle. Perhaps we're saying the same thing?

by ummonk 1y ago

jonahx 1y ago

What do you not buy? He's saying it could be used to do anything for free. He gave four examples. The first two don't have general solutions, and never will. You don't like the last 2 examples because we have algorithms for them, ok. It doesn't undermine the argument. And in any case both things were developed with effort and ingenuity... they weren't spit out of a halting problem calculator.

cvoss 1y ago
Having a decision algorithm does not make a computation free. It may take exponential time in the input size, doubly exponential time, some time involving Graham's number, ... etc. It may also take up an unreasonable amount of space. Indeed, some problems have such complex algorithms that you should expect the universe to end before the answer is determined and/or the computing device is doomed to collapse into a black hole, making the answer irretrievable. So the blog post's claims that a hypothetical halting algorithm would solve anything "overnight" are exaggerated and naive.
- jonahx 1y ago
  "Free" in the sense of thought, cleverness, insight. You have an "everything" calculator. That is the sense in which it might be intuitive that it couldn't exist. > So the blog post's claims that a hypothetical halting algorithm would solve anything "overnight" are exaggerated and naive. I agree "overnight" is misleading in this context. However, I am fairly sure the author is aware of the point you are making.
  - Dylan16807 1y ago
    > "Free" in the sense of thought, cleverness, insight. You have an "everything" calculator. That is the sense in which it might be intuitive that it couldn't exist. Right. But brute force solvers for bcrypt and chess are already "free" in the sense of thought, cleverness, insight. We already have the "everything" algorithm: iterate through all possible solutions in O(2^n) time and pick the best one. A halting solver gains us nothing in these scenarios. (The code for scoring a solution is the same code that would need to go into the halting solver. For bcrypt it's checking if the input matches, for chess it's the number of turns until checkmate.)
    - jonahx 1y ago
      Yeah, I thought I already addressed that above. Can we do the same for a theorem prover? For proofs of some fixed finite length, I think the answer is yes, but without that constraint the answer is no. Whereas with a halting detector we could. It still seems to me your complaint (and the other poster's) are just about these specific examples rather than general argument Hillel is making. Please clarify if that's not the case, and why.
      - ummonk 1y ago
        The complaint is that Hillel is providing an intuitive explanation but that intuition is clearly faulty, as demonstrated by two of the examples he gave. P.S., you can run that proof finding algorithm (iterate through every candidate proof one by one and check for validity) for proofs of finite length in general, not just some fixed finite length. Where the halting oracle comes in is that you can use it to check whether the proof finding algorithm will ever halt, and thereby find out whether the theorem is provable or not.
        jonahx 1y ago
        > for proofs of finite length in general, not just some fixed finite length. For a brute force proof finder, for your program to be guaranteed to finish in theory, you have to pick a length. So it is fixed. Ofc you can choose whatever length you want. But you don't have that constraint with the halting oracle. Perhaps we're saying the same thing?