We can put the point even more sharply. The Austrian-born mathematician Kurt Gödel taught that, given any mathematical question that hasn’t been answered yet (except for questions that boil down to a finite calculation, such as whether White has a winning move in a chess game), it’s possible that the answer is unprovable from the usual axioms of mathematics. And yet, 85 years after Gödel uncovered this gremlin at the centre of mathematics, the fact is that it’s remained mostly dormant. Gödel’s Incompleteness Theorem rears its head only in specialised situations: ...No, this is not correct. There was never a possibility that Fermat's Last Theorem might be demonstrably independent of the axioms of set theory.
It didn’t need to be that way (or, maybe it did, but it’s not obvious why). A priori, Fermat’s Last Theorem, the Poincaré Conjecture, and pretty much every other statement of mathematical interest could have been neither provable nor disprovable: if true, then totally disconnected from all the other interesting truths, an island unto itself, with the only question (a question of taste!) being whether we should add it on as a new axiom. But it didn’t turn out like that.
Any counterexample to FLT could be verified by a finite computation. Therefore the only possibilities were that FLT is provably true, true but not provable, and provably false. Any proof that FLT is independent of axioms would also be a proof that it is true about the integers.
While is it true that independence results are exceptional, the continuum hypothesis was certainly a mainstream math problem. It was the first of Hilbert's famous 1900 list of 23 open problems.
Lumo is flattered to be attaked in this essay, and disagrees with comments about the possibility of P=NP.
Aaronson gives the impression that mathematicians are solving the big questions, but his field of complexity became a real field over 40 years ago when everyone realized that P=NP was such an important question. A lot of really smart mathematicians and computer scientists have worked on it, without success.
And he specializes in the subfield of quantum computer complexity, and there is no consensus on whether a quantum computer is even possible.
This comment has been removed by the author.
ReplyDeleteI think Motl has a real point about P vs NP, at least in a theoretical sense, but the entire question is stupid because it's so open-ended and requires that proof methods condense the entire complexity of recursive algorithms to say anything either way. Are there a finite number of brute-force cases and the rest reachable by indexed pre-computation and fast heuristics? Besides threading, Turing machines don't even take into account a modern machine's constant-time jump instructions.
ReplyDeleteThe points about Godel are even more mislead than you let on. Godel is just Cantor in disguise and professional logicians and mathematicians seriously disappoint me. Very unintelligent discussions have gone on:
Self-referential sentence proofs: Godel, Rosser, Kleene, Post, Church, Turing, Smullyan, Jech, Woodin
Epsilon-naught induction proofs: Kripke, Paris-Harrington, Goodstein, Hydra
Kolmogorov complexity proofs: Chaitin, Boolos
Godel's result was reformulated by others in very simple terms. Given a computable axiomatic system A construct a program GODEL that does the following:
1. Prints its own code into a variable R. (Hint: Make quining a subroutine)
2. Go on deducing all consequences of A, looking for a proof of the statement "R does not halt."
3. If it finds this statement, it halts.
Cantor makes a more obvious appearance in the non-standard model, which requires infinite non-natural numbers after the natural numbers. Interestingly, one of the leading Godel scholars, Solomon Feferman, dispenses with Cantor but still, for some reason, entertains this incompleteness garbage. Incompleteness can be done away with using an infinitely axiomatizable system but that very fact reveals what it's really about. Poincare knew it was trivial all along.
The same way you can't complete the infinity of reals, you can't complete the entire list of computer programs. The initial assumptions are the problem. Furthermore, the Godel sentence is basically a gibberish freak that has no provable relation to meaningful mathematical problems. The idea that all undecidability is an instance of Godel is pure garbage and imbeciles like Cohen make me embarrassed. Godel sentences are of a very strange and peculiar kind.
In other words, you can construct nonsense linguistics AND/OR nonsense mathematics to cover over a bad premise. It doesn't matter what descriptive language you use, the language itself can not protect you from bad ideas and lies. What a tangled web we weave when we practice to deceive all the way down baby.
ReplyDeleteWhen people make a big deal out of undecidability, I just ask them if they stop beating their wife. The law of the excluded middle was always stupid. Furthermore, why ask a system you don't trust if it's consistent? It's pure circularity! No need for a fancy proof, but for some reason books get written about it.
Delete