6 ms·

Any deterministic system with a finite number of states is decidable, in the halting problem sense. Either it halts or repeats a state. The halting problem only

Any deterministic system with a finite number of states is decidable, in the halting problem sense. Either it halts or repeats a state. The halting problem only applies for infinite memory. Now, there are finite state systems where the halting problem is arbitrarily hard. But that's not undecidability. That's complexity. That's a problem in the space where P=NP lives. The article does not make this distinction, and it's important.

ummonk 1y ago
Yes, the article is clearly confused about the concepts, given its mention of bcrypt cracking and chess engines.
- dmurray 1y ago
  Yes, I thought the article was really good until it got to that point. > 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.) A Turing machine can be trivially repurposed as a bcrypt cracker or chess engine (for the same definition of trivial the author is using), so if it's not intuitive that a computer can do this, then your intuition is wrong. Program optimizers and theorem provers also exist, of course, but in those cases the problems really are undecidable so no Turing machine is guaranteed to work on any given program or theorem.
  - bubblyworld 1y ago
    A solution to the Halting problem can be repurposed as a general-purpose theorem prover. The author is correct. You simply write a program that searches all possible valid proofs till it finds the one you are looking for (or maybe doesn't and runs forever). Then you check whether it halts with your Halting solution - if that returns true, you know that a proof exists, otherwise you know that one doesn't. In other words, you can use undecidability of first-order logic to prove undecidability of the Halting problem if you like, although it's a bit of a chicken-egg thing historically (I believe).
    - dmurray 1y ago
      I edited the last part; I meant that the Turing machine from my second paragraph can't do those things, though the Halting machine can.
      - bubblyworld 1y ago
        Right, yeah that makes sense. But I think the author understands that very well.
        dmurray 1y ago
        Of course he must. But the fact that we're arguing about it (and there's another thread with the same conversation) says that at least, the intent of this part wasn't clear.
    - Maxatar 1y ago
      >A solution to the Halting problem can be repurposed as a general-purpose theorem prover. The author is correct. You simply write a program that searches all possible valid proofs till it finds the one you are looking for (or maybe doesn't and runs forever). The author is not correct and it's a common misconception. Simple question for you... let's say I give you a magical black box that can solve the halting problem. Now please use it to prove or disprove the continuum hypothesis (within ZFC). Hopefully you'll come back to me and say the black box shows that the continuum hypothesis can not be proved or disproved (in ZFC). Okay we agree so far, but note that we have established that having a solution to the halting problem can not actually be repurposed as a general purpose theorem prover, since no such proof exists in the first place. Okay you might counter by saying that a solution to the halting problem can be repurposed as a general purpose theorem prover for propositions that either have a proof or don't have a proof, ignore those pesky propositions that are neither provable or unprovable... But then the solution to the halting problem doesn't get you anything... if you're dealing with a proposition that either has a proof or a proof of its negation, you don't need a solution to the halting problem to find it, you are guaranteed to find it eventually by definition. The claim that a black box that solves the halting problem can be used as a general purpose theorem prover is simply untrue and confuses certain concepts together. At best you can claim it gives you a restricted theorem classifier.
bubblyworld 1y ago
I don't think this is an important distinction. The point of Turing machines is that you can ask questions like "can all instances of this problem be solved uniformly, and how relatively expensive is it?". This requires infinite memory in a formal sense, because instances of (most) problems can be arbitrarily large. Yes, if you ask the same question with a fixed (finite) memory restriction on everything, the answer is uninteresting. To me, this is... uninteresting. It tells you nothing about the underlying logical structure of your problem, which is what mathematicians are really trying to get at! (first and foremost Turing machines are a tool for analysing problems mathematically, not a model of your laptop) Also note that "states" in your sense are not the same as "states" in a Turing machine (which are just one of the inputs to the transition function). There are Turing machines with less than ten thousand states whose behaviour is undecidable in ZFC (https://arxiv.org/abs/1605.04343 https://arxiv.org/abs/1605.04343).
- Ukv 1y ago
  > Yes, if you ask the same question with a fixed (finite) memory restriction on everything, the answer is uninteresting. To me, this is... uninteresting. It tells you nothing about the underlying logical structure of your problem, which is what mathematicians are really trying to get at! > (first and foremost Turing machines are a tool for analysing problems mathematically, not a model of your laptop) I think what makes Animats's distinction worth stressing is that a lot of people miss this and fall into the trap of making false/misleading claims about the impact of the halting problem on actual computers/software. For instance, claiming that the halting problem proves there are problems humans can solve that computers fundamentally can't, giving "the halting problem makes this impossible" as reason against adding a halt/loop detector to a chip emulator, making all sorts of weird claims about AI[0][1], or arguably even this author's claim that a halt detector would make bcrypt cracking trivial. [0]: https://mindmatters.ai/2025/02/agi-the-halting-problem-and-the-human-mind/ https://mindmatters.ai/2025/02/agi-the-halting-problem-and-t... [1]: https://arxiv.org/pdf/2407.16890 https://arxiv.org/pdf/2407.16890
  - bubblyworld 1y ago
    That's fair, I've run into a lot of misconceptions like that before. And probably believed some of them at earlier points in my life =P (Roger Penrose himself makes a version of that claim in "the Emperor's New Mind", so we're in good company...) About the bcrypt thing... yeah, so one way you can do it is write a program that generates all possible keys starting with the letter 'a', and tests them. Then you run your halting oracle on that, and if it returns true you know the first letter of the key is 'a'. Do this for each index/letter combination and you can crack bcrypt keys in linear time (in the number of calls to your halting oracle).
yusina 1y ago
The halting problem applies also for finite-but-unbounded memory. If you give me a decider that can tell me for any program with a state space up to size N whether it halts or not, then I will be able to produce another program with a larger state space and which then your decider won't be able to decide. This new program doesn't use infinite space. Just more than your decider can handle. You can't produce a single decider that works for all inputs. It is often ok to approximate "finite but unbounded" with "infinite", and surely anyhing that can handle infinite inputs will be able to handle finite-but-unbounded inputs too, but in this context the two are not the same. The term "infinite" is often misused to mean "finite but unbounded" but it is an important distinction.
- dooglius 1y ago
  That doesn't sound right. All my decider needs to do is wait for a repeated state (no halt) or a halt. If the state space is finite then one of these is guaranteed to happen.
  - yusina 1y ago
    And how does your decider recognize that a state has been attained twice? If I make the input system large enough then you don't have enough space in your decider to save all the states which it has observed.
    - dooglius 1y ago
      What do you mean "space in your decider"? My decider takes finite but unbounded memory, same as the machine it's deciding.
      - yusina 1y ago
        Ok, if that's the class of systems we are talking about, then the system that your decider wants to check does not need to attain the same state twice. It may or may not terminate, and your decider may never know. You can't have it both ways. Keep in mind that the input can be as adversarial as it wants and knows, including having full knowledge of what your decider is trying to do.
Tainnor 1y ago
Decidability is a term from theoretical CS where languages can be arbitrarily big. It doesn't make sense to repurpose the term for actual finite-memory machines.

ummonk 1y ago

Yes, the article is clearly confused about the concepts, given its mention of bcrypt cracking and chess engines.

dmurray 1y ago
Yes, I thought the article was really good until it got to that point. > 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.) A Turing machine can be trivially repurposed as a bcrypt cracker or chess engine (for the same definition of trivial the author is using), so if it's not intuitive that a computer can do this, then your intuition is wrong. Program optimizers and theorem provers also exist, of course, but in those cases the problems really are undecidable so no Turing machine is guaranteed to work on any given program or theorem.
- bubblyworld 1y ago
  A solution to the Halting problem can be repurposed as a general-purpose theorem prover. The author is correct. You simply write a program that searches all possible valid proofs till it finds the one you are looking for (or maybe doesn't and runs forever). Then you check whether it halts with your Halting solution - if that returns true, you know that a proof exists, otherwise you know that one doesn't. In other words, you can use undecidability of first-order logic to prove undecidability of the Halting problem if you like, although it's a bit of a chicken-egg thing historically (I believe).
  - dmurray 1y ago
    I edited the last part; I meant that the Turing machine from my second paragraph can't do those things, though the Halting machine can.
    - bubblyworld 1y ago
      Right, yeah that makes sense. But I think the author understands that very well.
      - dmurray 1y ago
        Of course he must. But the fact that we're arguing about it (and there's another thread with the same conversation) says that at least, the intent of this part wasn't clear.
  - Maxatar 1y ago
    >A solution to the Halting problem can be repurposed as a general-purpose theorem prover. The author is correct. You simply write a program that searches all possible valid proofs till it finds the one you are looking for (or maybe doesn't and runs forever). The author is not correct and it's a common misconception. Simple question for you... let's say I give you a magical black box that can solve the halting problem. Now please use it to prove or disprove the continuum hypothesis (within ZFC). Hopefully you'll come back to me and say the black box shows that the continuum hypothesis can not be proved or disproved (in ZFC). Okay we agree so far, but note that we have established that having a solution to the halting problem can not actually be repurposed as a general purpose theorem prover, since no such proof exists in the first place. Okay you might counter by saying that a solution to the halting problem can be repurposed as a general purpose theorem prover for propositions that either have a proof or don't have a proof, ignore those pesky propositions that are neither provable or unprovable... But then the solution to the halting problem doesn't get you anything... if you're dealing with a proposition that either has a proof or a proof of its negation, you don't need a solution to the halting problem to find it, you are guaranteed to find it eventually by definition. The claim that a black box that solves the halting problem can be used as a general purpose theorem prover is simply untrue and confuses certain concepts together. At best you can claim it gives you a restricted theorem classifier.

bubblyworld 1y ago

I don't think this is an important distinction. The point of Turing machines is that you can ask questions like "can all instances of this problem be solved uniformly, and how relatively expensive is it?". This requires infinite memory in a formal sense, because instances of (most) problems can be arbitrarily large. Yes, if you ask the same question with a fixed (finite) memory restriction on everything, the answer is uninteresting. To me, this is... uninteresting. It tells you nothing about the underlying logical structure of your problem, which is what mathematicians are really trying to get at! (first and foremost Turing machines are a tool for analysing problems mathematically, not a model of your laptop) Also note that "states" in your sense are not the same as "states" in a Turing machine (which are just one of the inputs to the transition function). There are Turing machines with less than ten thousand states whose behaviour is undecidable in ZFC (https://arxiv.org/abs/1605.04343 https://arxiv.org/abs/1605.04343).

Ukv 1y ago
> Yes, if you ask the same question with a fixed (finite) memory restriction on everything, the answer is uninteresting. To me, this is... uninteresting. It tells you nothing about the underlying logical structure of your problem, which is what mathematicians are really trying to get at! > (first and foremost Turing machines are a tool for analysing problems mathematically, not a model of your laptop) I think what makes Animats's distinction worth stressing is that a lot of people miss this and fall into the trap of making false/misleading claims about the impact of the halting problem on actual computers/software. For instance, claiming that the halting problem proves there are problems humans can solve that computers fundamentally can't, giving "the halting problem makes this impossible" as reason against adding a halt/loop detector to a chip emulator, making all sorts of weird claims about AI[0][1], or arguably even this author's claim that a halt detector would make bcrypt cracking trivial. [0]: https://mindmatters.ai/2025/02/agi-the-halting-problem-and-the-human-mind/ https://mindmatters.ai/2025/02/agi-the-halting-problem-and-t... [1]: https://arxiv.org/pdf/2407.16890 https://arxiv.org/pdf/2407.16890
- bubblyworld 1y ago
  That's fair, I've run into a lot of misconceptions like that before. And probably believed some of them at earlier points in my life =P (Roger Penrose himself makes a version of that claim in "the Emperor's New Mind", so we're in good company...) About the bcrypt thing... yeah, so one way you can do it is write a program that generates all possible keys starting with the letter 'a', and tests them. Then you run your halting oracle on that, and if it returns true you know the first letter of the key is 'a'. Do this for each index/letter combination and you can crack bcrypt keys in linear time (in the number of calls to your halting oracle).

yusina 1y ago

The halting problem applies also for finite-but-unbounded memory. If you give me a decider that can tell me for any program with a state space up to size N whether it halts or not, then I will be able to produce another program with a larger state space and which then your decider won't be able to decide. This new program doesn't use infinite space. Just more than your decider can handle. You can't produce a single decider that works for all inputs. It is often ok to approximate "finite but unbounded" with "infinite", and surely anyhing that can handle infinite inputs will be able to handle finite-but-unbounded inputs too, but in this context the two are not the same. The term "infinite" is often misused to mean "finite but unbounded" but it is an important distinction.

dooglius 1y ago
That doesn't sound right. All my decider needs to do is wait for a repeated state (no halt) or a halt. If the state space is finite then one of these is guaranteed to happen.
- yusina 1y ago
  And how does your decider recognize that a state has been attained twice? If I make the input system large enough then you don't have enough space in your decider to save all the states which it has observed.
  - dooglius 1y ago
    What do you mean "space in your decider"? My decider takes finite but unbounded memory, same as the machine it's deciding.
    - yusina 1y ago
      Ok, if that's the class of systems we are talking about, then the system that your decider wants to check does not need to attain the same state twice. It may or may not terminate, and your decider may never know. You can't have it both ways. Keep in mind that the input can be as adversarial as it wants and knows, including having full knowledge of what your decider is trying to do.

Tainnor 1y ago

Decidability is a term from theoretical CS where languages can be arbitrarily big. It doesn't make sense to repurpose the term for actual finite-memory machines.