Elgot Categories and Abacus Programs

Abstract

We introduce Elgot categories, a sort of distributive monoidal category with additional structure in which the partial recursive functions are representable. Moreover, we construct an initial Elgot category, the morphisms of which coincide with a lightly modified version of Lambek's abacus programs. The partial functions that are strongly representable in this initial Elgot category are precisely the partial recursive ones.

In peer rewview, although not at MFPS, I'm just using their style files!