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.
LFCS Seminar: 13 November 2018 - Robin Cockett
IF 4.32/4.33