Recursion does not always help

Abstract

We show that adding recursion does not increase the total functions definable in the typed $\lambda \beta \eta$-calculus or the partial functions definable in the $\lambda \Omega$-calculus. As a consequence, adding recursion does not increase the class of partial or total definable functions on free algebras and so, in particular, on the natural numbers.

arXiv commentImproved presentation a little