Elgot Categories and Abacus Programs
Chad Nester
Tallinn University of Technology
Abstract:
This talk concerns the categorical representation of the partial recursive functions. Specifically, I will introduce Elgot categories, which are a sort of structured rig category in which all partial recursive functions are representable. Spefically, an Elgot category is a (uniform) traced cocartesian rig category with a distinguished isomorphism for some object .
I will construct an initial Elgot category, the morphisms of which will coincide with the abacus programs of Lambek. Finally, I will show that in this initial Elgot category, the class of strongly representable partial functions is precisely the class of partial recursive functions.