[johncolanduoni]

They are intimately related. If you look at how Gödel's incompleteness theorem is stated, the existence of "effective procedures" (I.e. Computable functions) figures in intimately.

A good overview of this in a reasonably accessible format can be found here: http://www.scottaaronson.com/blog/?p=710

The same author wrote a good treatment of the implications of the undecidability of P=NP: http://www.scottaaronson.com/papers/pnp.pdf

Scott Aaronson is probably one of the best at explaining theoretical computer science, if you're interested in these topics you should follow his blog.