[camccann]

Computer Science--as opposed to software engineering, or day-to-day programming in general--is nothing but an odd flavor of applied abstract math. Chances are, you know more CS than most people with CS degrees, since most undergraduate "computer science" programs are actually a mish-mash of software engineering and dumbed-down bits of CS.

[sz]

This is reassuring, because for months now I've been searching and searching for a sort of "mathematician's introduction to computer science". Something precise, concise, with elegant and efficient constructions and rigorous argument... possibly in the style of Rudin's classic analysis textbook?

I recently discovered Knuth's TAOCP but the thing is overwhelmingly long and I'm not sure it's what I'm looking for.

[camccann]

I'm not sure if what you're looking for exists--it depends on what angle you're looking to approach it from, for one thing. TAOCP is a classic for certain kinds of rigorous, formal reasoning about algorithms, but it can be a bit intimidating. One of Knuth's famous quotes is "Beware of bugs in the above code; I have only proved it correct, not tried it", if that gives you some idea of his style...

On the other hand, if you want to reconstruct computer science via symbolic logic and very abstract math, variations on Church's lambda calculus (from which most functional programming languages derive) correspond closely to intuitionistic logic/the internal logic of some cartesian closed category. That stuff is liable to give even some mathematicians a headache, though, and it's easy to lose sight of more practical corners of CS that way.