Turing categories, abstract computability, and unifying complexity with computability

Robin Cockett, University of Calgary. Part of the Algebra, Logic, and Algorithms Seminar Series.

Turing categories give an abstract formulation of computability.  They may be viewed as the computable maps of a partial combinatory algebra which lives somewhere -- usually not in sets!  While it is well known that partial combinatory algebras can express all computable functions, a question one can still reasonably ask is: what categories can be the total maps of a Turing category?

The answer, somewhat surprisingly, includes the total maps of all "functional" complexity classes (hence the title).  Thus, there are Turing categories whose total maps are exactly the P-time functions or the log-space maps.  The talk will describe a concrete and yet fairly general way in which to construct a Turing category whose total maps belong to a particular complexity class.