Wednesday, November 9, 2011

Why philosophers should care about computational complexity

Read this paper a month or two back.  It's a truly fascinating discussion of the mathematics of computational complexity ("How hard is it to find an answer to a problem in class X using algorithm Y?") and its implications for some puzzles in philosophy.

Turns out that understanding complexity classes can add a lot to the way we think about our own minds. Examples include:
  • Do I "know" what 1,847,234 times 345 is?
  • Is it possible to cheat on the Turing test?
  • Can waterfalls think?
  • When can you prove you know something without revealing *how* you know it?
  • If my grandkids learn to time travel, do I have to worry they might kill me?
There's math, but Aaronson has gone to a lot of effort to keep it manageable and well-explained. Highly recommend it.

(BTW, the paper has been out there for a few months. I'm posting now because it's related--a little--to the review of computational social science I've been working on.)

No comments:

Post a Comment