This is a big-list community question, so I'm sorry in advance if it is deemed too soft but I haven't seen anything similar yet.
I've seen computer scientists post questions looking to learn things from pure maths. This is basically the other way around… My ignorance may prevent me from being as specific as I think I would like to be and so I have separated my main question into two.
What good books – readable
introductions – are there for
mathematicians to learn about computer
science?
By this I really mean the science of how computers work. There are perhaps some books out there which are written in a style which mathematicians can relate to – e.g. not practicality-focused, starting from the more abstract fundamentals and building up (I may be wrong but I'm under the impression that a lot of books in other disciplines shy away from presenting things this way around, whereas mathematicians (for better or worse) are accustomed to it). Partly to illustrate what the first question is not asking, the second question is
What good books – readable
introductions – are there for
mathematicians looking to learn about
theoretical computer science, as it is as a
subfield of maths?
Here is where my ignorance prevents me from explaining the question any more because I can only assume these two aren't the same thing…
It seems quite frustrating that I have made it to grad school and know very little about computers and theoretical CS.
Standard "one recommendation per post" is probably appropriate, + a few sentences about what the books did for you. Also, maybe I should say that I'm not looking to ditch my current interests and become a computer scientist, so things being readable is a fairly strong condition. I'm not looking to become an expert, just to deal with my own ignorance. Thanks in advance.
Best Answer
For the second question (theoretical computer science) I strongly recommend Sipser's Introduction to the Theory of Computation. It is a very easy read for someone with a math background, and requires essentially no specific previous knowledge. It is essentially a one-semester first course in the subject of computability and complexity theory. As such, you get all the nice classical results, but not the more recent results which are less complete, polished, or appealing to an outsider who just wants a "taste".