LFCS seminar: Robin Cockett: Abstract computability: unifying complexity and computability
What 


When 
Nov 13, 2018 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Add event to calendar 
vCal iCal 
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 Ptime functions or the logspace 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.