I think Sipser's Introduction to the Theory of Computation deserves a mention. It is incredibly clear, full of valuable examples, and an absolute classic. I can't think of a better book for a mathematician who's interested in theoretical computer science. It also seems to serve computer scientists without a great deal of mathematical background by providing an introduction to proofs at the beginning. My favorite part: all theorems come with "Proof Idea" first and then proof after that. This helps the computer scientists who are not that familiar with proofs, but it's also great for a mathematician to get the main idea of the proof, fill in the blanks themselves, and then move on to the next result.

I think Sipser's Introduction to the Theory of Computation deserves a mention. It is incredibly clear, full of valuable examples, and an absolute classic. I can't think of a better book for a mathematician who's interested in theoretical computer science. It also seems to serve computer scientists without a great deal of mathematical background by providing an introduction to proofs at the beginning. My favorite part: all theorems come with "Proof Idea" first and then proof after that. This helps the computer scientists who are not that familiar with proofs, but it's also great for a mathematician to get the main idea of the proof, fill in the blanks themselves, and then move on to the next result.