I recommend The Incompleteness Phenomenon over GEB[1]. It thoroughly presents Gödel's Completeness and Incompleteness theories at a level appropriate to the collegiate Math or Computer Science student.
The discussion of Gödel's theorems is not the only thing that makes GEB an interesting read.
What's more, GEB presents Aristotelianism vs. Platonism in the context of _computation_.
_That_ is a question CS majors should at least be aware of.
The question of whether computations can _ever_ be brought to have consciousness.
Then again, given my limited knowledge, I am far from being an authority on the topic and look forward to gaining more insight by hearing other opinions.
Undoubtedly. However, from a standpoint of teaching a class to Math and Computer Science students you can and should present the backing theories in full detail. Student benefit greatly from having a common write up on the proofs. The philosophical discussion can be saved for the classroom (with supporting supplementary readings).
The best match among existing categories, IMHO is ``Theory,'' which I assume refers to "Theory of Computation."
It is there that formal systems are brought up and CS majors should be aware of the hierarchy and limitations of formal systems, which are discussed in GEB.
If I were to place GEB under an arbitrary category, I would probably suggest ``Philosophy of Computation.''
I was about to add GEB, but realized it doesn't quite fit under any category.
I could add a "general" reading list, but do you think it fits in a category?