Abstract:
Using basic category theory (category, functor, natural transformation, etc.), 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 text, we meet some of the deepest ideas and theorems of modern computers and mathematics, e.g.,
- Turing machines,
- unsolvable problems,
- the P=NP question,
- Kurt Gödel’s incompleteness theorem,
- intractable problems,
- Turing’s Halting problem,
- ...
The concepts come alive with many examples and exercises. This short text covers the usual material taught in a year-long course.
This is the book written by Noson S. Yanofsky.
There is another paper with the same name as this book from the same author.
Abstract. Theoretical computer science discusses foundational issues about computations. It asks and answers questions such as:
- “What is a computation?”,
- “What is computable?”,
- “What is efficiently computable?”,
- “What is information?”,
- “What is random?”,
- “What is an algorithm?”,
- ...
We will present many of the major themes and theorems with the basic language of category theory. Surprisingly, many interesting theorems and concepts of theoretical computer science are easy consequences of functoriality and composition when you look at the right categories and functors connecting them.