Theory of Computation (Sipser)

Series: AI Books · Book deep dive

Introduction to the Theory of Computation — Michael Sipser

Michael Sipser introduces the mathematical foundations of computation.

Automata and formal languages explain what different computational models can recognize.

Computability theory asks which problems can be solved by algorithms at all.

Complexity theory studies how the required time and memory grow with a problem’s size.

Proofs and examples connect these questions to the capabilities and limits of computers.

Publication source

Explore: AI & Computer Science

Related episodes: Structure and Interpretation of Computer Programs (Abelson & Sussman) · The Information (James Gleick)