Kleene's Two Kinds of Recursion

2016/02/19 by G. A. Kavvos, Kavvos, G. A.
Computer Science · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems

paper · pdf · doi:10.48550/arxiv.1602.06220

openalex publication_date 2016/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This is an elementary expository article regarding the application of Kleene's Recursion Theorems in making definitions by recursion. Whereas the Second Recursion Theorem (SRT) is applicable in a first-order setting, the First Recursion Theorem (FRT) requires a higher-order setting. In some cases both theorems are applicable, but one is stronger than the other: the FRT always produces least fixed points, but this is not always the case with the SRT. Nevertheless, an old result by Rogers allows us to bridge this gap by subtly redefining the implementation of a higher-order functional in order to bring it to a `standard form.'

Related

• Kleene, Rogers and Rice Theorems Revisited in C and in Bash
• Elementary recursive algorithms
• On the Semantics of Intensionality and Intensional Recursion
• Higher-Order Recursion Abstraction: How to Make Ackermann, Knuth and Conway Look Like a Bunch of Primitives, Figuratively Speaking
• Ordinal Recursion Theory