3 April 2007

2:30 - 4:00 Pieter Hofstra

Title: Abstract Computability

Abstract (joint work with R. Cockett): Consider the category where the
objects are the finite powers of the natural numbers and where the
morphisms are partial computable functions. This is the prime example
of a Turing category - a small weakly cartesian closed partial map
category with a universal object. Such categories (or, to be precise,
a subclass of these) were first studied by Di Paolo and Heller under
the name recursion categories, with the aim of giving diagrammatic
proofs of results in basic recursion theory. 
We first show how such partial map categories come equipped with a
term logic, making reasoning about them much easier. Then we'll
illustrate this by analysing some recursion-theoretic
phenomena. Finally, we explain why the scope of Turing categories is
much wider than just the categorical study of recursion theory: they
are equally suitable for studying models of untyped (partial) lambda
calculus. More generally, the study of Turing categories is, in a way,
equivalent to the study of partial combinatory algebras.