4 ms·

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 uni

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).
  - Ukv 1y ago
    > 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'. And you really can do that. For actual computers we have cycle detection algorithms that can tell you definitively if your program will halt or not. Determining whether the program halts can still be complex or slow, which is the case here, but the halting problem does not make it undecidable (because it doesn't apply to real computers) nor place any lower bound on that complexity (nothing preventing a more advanced halt detector from finding better shortcuts).
    - deleted 1y ago
      [deleted]
    - bubblyworld 1y ago
      The conversation is going in circles here =) I agree with everything you have written.
  - Animats 1y ago
    > (Roger Penrose himself makes a version of that claim in "the Emperor's New Mind", so we're in good company...) Right. That leads to the whole 'brains are special and analog and quantum or something and thus can't be emulated digitally' line of thought. That line of argument is looking rather threadbare since LLMs got good. That's a different issue than decidability, though. Penrose does raise a good question as to how biological brains get so much done with so little power and rather low-frequency signals.

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).
- Ukv 1y ago
  > 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'. And you really can do that. For actual computers we have cycle detection algorithms that can tell you definitively if your program will halt or not. Determining whether the program halts can still be complex or slow, which is the case here, but the halting problem does not make it undecidable (because it doesn't apply to real computers) nor place any lower bound on that complexity (nothing preventing a more advanced halt detector from finding better shortcuts).
  - deleted 1y ago
    [deleted]
  - bubblyworld 1y ago
    The conversation is going in circles here =) I agree with everything you have written.
- Animats 1y ago
  > (Roger Penrose himself makes a version of that claim in "the Emperor's New Mind", so we're in good company...) Right. That leads to the whole 'brains are special and analog and quantum or something and thus can't be emulated digitally' line of thought. That line of argument is looking rather threadbare since LLMs got good. That's a different issue than decidability, though. Penrose does raise a good question as to how biological brains get so much done with so little power and rather low-frequency signals.