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) fi

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 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 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.