Aspects of Recursion Theory in Arithmetical Theories and Categories

Abstract

Traditional recursion theory is the study of computable functions on the natural numbers. This thesis considers recursion theory in first-order arithmetical theories and categories, thus expanding the work of Ritchie and Young, Lambek, Scott, and Hofstra.

We give a complete characterisation of the representability of computable functions in arithmetical theories, paying attention to the differences between intuitionistic and classical theories and between theories with and without induction. When considering recursion theory from a category-theoretic perspective, we examine syntactic categories of arithmetical theories. In this setting, we construct a strong parameterised natural numbers object and give necessary and sufficient conditions to construct a Turing category associated to an intuitionistic arithmetical theory with induction.