LFCS Seminar: 13 November 2018 - Robin Cockett

Title: Abstract Computability: Unifying Complexity and Computability

Abstract:

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.