Comment by strlen

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.

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.