Foundations & Overviews

A Mathematical Theory of Communication

Claude Shannon

Defines information quantitatively and proves the limits of compression and error-free transmission over noisy channels.

Assumes probability and logarithms, plus the patience to let the opening pages define everything they use

MIT 18.404J Theory of Computation

Michael Sipser (MIT OpenCourseWare)

Develops automata, computability and complexity as one argument about what machines cannot do, taught by the author of the standard text.