What is categorical recursion theory?
- Date: Wednesday 7 November 2018, 16:15 – 17:15
- Location: Mathematics Level 8, MALL 1, School of Mathematics
- Type: Algebra, Logic and Algorithms, Seminars, Pure Mathematics
- Cost: Free
Philip Scott, University of Ottawa. Part of the Algebra, Logic, and Algorithms Seminar Series.
We survey various approaches to computable functions and functionals arising in categorical logic. We focus on two trends. One trend describes internal recursive functions that arise naturally within certain familiar free categories, for example in free cartesian, monoidal or cartesian closed categories, as well as the free topos and certain classifying categories.
The classes of numerical functions so obtained often have close connections with familiar notions of "provably recursive" functions and functionals of higher type arising in various logics. A second, more recent, trend is to give abstract categorical theories of partiality and computability (e.g. Cockett-Hofstra's Turing Categories, and related theories based on partial combinatory algebras). These provide a modern categorical framework for partial maps and recursion theory, covering also bounded complexity and higher types.
If time permits, we briefly mention some more recent categorical extensions and characterization theorems.