Yanofsky N. Theoretical Computer Science...2022

Textbook in PDF format

Using basic category theory, this Element describes all the central concepts and proves the main theorems of theoretical computer science. Category theory, which works with functions, processes, and structures, is uniquely qualified to present the fundamental results of theoretical computer science. In this Element, readers will meet some of the deepest ideas and theorems of modern computers and mathematics, such as Turing machines, unsolvable problems, the P=NP question, Kurt Gödel's incompleteness theorem, intractable problems, cryptographic protocols, Alan Turing's Halting problem, and much more. The concepts come alive with many examples and exercises.
Preface
Introduction
Aide-Mémoire on Category Theory
Slice Categories and Comma Categories
Models of Computation
The Big Picture
Manipulating Strings
Manipulating Natural Numbers
Manipulating Bits
Logic and Computation
Numbering Machines and Computable Functions
Computability Theory
Turing’s Halting Problem
Other Unsolvable Problems
Classifying Unsolvable Problems
Complexity Theory
Measuring Complexity
Decision Problems
Space Complexity
Diagonal Arguments
Cantor’s Theorem
Applications in Computability Theory
Applications in Complexity Theory
Conclusion
Looking Back
Moving Forward
References
Acknowledgements
Index