> The halting problem says that we cannot create an algorithm that, when applied to an arbitrary program, tells us whether the program will halt or not.
Or more simply:
No program can tell whether any program will halt or not.
I found this bit was really helpful:
“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.”
You are correct that Goldbach cannot be proven true via brute force. But again, a hypothetical general halting machine may require impractical time — 14 million billion years.
So the idea that “if this existed we crack all sorts of hard problems/optimize” is not necessarily true.
Might try for another wording which isn't easily misunderstood. I was going to suggest every instead of any but that supports a different misunderstanding.