If you haven't read the book "Gödel, Escher, Bach" - http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach - you need to do yourself a favor and do so. It explores the ideas of recursion, logic, infinity, and so much more in one beautifully written book.