Why Philosophers Should Care About Computational Complexity
scottaaronson.com
Why Philosophers Should Care About Computational Complexity
1–10 of 38 posts
Re: Why Philosophers Should Care About Computational Complexity
#2This is basically aimed at analytic philosophers. Continental philosophers generally aren't interested in this sort of thing.
Re: Why Philosophers Should Care About Computational Complexity
#3This 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.
Re: Why Philosophers Should Care About Computational Complexity
#4They 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.
Here's philosophers' take on Kurt Godel:
http://plato.stanford.edu/entries/goedel/
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.
Re: Why Philosophers Should Care About Computational Complexity
#5They 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. Here's philosophers' take on Kurt Godel: http://plato.stanford.edu/entries/goedel/ I am, however, curious as to how other problems in computational complexity figure in philosoph…
> They already do. Incompleteness Theorem ("some statements can neither be proved nor disproved", e.g., The Halting Problem which is incomplete) is one of the most significant achievements in logic.
Aaronson covers this, pointing out that those results are both in computability theory, not complexity.
Re: Why Philosophers Should Care About Computational Complexity
#6They 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. Here's philosophers' take on Kurt Godel: http://plato.stanford.edu/entries/goedel/ I am, however, curious as to how other problems in computational complexity figure in philosoph…
Godel's incompleteness theorems do not assert that particular statements cannot be proven. Furthermore, the "Haklting Problem" is not a statement.
Re: Why Philosophers Should Care About Computational Complexity
#7A 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. (p. 43)
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 true without further qualification. For instance, take Gödel's first incompleteness theorem. It states that if F is any consistent formal system capable of proving statements about whether or not arbitrary Turing machines halt, then there are true statements which cannot be proved within F. (Here, consistent means that it's not possible within F to prove both a statement "S" and its negation "not S".)
In the same sense, its true (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."
Re: Why Philosophers Should Care About Computational Complexity
#8They 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. Here's philosophers' take on Kurt Godel: http://plato.stanford.edu/entries/goedel/ I am, however, curious as to how other problems in computational complexity figure in philosoph…
> They already do. Incompleteness Theorem ("some statements can neither be proved nor disproved", e.g., The Halting Problem which is incomplete) is one of the most significant achievements in logic. Aaronson covers this, pointing out that those results are both in computability theory, not complexity .
Ah, thanks for the correction. I always thought of complexity as being a subset of computability theory (much like NP-Complete problems are a subset of Complete problems), but you are right-- they're separate disciplines.
Will need to read this, of course. My fault for replying before at least attempt to scan over the full essay linked from the post.
Re: Why Philosophers Should Care About Computational Complexity
#9They 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. Here's philosophers' take on Kurt Godel: http://plato.stanford.edu/entries/goedel/ I am, however, curious as to how other problems in computational complexity figure in philosoph…
I haven't read the paper, but here's one example I've seen. Assume for the moment that the universe is closed, complete (there is nothing but our universe), and deterministic under the hood. Obviously, nobody in the universe has free will, right? Because it's all closed and all outcomes are predetermined.
But maybe that's not a useful definition of free will. The conventional, fuzzy definition of free will has an omniscient narrator in it; "I do not have free will if the omniscient narrator knows in advance everything I will do" is a reasonable expansion of the conventional idea. But in my hypothesized universe, there is no omniscient narrator. There are only various entities with various degrees of computational power, with a varying but rather quantifiable amount of information that any entity can obtain about any other.
Suppose it can be demonstrated that it is computationally infeasible for any entity due to being too complex to ever predict the actions of any human-sized (or greater) other entity, even if granted all the remaining resources in the universe to compute the actions. Or suppose it is demonstrated to be quite easy. Either way, that would be an interesting philosophical contribution, no?
(I'm just sketching the idea here. I'm not trying to defend it or attack it. Oh, and one of the foundations of philosophy is that there is never One True Definition; all loaded terms in this post are ultimately ill-defined, and I've avoided the distraction of even beginning to nail them down on purpose.)
Re: Why Philosophers Should Care About Computational Complexity
#10one interesting perspective on complexity is that of Ashby and his law of requisite variery. http://en.wikipedia.org/wiki/Variety_(cybernetics)#The_Law_o...
this work was later manifested in the work of stafford beer creating a control center in chile during the 70s.(http://en.wikipedia.org/wiki/Project_Cybersyn).