- The Annotated Turing by Charles Petzold
- Quantum Computing since Democritus by Scott Aaronson
- Euclidean and Non-Euclidean Geometries by Marvin Jay Greenberg (a textbook, but an easy one to read on your own)
- Gödel's Proof by Nagel and Newman (best if he can read it with a partner and talk through the steps)
- Prime Obsession by John Derbyshire
Some of those have already been mentioned, but consider this another vote for them. :-)
- The Annotated Turing by Charles Petzold
- Quantum Computing since Democritus by Scott Aaronson
- Euclidean and Non-Euclidean Geometries by Marvin Jay Greenberg (a textbook, but an easy one to read on your own)
- Gödel's Proof by Nagel and Newman (best if he can read it with a partner and talk through the steps)
- Prime Obsession by John Derbyshire
Some of those have already been mentioned, but consider this another vote for them. :-)