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