2022/06/16 by Gordon Plotkin, Plotkin, Gordon
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #Mathematical and Theoretical Analysis
paper · pdf · doi:10.48550/arxiv.2206.08413
openalex publication_date 2022/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that adding recursion does not increase the total functions definable in the typed λβη-calculus or the partial functions definable in the λΩ-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.