Date/Time
Date(s) - 13/11/2018
4:00 pm - 5:00 pm
Location
The Informatics Forum, University of Edinburgh
SICSA DVF Professor Robin Cockett, Department of Computing Science at the University of Calgary will be giving a seminar at the Informatics Forum, University of Edinburgh on 13th November.
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.
Bio: Prof. J. R. B. Cockett (1952) is a category theorist and computer scientist working in proof theory, computability and complexity, programming languages and semantics, categorical quantum information theory, and abstract differential geometry. After his PhD in Mathematics at the University of Leeds in 1979, he has worked in Essex (for Marconi research), Tennessee (US), Sydney (Australia), and since 1991 has been at the University of Calgary (Canada), where is a professor of computer science. He has developed three programming languages, Chartity, LQPL, and MPL, and is known for introducing and studying restriction categories, Turing categories, differential categories, and tangent categories.
Professor Cockett is being hosted by Dr Chris Heunen, University of Edinburgh
