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 scienctists 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-focussed, 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.