Synthetic Computability (MFPS XXIII Tutorial)
A tutorial presented at the Mathematical Foundations of Programming Semantics XXIII Tutorial Day.
Abstract: In this tutorial we show how to elegantly develop the basics of computability theory with simple set-theoretic and domain-theoretic ideas and constructions. Computability is never mentioned explicitly, instead we work in an intuitionistic set theory extended with suitable (classically inconsistent) axioms. The usual theorems of computability theory are expressed as statements of set-theoretic, domain-theoretic and topological nature. Classical theorems of computability theory are then just interpretations of our theorems in an appropriate realizability model (which will be presented in a separate tutorial).
Download slides: syncomp-mfps23.pdf