Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: Robin Cockett: Abstract computability: unifying complexity and computability

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

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
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 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.   

Document Actions