Godel, Escher, Bach - An Eternal Golden Braid
The book builds in a very approachable manner, for even the most uninitiated reader, from basic formal systems to DNA and artificial intelligence. Each step is presented first with a humorous take in the form of a dialog between characters like Achilles and Tortoise and then the idea is elaborated on in a more formal manner with intellectual exercises that should engage the reader. Also the progression is made with a great many analogies where things like music, memory, DNA, and other seemingly unrelated topics are woven together to give a purchase point from many angles and thus be accessible to a great many people with a variety of backgrounds. I can say that I personally, with those 40 years of hindsight, don't give much credibility to some of the future (current) prospects of AI, but non-the-less find the book interesting and a worthwhile read for anyone interested in the topics. Overall the book is funny, informative, and a great introduction to some topics that 40+ years later we are still grappling with.