Unlocking Computability: A Category Theory Perspective in Theoretical Computer Science 🧠

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.