<i>A given Turing machine M either accepts, rejects,
or runs forever (when started on a blank tape)... [W]hich one it does is an objective fact, independent of our formal axiomatic theories, the laws of physics, the biology of the human brain, cultural conventions, etc.</i> (p. 43)<p>Nice way to put it. As Franzen points out in "Inexhaustibility", although non-logicians sometimes find it puzzling, the above is related to what mathematicians mean when they say that a statement is <i>true</i> without further qualification. For instance, take Gödel's first incompleteness theorem. It states that if <i>F</i> is any consistent formal system capable of proving statements about whether or not arbitrary Turing machines halt, then there are <i>true</i> statements which cannot be proved within <i>F</i>. (Here, <i>consistent</i> means that it's not possible within <i>F</i> to prove both a statement "<i>S</i>" and its negation "not <i>S</i>".)<p>In the same sense, its <i>true</i> (as Aaronson wrote in "Logicians on Safari") that "there’s a finite (and not unimaginably-large) set of boxes, such that if we knew how to pack those boxes into the trunk of your car, then we’d also know a proof of the Riemann Hypothesis."
They already do. Incompleteness Theorem ("some logical statements are true but are unprovable", e.g., "this program will terminate" for some arbitrary programs a.k.a. the Halting Problem) is one of the most significant achievements in logic.<p>Here's philosophers' take on Kurt Godel:<p><a href="http://plato.stanford.edu/entries/goedel/" rel="nofollow">http://plato.stanford.edu/entries/goedel/</a><p>I am, however, curious as to how other problems in computational complexity figure in philosophy, e.g., P vs. NP completeness. Wish I had the time to read the essay.
It's interesting that one of the references Aaronson cites [63] is the pg essay "How to do philosophy" <a href="http://www.paulgraham.com/philosophy.html" rel="nofollow">http://www.paulgraham.com/philosophy.html</a>
This looks fascinating, and in yours truly is guaranteed at least one reader, once I have some time to devote to it. I think there's a lot of room for interesting work in this area.
The problem with Godel and friends is that they point to the limits of rationality. Without a transcendent rationality (and morality) upon which to discurse, philosophers are out of a job, so to speak. If you use logic to understand everything, the last thing you want to deal with is somebody telling you the limits to logic. So they blow him off.<p>At least I think the above is true for "analytic" philosophers. The "continentals", on the other hand, have been engaging in an extended <i>attack</i> on transcendent rationality since Nietszche who said, to paraphrase, that every transcendent metaphysics was an attempt to justify a morality, and every morality was facilitated a (usually inarticulate) "will to power." (This line sort of starts with Hegel, who posited that rationality emerged from history and the development of a collective human spirit, but wasn't "out there" before that). Godel seems like ammunition for these guys, but I don't think they have picked him up much. I guess if you are anti-rationalist, the last thing you read up on is advanced logic, even if it is so advanced it comes to its own frontier.
I've always considered philosophy as a sort of the mind's struggle for its own life. The introspective mind somehow can't validate itself without somehow having the absolute last say about something.<p>Given this track, a philosophical mind will produce a lot of thoughts, models, and theories of how anything that already exists <i>could</i> exist in the first place. That is itself an interesting mind-game that in some cases might even produce an insight that is applicable to something real, but generally that's where it should stay.<p>The mind can't think itself into existence, even if it wants to believe it can.<p>If it does the result bears resemblance to as if someone would try to describe forest but only be allowed to draw straight lines in one color. At best it could be exemplary line art, at worst it's just ridiculous and childish and most people will turn the other way.
It seems nobody has mentionned Gregory Chaitin[1] yet, and in my opinion it's kind of mandatory when discussing this very topic. So now it's done :-). I like his work a lot. His not really working on this subject anymore (now he's developping a new field called metabiology which is also fascinating but not very relevant here) but he used to work on Algorithmic Information Theory and he wrote a lot of books and essays (you can find almost everything on his webpage) on the subject we're discussing here. _The Limits of Mathematics_[2] might be the most relevant to Hacker News users.<p>[1] <a href="http://www.cs.umaine.edu/~chaitin/" rel="nofollow">http://www.cs.umaine.edu/~chaitin/</a>
[2] <a href="http://news.ycombinator.com/item?id=1725936" rel="nofollow">http://news.ycombinator.com/item?id=1725936</a>
Unabridged work posted on the Electronic Colloquium on Computational Complexity: <a href="http://eccc.hpi-web.de/report/2011/108/" rel="nofollow">http://eccc.hpi-web.de/report/2011/108/</a>
one interesting perspective on complexity is that of Ashby and his law of requisite variery. <a href="http://en.wikipedia.org/wiki/Variety_(cybernetics)#The_Law_of_Requisite_Variety" rel="nofollow">http://en.wikipedia.org/wiki/Variety_(cybernetics)#The_Law_o...</a><p>this work was later manifested in the work of stafford beer creating a control center in chile during the 70s.(<a href="http://en.wikipedia.org/wiki/Project_Cybersyn" rel="nofollow">http://en.wikipedia.org/wiki/Project_Cybersyn</a>).
I think irreducibility is well received in philosophy. Evolutionary Biology not so much for political reasons. Sure there are are plenty of models that incorporate emergent phenomena but it's a heated area.