Theoretical Computer Science from the Category Theory Perspective

A talk given in the Wolfram Summer School, Bentley University, Waltham MA We describe the structure of the collection of computable functions. We show how category theory is fundamental for understanding the major ideas and theorems of theoretical computer science. Computability theory and complexity theory will be our main focus. We will meet some of the deepest notions of modern computer science and mathematics, e.g., Turing machines, unsolvable problems, the P=NP question, Kurt Gödel's incompleteness theorem, intractable problems, cryptographic protocols, Alan Turing's Halting problem.