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).
> 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).
The conversation is going in circles here =) I agree with everything you have written.
> (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.