Hacker News Reader

Comment by cobbzilla | Hacker News Reader

I really enjoyed the author’s explanation of undecidability.

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.”

View on HN

I'm not sure about that. These are also easily solved with a general-purpose CPU, if you don't care about running time. And there's nothing that says that a halt detector would be fast. The impossibility result is more interesting than just "it would take a million times the age of the universe to complete if every atom in it were put to the sole purpose of computing it" as we often see with cryptography.

That's not necessarily true. Consider the program `x := 4; loop {if !sum_of_two_primes(x) {return true}; x += 2}`. If we run this on a general purpose CPU, this will halt if and only if Goldbach's conjecture has a counterexample. Otherwise it will run forever. So even if a working halt detector takes 14 million billion years, it will definitely tell us if the conjecture is true or not. Whereas if the general purpose CPU is still running after that time, we still have no way of knowing whether it's because it's going to run forever or if it simply hasn't reached the first (ludicrously large) counterexample.

I think you're agreeing with me. The problems listed as something that a halt detector can be "trivially repurposed" for are problems that a normal CPU can also be trivially repurposed for (ignoring the issue of execution time), and my understanding is that normal CPUs are not impossible. The halting problem is different because it is provably impossible even with unlimited resources unless you're somehow able to make something more capable than a Turing machine.

They’re saying that chess and bcrypt and some others can be brute forced.

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.

Reply on news.ycombinator.com