<story><title>Why Philosophers Should Care About Computational Complexity</title><url>http://www.scottaaronson.com/blog/?p=735</url></story><parent_chain></parent_chain><comment><author>bumbledraven</author><text>&lt;i&gt;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.&lt;/i&gt; (p. 43)&lt;p&gt;Nice way to put it. As Franzen points out in &quot;Inexhaustibility&quot;, although non-logicians sometimes find it puzzling, the above is related to what mathematicians mean when they say that a statement is &lt;i&gt;true&lt;/i&gt; without further qualification. For instance, take Gödel&apos;s first incompleteness theorem. It states that if &lt;i&gt;F&lt;/i&gt; is any consistent formal system capable of proving statements about whether or not arbitrary Turing machines halt, then there are &lt;i&gt;true&lt;/i&gt; statements which cannot be proved within &lt;i&gt;F&lt;/i&gt;. (Here, &lt;i&gt;consistent&lt;/i&gt; means that it&apos;s not possible within &lt;i&gt;F&lt;/i&gt; to prove both a statement &quot;&lt;i&gt;S&lt;/i&gt;&quot; and its negation &quot;not &lt;i&gt;S&lt;/i&gt;&quot;.)&lt;p&gt;In the same sense, its &lt;i&gt;true&lt;/i&gt; (as Aaronson wrote in &quot;Logicians on Safari&quot;) that &quot;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.&quot;</text></comment>
<story><title>Why Philosophers Should Care About Computational Complexity</title><url>http://www.scottaaronson.com/blog/?p=735</url></story><parent_chain></parent_chain><comment><author>gnosis</author><text>This is basically aimed at analytic philosophers.  Continental philosophers generally aren&apos;t interested in this sort of thing.</text></comment>