15th Estonian Winter School in Computer Science (EWSCS)
XV Eesti Arvutiteaduse Talvekool

Palmse, Estonia, February 28 -March 5, 2010

Robin Cockett

Department of Computer Science
University of Calgary
Alberta, Canada

Categories and Computability

Abstract

Turing categories are a convenient setting for the study of abstract notions of computability: the aim of these tutorials will be to introduce these categories and to show how they can be used to unify various notions of computability.

... and to understand Turing categories it is useful to understand abstract categories of partial maps. These are called restriction categories - that they have a simple algebraic formulation is a quite remarkable fact of nature.

... and to understand in what sense restriction categories capture the notion of "partial map" some basic category theory is useful: this is where the course will start.

Category theory is a foundational subject which unifies tools and has ramifications in theoretical subjects from physics, through computer science, to philosophy and logic. It is not a static subject, rather it is undergoing a dynamic development in the hands not only of category theorists but an increasingly diverse community of people who are applying category theory. Hopefully the course will give some flavor of this diversity.

The course will give a swift introduction to categories, functors, natural transformations, adjoints, monads, and limits. I will introduce some categories I know and love. Then the course will focus on showing how one can model partial maps both using monads and, more elementarily, using restriction categories: this will then lead to an - all too brief - introduction to Turing categories.

Course materials

Valid CSS! Valid XHTML 1.0 Strict Last changed March 9, 2010 2:20 EET by local organizers, ewscs10(at)cs.ioc.ee
EWSCS'10 page: http://cs.ioc.ee/ewscs/2010/