Is it true to say that "it's not logically possible to prove something can't be done"?
A friend of mine asked me if I could explain this statement: "It's not logically possible to prove that something can't be done". The actual reason is the understanding of this strip:
Since I'm not an expert on logic, but at least know the basics, I told him that the statement is false. To prove it I gave him the counterexample of the impossibility of trisecting an angle by using only straightedge and compass, which was proved by Pierre Wantzel. This shows clearly that it's possible to prove that something can't be done.
When I told him this, he explained to me that this is sort of naive because Asok, the guy who makes the statement, is a graduate from IIT and also I read that he's always a brilliant character in the strip.
Can you guys please tell me what you think about this? Also I'd like to know how you would interpret this dialog.
Solution 1:
What the strip most likely was (awkwardly) referring to is not that it's impossible to prove something can't be done, but rather that it's impossible to prove within a (sufficiently powerful) formal system that something can't be proven in that system — in other words, letting $P(\phi)$ be the statement 'there exists a proof of $\phi$', then it's impossible to prove any statement of the form $\neg P(\phi)$ (i.e., the statement $P(\neg P(\phi))$ can't be true).
The reason behind this has to do with Godel's second incompleteness theorem that no formal system can prove its own consistency - in other words, the system can't prove the statement $\neg P(\bot)$ (or equivalently, $P(\neg P(\bot))$ is false). The logical chain follows from the statement 'false implies anything': $\bot\implies\phi$ for any proposition $\phi$. By the rules of deduction, this gives that $P(\bot)\implies P(\phi)$, and then taking the contrapositive, $\neg P(\phi)\implies\neg P(\bot)$ for any proposition $\phi$; using deduction once more, this gives $P(\neg P(\phi))\implies P(\neg P(\bot))$ — if the system can prove the unprovability of any statement, then it can prove its own consistency, which would violate Godel's second incompleteness theorem.
Note the keyword 'sufficiently powerful' here - and also that we're referring to a formal system talking about proofs within itself. This is what allows statements like the impossibility of angle trisection off the hook: the axioms of ruler-and-compass geometry aren't sufficiently strong for Godel's theorem to apply to the system, so that geometry itself can't talk about the notion of proof, and our statements of proofs of impossibility within that system are proofs from outside of that system.
Solution 2:
Scott Adams may have intended something different, but in the given context and with the given wording, Dan is right and Asok is wrong.
Imagine Asok writing a piece of software that crucially depends on deciding the halting problem (or any other property covered by Rice's theorem), then Dan is right: The halting problem is not decidable and therefore the software will never work. And Dan can indeed prove it, because the undecidability of the halting problem is provable.
Solution 3:
It's a paradox: by saying "it's not logically possible to do X", Asok is, in effect, claiming that there must exist a proof that X is impossible. Which is impossible, if Asok is right.
Hence Asok must be wrong!
Solution 4:
Basically the strip is about the scientist being a smartass and not about logic, possiblity of proving something etc. What he says is "software you're writing will never work" (and not "software you wrote"), so at this point it's really impossible to prove anything. It's not possible to prove the software will never work, once it's written. So your friend's conclusion misses the point, he is rather siding with Dan (trying to outsmart you, not understanding the core problem) than with Asok.
Solution 5:
"That software you are writing will never work" is not a claim within a formal system.
Trying to cast it into a propositional statement can only ruin the joke (and I can prove it).