Having a decision algorithm does not make a computation free. It may take exponential time in the input size, doubly exponential time, some time involving Graham's number, ... etc. It may also take up an unreasonable amount of space. Indeed, some problems have such complex algorithms that you should expect the universe to end before the answer is determined and/or the computing device is doomed to collapse into a black hole, making the answer irretrievable.
So the blog post's claims that a hypothetical halting algorithm would solve anything "overnight" are exaggerated and naive.
"Free" in the sense of thought, cleverness, insight. You have an "everything" calculator. That is the sense in which it might be intuitive that it couldn't exist.
> So the blog post's claims that a hypothetical halting algorithm would solve anything "overnight" are exaggerated and naive.
I agree "overnight" is misleading in this context. However, I am fairly sure the author is aware of the point you are making.
> "Free" in the sense of thought, cleverness, insight. You have an "everything" calculator. That is the sense in which it might be intuitive that it couldn't exist.
Right.
But brute force solvers for bcrypt and chess are already "free" in the sense of thought, cleverness, insight. We already have the "everything" algorithm: iterate through all possible solutions in O(2^n) time and pick the best one.
A halting solver gains us nothing in these scenarios.
(The code for scoring a solution is the same code that would need to go into the halting solver. For bcrypt it's checking if the input matches, for chess it's the number of turns until checkmate.)
Yeah, I thought I already addressed that above.
Can we do the same for a theorem prover? For proofs of some fixed finite length, I think the answer is yes, but without that constraint the answer is no. Whereas with a halting detector we could.
It still seems to me your complaint (and the other poster's) are just about these specific examples rather than general argument Hillel is making. Please clarify if that's not the case, and why.
The complaint is that Hillel is providing an intuitive explanation but that intuition is clearly faulty, as demonstrated by two of the examples he gave.
P.S., you can run that proof finding algorithm (iterate through every candidate proof one by one and check for validity) for proofs of finite length in general, not just some fixed finite length. Where the halting oracle comes in is that you can use it to check whether the proof finding algorithm will ever halt, and thereby find out whether the theorem is provable or not.
> for proofs of finite length in general, not just some fixed finite length.
For a brute force proof finder, for your program to be guaranteed to finish in theory, you have to pick a length. So it is fixed. Ofc you can choose whatever length you want. But you don't have that constraint with the halting oracle. Perhaps we're saying the same thing?
For the program to be guaranteed to finish in theory, all that is required is that a valid proof exists. You don't have to pick a length in advance - the program just has to keep trying proofs of progressively longer lengths.
But it won't finish if there is no proof! A halting oracle will finish either way.
Sure, but neither bcrypt or chess fall into the category of being unprovable, so having a halting detector doesn't help for those situations. The author is mixing up problems that are "hard" in the sense that we know in principle how to solve it but need a lot of resources, versus "hard" in the sense that we genuinely don't know how to solve the problem, even if we had access to infinite resources.
Mixing these two up is very misleading and detracts from what is otherwise a well written article.
This is a fair point, and I conceded it above in one of my first replies.
The problem is the author's giving a misleading picture of the problem space with those examples.
Tasks like optimizing whole programs or running a theorem prover are difficult/impossible tasks to do perfectly. We don't have a solution verifier that we can plug into the "free" brute force framework. With theorem provers, even when restricted to fixed finite (non-trivial) lengths, I don't think we have one that always gives the right answer. And fully optimizing programs is similarly impossible to be perfect at. But if you had a halting solver you could bypass those difficulties for all of those problems.
Tasks like breaking encryption or playing chess have super simple verifiers. A halting solver would solve them sure, but we already have programs to solve them. We only lack fast enough computer to run those programs.
These are both big and significant classes of problem. The latter is not just a couple scattered examples. It has its own answers to the important questions like whether you can try every answer to make an "everything" calculator. For the first class you can't, for the second class you can. The intuition that such a thing is "too powerful" is actually a pretty bad intuition here.
> The intuition that such a thing is "too powerful" is actually a pretty bad intuition here.
I still disagree. Just focus on theorem proving and not the examples that are too simple. If the halting problem could be solved, we'd be able to magically solve all these "impossible" problems. But our intuition is that just doesn't make sense, it's "too good to be true", "the universe is just more complex than that", etc. This intuition isn't a proof, but since we do have a proof, it makes sense as an intuition. That's all that's being said.
Scott Aaronson has a similar sentiment about P =/= NP:
"If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett."
Certainly not a proof -- and ofc we have none in this case -- but still a powerful intuition.
The examples matter for the correctness.
This example is a little flawed, but go with me. Imagine someone was making an argument that an algorithm is too powerful because it can solve really hard problems, then list a bunch of problems that need ridiculous amounts of compute time to solve, but half their examples are NP-hard and half their examples are P.
The intuition that says "wow, that problem is very difficult to solve, so I'm very skeptical of a solution" is wrong. Because that intuition applies to both the NP examples and the P examples. That intuition is too simplistic and overgeneral.
You need an intuition that is right with both classes of problem. It has to say "no" to one class and "yes" to another. Ignoring the wrong examples is not how you evaluate an intuition.
My complaint is that I don't get what we are getting at when we reference "creativity," "cleverness," "ingenuity" and so on. The halting problem cannot be solved, in the general case, by any machine constructable in physical reality. That includes both computers and human beings. And computers can keep at it much longer than I can, come up with novel hypotheses to test much longer than I have the patience for, and can basically do anything I can do except try a bunch of random crap out of sheer frustration and eventually give up.