[GregBuchholz]

I always liked "Godels Theorem Simplified". It doesn't rely on heavy technical prerequisites in mathematics or CS. It is pretty much as advertised, a simplification of Godel's original proof. Godel used a more complicated encoding scheme using prime numbers, which Gensler replaces with a simpler encoding scheme. He walks you through various less powerful formal systems, before you get to one complicated enough to have incompleteness issues. There is also discussion about the philosophical ramifications of Godel's theroems.

http://www.amazon.com/Godels-Theorem-Simplified-Harry-Gensle...

"Godel, Escher, Bach" is another interesting read, but that volume does have a lot of extraneous fluff.

[davvid]

extraneous fluff

Hey, now. Gödel, Escher, Bach has character and is IMO a very fun book. You might have to read it more then once, though.. it's self-referential and strange-loopy in that way.

[lcargill99]

It's an excellent book, but it's very broad, and requires a commitment in time.