Partial Recursive Functions and Finality

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We seek universal categorical conditions ensuring the representability of all partial recursive functions. In the category Pfn of sets and partial functions, the natural numbers provide both an initial algebra and a final coalgebra for the functor 1 + −. We recount how finality yields closure of the partial functions on natural numbers under Kleene’s μ-recursion scheme. Noting that Pfn is not cartesian, we then build on work of Paré and Román, obtaining weak initiality and finality conditions on natural numbers algebras in monoidal categories that ensure the (weak) representability of all partial recursive functions. We further obtain some positive results on strong representability. All these results adapt to Kleisli categories of cartesian categories with natural numbers algebras. However, in general, not all partial recursive functions need be strongly representable.
Original languageEnglish
Title of host publicationComputation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky
Subtitle of host publicationEssays Dedicated to Samson Abramsky on the Occasion of His 60th Birthday
PublisherSpringer Berlin Heidelberg
Pages311-326
Number of pages16
Volume7860
ISBN (Electronic)978-3-642-38164-5
ISBN (Print)978-3-642-38163-8
DOIs
Publication statusPublished - 2013

Fingerprint Dive into the research topics of 'Partial Recursive Functions and Finality'. Together they form a unique fingerprint.

Cite this