Fixed point theorems, numberings, and partial combinatory algebra

Sebastiaan Terwijn, Radboud University Nijmegen. Part of the Logic Seminar Series.

Kleene's recursion theorem is a basic but somewhat counterintuitive result from computability theory.  It was found by Kleene in his studies of the lambda calculus.  There is a nice survey paper by Moschovakis listing many applications of the recursion theorem (see below). 

We discuss several extensions of Kleene's recursion theorem, including Visser's ADN theorem and Arslanov's completeness criterion, and we prove a joint generalization of these theorems.

We will also discuss fixed point theorems in the extended setting of numberings, and the extent to which the various fixed point theorems are effective. 

In recent work with Henk Barendregt we generalized the setting from numberings on the natural numbers to numberings on a partial combinatory algebra.  We show that a generalization of Ershov's fixed point theorem holds in this setting.

Y. N. Moschovakis, 
Kleene's amazing second recursion theorem, 
Bulletin of Symbolic Logic 2010.

S. A. Terwijn, 
Generalizations of the recursion theorem, 
Journal of Symbolic Logic 2018.

S. A. Terwijn, 
The noneffectivity of Arslanov's completeness criterion and related theorems, 
Archive for Mathematical Logic 2020. 

H. P. Barendregt and S. A. Terwijn,
Fixed point theorems for precomplete numberings, 
Annals of Pure and Applied Logic 2019.